Алгоритм швидкого сортування в JavaScript

Що таке сортування?

Сортування — це не що інше, як розташування елементів у потрібному порядку. Можливо, ви стикалися з цим у школі чи коледжі. Як упорядкування чисел від меншого до більшого (зростання) або від більшого до меншого (за спаданням), ми бачили досі і називається сортуванням.

Сортування за замовчуванням JavaScript

Як згадувалося раніше, 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]

У чому причина вибору швидкого сортування замість sort() за замовчуванням JavaScript

Хоча sort() дає бажаний результат, проблема полягає в тому, як він сортує елементи масиву. Типовий сорт() в JavaСценарій використовує сортування вставки by Двигун V8 Chrome та Об’єднання сортування by Mozilla Firefox та Safari.

Але в іншому випадку це не підходить, якщо вам потрібно відсортувати велику кількість елементів. Отже, рішення полягає у використанні швидкого сортування для великого набору даних.

Отже, щоб повністю зрозуміти, вам потрібно знати, як працює швидке сортування, і давайте зараз розглянемо це детально.

Що таке швидке сортування?

Слідує швидке сортування Розділяй і володарюй алгоритм. Він ділить елементи на менші частини на основі певної умови та виконує операції сортування над цими розділеними меншими частинами. Отже, він добре працює для великих наборів даних. Отже, ось кроки, як працює швидке сортування простими словами.

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

Отже, це основний план швидкого сортування. Ось кроки, які потрібно виконувати один за одним, щоб виконати швидке сортування.

Як працює QuickSort

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, перемістіть покажчики на ще один крок і зупиніться, коли лівий покажчик перетнеться з правим, і поверніть індекс лівого покажчика.

Отже, ґрунтуючись на наведеному вище підході, нам потрібно написати код для заміни елементів і розділення масиву, як зазначено у вищезазначених кроках.

Код для заміни двох чисел 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 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]

ПРИМІТКА: Швидке сортування виконується з часовою складністю O(nlogn).