Алгоритм быстрой сортировки в JavaСценарий

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

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

Сортировка по умолчанию JavaСценарий

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

Код:

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

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

Хотя функция sort() дает желаемый результат, проблема заключается в том, как она сортирует элементы массива. Сортировка по умолчанию() в JavaСкрипт использует сортировка вставок by Двигатель V8 Chrome и Сортировка слиянием by Mozilla Firefox и Сафари.

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

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

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

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

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

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

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

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

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

Определить элемент Pivot

Но прежде чем приступить к быстрой сортировке, важную роль играет выбор опорного элемента. Если вы выберете первый элемент в качестве элемента поворота, это даст худшую производительность в отсортированном массиве. Поэтому всегда желательно выбирать средний элемент (длина массива, разделенная на 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, переместите указатели еще на один шаг и остановитесь, когда левый указатель пересекает правый указатель, и верните индекс левого указателя.

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

Код для обмена двух чисел JavaСценарий

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 element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //swap two elements
            i++;
            j--;
        }
    }
    return i;
}

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

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

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

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

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

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var 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 element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //sawpping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var sortedArray = quickSort(items, 0, items.length - 1);
console.log(sortedArray); //prints [2,3,5,6,7,9]

ПРИМЕЧАНИЕ: Быстрая сортировка выполняется с временной сложностью О(нлогн).