Есть (нет?) Тридцать шесть способов отсортировать массив

Алгоритмы сортировки на основе сравнения

Вступление

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

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

Примеры реализации написаны на JavaScript и заимствованы из App Academy с моими собственными изменениями и комментариями. Все ошибки - мои собственные.

Алгоритмы сортировки на основе сравнения

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

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

function swap(arr, index1, index2) {
  let temp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = temp;
}

Примечание. В JS ES6 свопинг без использования временной переменной стал возможен с деструктуризацией (например, [arr[2], arr[1]] = [arr[1], arr[2]]).

Наихудший случай временной сложности этих четырех алгоритмов равен O (n²): пузырьковая сортировка, сортировка по выбору, сортировка вставкой, быстрая сортировка.

Наихудшая временная сложность этих двух алгоритмов равна O (n log n): сортировка слиянием, рандомизированная быстрая сортировка.

Пузырьковая сортировка

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

function bubbleSort(array) {
  let swapped = true;
  while(swapped) {
    swapped = false;
    for (let i = 0; i < array.length - 1; i++) {  
      if (array[i] > array[i+1]) { //if this condition is not met
        swap(array, i, i+1);
        swapped = true; //the outer loop exits when the inner's done
      }
    }
  }
  return array;
}

Выбор Сортировка

Внешний цикл проходит через массив по одному элементу за раз, в то время как внутренний цикл находит наименьший несортированный элемент (то есть наименьший элемент справа от i). Когда внутренний цикл завершается, элемент, с которого он начался, становится минимальным значением. Затем внешний цикл начинает еще один проход с элементом в (i + 1).

function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) { 
    let minIndex = i;
for (let j = i + 1; j < arr.length; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    swap(arr, i, minIndex);
  }
  return arr;
}

Вставка сортировки

Сортировка вставками больше всего похожа на технику сортировки, которую я использовал на одной из моих первых работ, когда книги на полках библиотеки располагались в алфавитном порядке по автору и названию. Подобно сортировке по выбору и в отличие от пузырьковой сортировки, она работает слева направо, перемещая элементы более чем на одно место за раз в отсортированный раздел. Однако, в отличие от сортировки по выбору, внутренний цикл поочередно перемещается по отсортированной части массива, чтобы найти место для оцениваемого элемента во внешнем цикле. Внешний цикл движется слева направо, в то время как внутренний цикл движется в другом направлении, сдвигая каждый элемент на один вправо, пока не обнаружит, что оцениваемый элемент не меньше, чем следующий элемент слева от него. Затем он сохраняет сортируемый элемент в пространстве повторяющегося элемента.

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) { // moves right
    let currElement = arr[i];
for (var j = i - 1; j >= 0 && currElement < arr[j]; j--) {
      arr[j + 1] = arr[j]; // each element is shifted right
    } // starting from the right-most element of the sorted portion
      // so arr[i] becomes the right-most sorted element, etc.
arr[j + 1] = currElement; //when arr[j] < element
  }
return arr;
}

Сортировка слиянием

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

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

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

    let midIdx = Math.floor(array.length / 2);
    let leftHalf = array.slice(0, midIdx);
    let rightHalf = array.slice(midIdx);

    let sortedLeft = mergeSort(leftHalf);
    let sortedRight = mergeSort(rightHalf);

    return merge(sortedLeft, sortedRight);
}

Вспомогательная функция merge берет два отсортированных массива и объединяет их, сравнивая их первые элементы один за другим.

function merge(array1, array2) {
    let merged = [];

    while (array1.length || array2.length) {
        let ele1 = array1.length ? array1[0] : Infinity;
        let ele2 = array2.length ? array2[0] : Infinity;

        let next;
        if (ele1 < ele2) {
            next = array1.shift();
        } else {
            next = array2.shift();
        }

        merged.push(next);
    }

    return merged;
}

Согласно Visualgo:

В отличие от того, что обычно показывают многие другие печатные учебники CS (поскольку учебники статичны), фактическое выполнение сортировки слиянием не разбивается на два подмассива уровень за уровнем, но оно будет рекурсивно отсортируйте левый подмассив, прежде чем работать с правым подмассивом.

Вот и все, в примере массива [7, 2, 6, 3, 8, 4, 5] он будет рекурсивен к [7, 2, 6, 3], затем [7, 2], затем [7] (a одиночный элемент, отсортированный по умолчанию), возврат, возврат к [2] (отсортированный), возврат, затем окончательное слияние [7, 2] с [2, 7], прежде чем он продолжит обработку [6, 3] и так далее.

Сортировка слиянием выполняется за O (n * log n) - длина ввода умножается на количество рекурсивных вызовов, которые нам нужно сделать, чтобы уменьшить его вдвое. В отличие от других описанных выше алгоритмов сортировки, которые имеют O (1), сортировка слиянием неэффективна с точки зрения памяти. Сложность пространства равна O (n), потому что нам нужно создать новый массив для каждого элемента.

Быстрая сортировка

Быстрая сортировка, как и сортировка слиянием, представляет собой алгоритм «разделяй и властвуй», который разбивает входной массив на отсортированные массивы и объединяет их. Разница в реализации заключается в том, что быстрая сортировка разбивает массив пополам не по их индексу, а по значению элементов относительно точки поворота.

Элементы меньше поворота попадают в левый массив, а элементы больше поворота справа.

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

    let pivot = array.shift();
    let left = array.filter(el => el < pivot);
    let right = array.filter(el => el >= pivot);

    let leftSorted = quickSort(left);
    let rightSorted = quickSort(right);

    return leftSorted.concat([pivot]).concat(rightSorted);
    // in ES6 you can use the spread operator:
    // return [ ...leftSorted, pivot, ...rightSorted ]
}

Затем отсортированные массивы объединяются и возвращаются. Если в худшем случае вы выберете наименее оптимальную точку поворота, сложность выполнения будет O (n²) из-за рекурсивных вызовов filter (что составляет O (n) или в данном случае O (2n)).

Показанная здесь реализация быстрой сортировки имеет пространственную сложность O (n), потому что, как и сортировка слиянием, мы создаем новый массив для каждого элемента во входных данных, но если вы поменяете местами элементы на месте, сложность пространства будет O (log n) .

Рандомизированная быстрая сортировка

Если вы знаете, что ваши входные массивы уже в основном отсортированы, запускать их через реализацию быстрой сортировки, которую мы определили выше, не является хорошей идеей. Первый элемент будет одним из самых маленьких, и вам придется сортировать длинный массив. Выбор случайной точки поворота решает эту проблему.

И это еще не все ...

Алгоритмы сортировки, не основанные на сравнении, будут рассмотрены в следующей статье. Они быстрее, чем алгоритмы сортировки на основе сравнения. Наихудшая временная сложность для подсчета сортировки составляет O (n + k) и O (w * (n + k)) для сортировки по основанию.

Дополнительные ресурсы