Добро пожаловать в пост №4 из серии, посвященной изучению алгоритмов с помощью JavaScript. В этом сообщении блога я хотел бы поговорить о быстрой сортировке и о том, почему это так важно.

Что такое быстрая сортировка?

Первоначально алгоритм был разработан британским компьютерным ученым Тони Хоаром в 1959 году. Он до сих пор широко используется для сортировки. При правильной реализации он может быть примерно в два или три раза быстрее, чем его основные конкуренты, Merge sort и Heapsort.

Быстрая сортировка - это алгоритм "разделяй и властвуй". Он работает путем выбора элемента поворота из массива и разделения других элементов на два подмассива в зависимости от того, больше они или меньше элемента поворота. Затем подмассивы рекурсивно сортируются. Это можно сделать на месте, потребовав небольшого дополнительного объема памяти для выполнения сортировки.

Существует множество различных версий быстрой сортировки, которые выбирают точку поворота по-разному:

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

Как работает быстрая сортировка простыми словами:

  1. Сначала выберите элемент, который будет называться стержневым элементом.
  2. Затем сравните все элементы массива с выбранным элементом поворота и расположите их таким образом, чтобы элементы меньше, чем элемент поворота, находились слева от него, а элементы больше, чем элемент поворота, были справа.
  3. Наконец, проделайте те же операции с левым и правым боковыми элементами для элемента поворота.

Почему важна быстрая сортировка?

Как и многие другие популярные языки, JavaScript имеет встроенный метод сортировки массивов. Хотя конечный результат один и тот же, различные движки JavaScript реализуют этот метод, используя разные алгоритмы сортировки:

Итак, вы, возможно, слышали о sort (), которая уже доступна в JavaScript. Тогда вы могли подумать, зачем нужен этот алгоритм быстрой сортировки.

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

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

Выполнение

Сначала добавьте несколько вспомогательных функций:

Быстрая сортировка по схеме разделения Хоара:

Пошаговые инструкции:

  1. Сначала найдите в массиве элемент «pivot» (индекс). (в этом случае индекс всегда является средним объектом - строка 18)
  2. Начать левый указатель с первого элемента массива.
  3. Начать правый указатель с последнего элемента массива.
  4. Сравните элемент, указывающий с левым указателем, и, если он меньше, чем элемент поворота, переместите левый указатель вправо. Продолжайте так, пока левый боковой элемент не станет больше или равен элементу поворота.
  5. Сравните элемент, указывающий с правым указателем, и, если он больше, чем элемент поворота, переместите правый указатель влево. Продолжайте так, пока правый боковой элемент не станет меньше или равен элементу поворота.
  6. Убедитесь, что левый указатель меньше или равен правому указателю, а затем увидел элементы в местах расположения этих указателей.
  7. Увеличьте левый указатель и уменьшите правый указатель.
  8. Если индекс левого указателя все еще меньше индекса правого указателя, повторите процесс; иначе вернет индекс левого указателя.

Быстрая сортировка по схеме разделов Ломуто:

Шаг за шагом:

  1. Выберите «поворотный» (индекс), который обычно является последним элементом в массиве. (строка 18)
  2. Начать указатель с элемента start массива. (строка 17)
  3. Проверьте, меньше ли значение в текущем указателе (переменная i), чем значение, затем поменять местами значения указателя index и текущего элемента .
  4. Увеличьте указатель индекса.
  5. После цикла for позволяет поменять местами выбранные «сводную точку» и индекс.
  6. После этого у нас есть 2 подмассива, значения левой стороны от «pivot» ниже, справа - больше.
  7. Проверяйте рекурсивно, пока начальный индекс не станет больше или равен до конца

Хоар против Люмоту:

Измерение производительности:

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

Там Ломуто нужно втрое столько же, сколько Хоару!

Количество сравнений

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

Количество свопов

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

Поскольку учитывается только относительный порядок, мы предполагаем, что элементами являются числа 1,…, 𝑛. Это упрощает обсуждение ниже, поскольку ранг элемента и его значение совпадают.

Шаблон доступа к памяти

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

Вывод

Метод Ломуто прост и проще в реализации, но его не следует использовать для реализации метода сортировки библиотеки.

P.S

Проблема голландского национального флага (DNF) - одна из самых популярных программных задач, предложенных Эдсгером Дейкстра. Флаг Нидерландов состоит из трех цветов: белого, красного и синего. Задача состоит в том, чтобы случайным образом расположить шары белого, красного и синего цветов так, чтобы шары одного цвета располагались вместе.

Проблема тесно связана с операцией разбиения Quicksort, и мы рассмотрим эту проблему с помощью Javascript позже.

#Ресурсы: