Перевод статьи «An intro to advanced sorting algorithms: merge, quick & radix sort in JS».
Ранее мы уже рассматривали алгоритмы сортировки пузырьком, выбором и вставками. Теперь давайте рассмотрим сортировку слиянием, быструю сортировку и поразрядную сортировку. Все они более совершенны в плане средней временной сложности, которая составляет меньше, чем O(n²). Перейдем к более детальному разбору.
Сортировка слиянием (merge sort)
При сортировке слиянием список разбивается на его составляющие. Затем происходит сортировка этих частей с постепенным слиянием результатов во все возрастающие отсортированные списки.
На практике это означает разделение массива на массивы, содержащие по одному элементу, а затем помещение каждого элемента в больший массив (начиная с элемента с меньшим значением). Каждый этап помещения элементов двух меньших массивов в один больший связан с определением, какой из массивов имеет меньшее значение.
Сложность сортировки слиянием составляет O((n log n) + 1). Мы помним, что «О» большое это подсчет количества операций (О) относительно количества элементов (n). Таким образом, список из 4 элементов требует 3 разбиений. Обратите внимание, что для простоты примера список здесь уже отсортирован.
Для слияния 4 массивов нужно произвести 6 сравнений.
То есть, в математическом выражении это будет выглядеть так:
Если брать по-простому, то сложность сортировки слиянием это O(n log n). «+1» незначительно по сравнению со значением n log n. Предполагается, что основа логарифма – 2.
Быстрая сортировка (quick sort)
При быстрой сортировке выбирается опорное значение (например, значение элемента под индексом 0), все элементы с меньшими значениями перемещаются в одну сторону от него, а с большими – в другую. Опорный элемент при этом оказывается на своей правильной позиции. Затем процесс повторяется для элементов справа и слева от опорного элемента.
Подобно сортировке слиянием, при быстрой сортировке список разбивается на меньшие списки. Только здесь для упорядочивания списка выбирается опорное значение, а далее элементы с меньшим значением, чем опорное, смещаются влево, а с большим — вправо. Не удивительно, что сложность быстрой сортировки тоже O(n log n).
Итак, для массива из 4 элементов выбирается опорное значение. Далее происходит поиск правильного местоположения для этого опорного значения (например, значение 2 должно быть у элемента с индексом 1). Для того чтобы найти правильное положение, делается 3 сравнения опорного значения (2) с остальными значениями (4, 3 и 1).
Частично отсортированный массив (1, 2, 4, 3) делится на части для поиска позиций для новых опорных значений – 1 и 4 (4 при этом сравнивается с 3), а затем находится позиция для последнего опорного значения (3). Т.е., нужно произвести 4 сравнения и найти 4 опорные позиции:
Поразрядная сортировка (radix sort)
В этом случае числа (101, 54, 305, 6, 81) сначала упорядочиваются по единицам, затем по десяткам и, наконец, по сотням (т. е., по разрядам, от меньшего к большему).
На практике это означает создание блоков (по цифрам от 0 до 9) для хранения чисел с одинаковыми цифрами в одинаковых разрядах (например, у 101 и 81 в разряде единиц одинаковая цифра – 1). Затем все числа комбинируются по порядку их блоков (сначала по единицам: 101, 81, 54, 305, 6). После этого процесс повторяется для цифр на позиции десятков, сотен и т. д.
В целом, сложность поразрядной сортировки – O(kn), где n это число элементов, а k – среднее количество цифр в числах (разрядов элементов).
Количество чисел, которые нужно упорядочить (n), это число операций по помещению элементов списка в блоки. Т.е., для списка чисел 101, 54, 305, 6, 81 требуется как минимум 5 блоков.
Чем выше количество разрядов (k) в числах, тем больше раз потребуется повторить процесс сортировки. Наш список 101, 54, 305, 6, 81 требует помещать элементы в блоки 15 раз: по 5 раз для единиц, десятков и сотен.
Заключение
Изучение продвинутых алгоритмов не избавляет нас от необходимости изучения самых базовых. Именно изучение основных алгоритмов дает нам понятие о поиске и сортировке. А в процессе изучения мы начинаем понимать проблемы, связанные с этими алгоритмами.
[customscript]techrocks_custom_after_post_html[/customscript]
[customscript]techrocks_custom_script[/customscript]