Алгоритмы сортировки

Когда мы говорим про алгоритмы, то понимаем, что многие из них работают с отсортированными данными. Например, бинарный поиск работает так.

Какие есть алгоритмы сортировки?

• Сортировка пузырьком (Bubble Sort)
• Сортировка вставками (Insertion Sort)
• Сортировка выбором (Selection Sort)
• Сортировка слиянием (Merge Sort)
• Быстрая сортировка (Quick Sort) ... и так далее

Что важно понимать - сортировать можно не только массивы, но и связные списки, деревья и графы.

Сегодня мы рассмотрим простой алгоритм пузырьковой сортировки и более сложный алгоритм сортировки слиянием. Сортировка слиянием способна сортировать массивы и связные списки. Поэтому она нам так важна.

Bubble Sort

Она работает путем многократного прохода по списку, сравнения каждой пары соседних элементов и их обмена, если они находятся в неправильном порядке. Этот процесс повторяется до тех пор, пока не будет пройден весь список без каких-либо обменов, что означает, что список отсортирован.

Принцип действий прост: обходим массив от начала до конца, попутно меняя местами неотсортированные соседние элементы. В результате первого прохода на последнее место «всплывёт» максимальный элемент. Теперь снова обходим неотсортированную часть массива (от первого элемента до предпоследнего) и меняем по пути неотсортированных соседей. Второй по величине элемент окажется на предпоследнем месте. Продолжая в том же духе, будем обходить всё уменьшающуюся неотсортированную часть массива, запихивая найденные максимумы в конец.

Псевдокод

Функция ПузырьковаяСортировка(массив)
    n = длина(массив)
    повторять
        обменов = 0
        для i от 1 до n-1
            если массив[i-1] > массив[i]
                обмен(массив[i-1], массив[i])
                обменов = обменов + 1
        конец для
        n = n - 1
    пока обменов > 0
Конец функции

Реализация кода - классическая сортировка от меньшего к большему

function bubbleSort(array) {
  let n = array.length;
  let swapped;

  do {
    swapped = false;
    for (let i = 1; i < n; i++) {
      if (array[i - 1] > array[i]) {
        [array[i - 1], array[i]] = [array[i], array[i - 1]]; // если текущий элемент меньше предыдущего, меняем их местами
        swapped = true; // отмечаем, что был выполнен обмен
      }
    }
    n--; // уменьшаем n, так как последний элемент уже находится на своем месте
  } while (swapped); // повторяем, пока идут обмены

  return array; // возвращаем отсортированный массив
}

Реализация кода - от большего к меньшему

function bubbleSortDescending(array) {
  let n = array.length;
  let swapped;

  do {
    swapped = false;
    for (let i = 1; i < n; i++) {
      if (array[i - 1] < array[i]) {
        [array[i - 1], array[i]] = [array[i], array[i - 1]]; // если текущий элемент больше предыдущего, меняем их местами
        swapped = true; // отмечаем, что был выполнен обмен
      }
    }
    n--; // уменьшаем n, так как последний элемент уже находится на своем месте
  } while (swapped); // повторяем, пока идут обмены

  return array; // возвращаем отсортированный массив
}

Алгоритм для описания на собеседовании

1. Принимаем на вход список или массив элементов и проверяем, что его длина не равна 0.

2. Проход по массиву:

   • Сравниваем последовательно каждую пару соседних элементов.
   • Если элементы находятся в неправильном порядке (например, первый элемент больше второго при сортировке по возрастанию), меняем их местами.

3. Проверка на завершение:

   • После каждого полного прохода по массиву проверяем, были ли сделаны какие-либо обмены.
   • Если обменов не было, массив считается отсортированным и алгоритм завершает работу.
   • Если были обмены, алгоритм повторяет проход с начала.

4. Вернуть отсортированный массив.

Merge sort

Алгоритм Merge Sort работает по принципу "разделяй и властвуй". Он рекурсивно делит массив на две половины, сортирует каждую из них и затем объединяет обратно в отсортированный массив.

Псевдокод

Функция MergeSort(массив)
    если длина(массив) <= 1
        вернуть массив
    конец если
    середина = длина(массив) / 2
    левая_половина = массив от 0 до середины
    правая_половина = массив от середины до конца
    вернуть Слияние(MergeSort(левая_половина), MergeSort(правая_половина))
Конец функции

Функция Слияние(левая, правая)
    результат = пустой массив
    пока левая не пуста и правая не пуста
        если первый элемент левой <= первый элемент правой
            добавить первый элемент левой в результат
            удалить первый элемент из левой
        иначе
            добавить первый элемент правой в результат
            удалить первый элемент из правой
        конец если
    конец пока
    если левая не пуста
        добавить оставшиеся элементы левой в результат
    конец если
    если правая не пуста
        добавить оставшиеся элементы правой в результат
    конец если
    вернуть результат
Конец функции

function mergeSort(array) {
  if (array.length <= 1) {
    return array;
  }

  const middle = Math.floor(array.length / 2);
  const left = array.slice(0, middle);
  const right = array.slice(middle);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}