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

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

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

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

Что такое сортировка?

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

Сортировка по умолчанию в JavaScript

Как упоминалось ранее, в JavaScript есть sort () . Давайте возьмем пример с несколькими массивами элементов, такими как [5,3,7,6,2,9], и захотим отсортировать элементы этого массива в порядке возрастания. Просто вызовите sort () для массива элементов, и он отсортирует элементы массива в порядке возрастания.

Код:

var items = [5,3,7,6,2,9];console.log(items.sort());//prints [2, 3, 5, 6, 7, 9]

В чем причина выбора быстрой сортировки вместо sort () по умолчанию в JavaScript

Хотя sort () дает желаемый результат, проблема заключается в том, как он сортирует элементы массива. По умолчанию sort () в JavaScript использует сортировку вставкой в движке V8 Chrome и сортировку слиянием в Mozilla Firefox и Safari .

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

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

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

Быстрая сортировка следует алгоритму Divide and Conquer . Он разделяет элементы на более мелкие части в зависимости от некоторого условия и выполняет операции сортировки этих разделенных более мелких частей. Следовательно, он хорошо работает для больших наборов данных. Итак, вот шаги, как работает быстрая сортировка простыми словами.

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

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

Как работает QuickSort

Сначала найдите «стержневой» элемент в массиве.
Начать левый указатель с первого элемента массива.
Начать правый указатель с последнего элемента массива.
Сравните элемент, указывающий с левым указателем, и если он меньше, чем элемент поворота, переместите левый указатель вправо (добавьте 1 к левому индексу). Продолжайте это, пока левый боковой элемент не станет больше или равен элементу поворота.
Сравните элемент, указывающий с правым указателем, и, если он больше, чем элемент поворота, переместите правый указатель влево (вычтите 1 из правого индекса). Продолжайте это до тех пор, пока правый боковой элемент не станет меньше или равен элементу поворота.
Убедитесь, что левый указатель меньше или равен правому указателю, а затем увидел элементы в местах расположения этих указателей.
Увеличьте левый указатель и уменьшите правый указатель.
Если индекс левого указателя все еще меньше индекса правого указателя, повторите процесс; иначе вернет индекс левого указателя.

Итак, давайте рассмотрим эти шаги на примере. Рассмотрим массив элементов, который нам нужно отсортировать, как [5,3,7,6,2,9].

Определить сводный элемент

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

Вот шаги для выполнения быстрой сортировки, показанной на примере [5,3,7,6,2,9].

ШАГ 1: Определите опорный элемент как средний элемент. Итак, 7 - это стержневой элемент.

ШАГ 2: Начните левый и правый указатели как первый и последний элементы массива соответственно. Итак, левый указатель указывает на 5 с индексом 0, а правый указатель указывает на 9 с индексом 5.

ШАГ 3: Сравните элемент у левого указателя с элементом поворота. Так как 5 <6 сдвигает левый указатель вправо до индекса 1.

ШАГ 4: Теперь по-прежнему 3 <6, поэтому переместите левый указатель на еще один индекс вправо. Итак, теперь 7> 6 перестают увеличивать левый указатель, и теперь левый указатель находится в индексе 2.

ШАГ 5: Теперь сравните значение в правом указателе с элементом поворота. Так как 9> 6 переместите правый указатель влево. Теперь, когда 2 <6, перестаньте перемещать правый указатель.

ШАГ 6: Поменяйте местами оба значения, присутствующие на левом и правом указателях, друг с другом.

ШАГ 7: Переместите оба указателя еще на один шаг.

ШАГ 8: Поскольку 6 = 6, переместите указатели на еще один шаг и остановитесь, когда левый указатель пересечет правый указатель и вернет индекс левого указателя.

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

Код для замены двух чисел в JavaScript:

function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}

Код для выполнения раздела, как указано в шагах выше:

function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //swap two elementsi++;j--;}}return i;}

Выполните рекурсивную операцию

Как только вы выполните вышеуказанные шаги, будет возвращен индекс левого указателя, и нам нужно использовать его, чтобы разделить массив и выполнить быструю сортировку для этой части. Следовательно, он называется алгоритмом «разделяй и властвуй».

Итак, быстрая сортировка выполняется до тех пор, пока не будут отсортированы все элементы в левом массиве и правом массиве.

Примечание. Быстрая сортировка выполняется для того же массива, и в процессе не создаются новые массивы.

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

function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar result = quickSort(items, 0, items.length - 1);

Полный код быстрой сортировки:

var items = [5,3,7,6,2,9];function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //sawpping two elementsi++;j--;}}return i;}function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar sortedArray = quickSort(items, 0, items.length - 1);console.log(sortedArray); //prints [2,3,5,6,7,9]