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

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

Алгоритм швидкого сортування слідує підходу Divide and Conquer. Він розділяє елементи на менші частини залежно від певної умови та виконує операції сортування цих розділених менших частин.

Алгоритм швидкого сортування - один з найбільш часто використовуваних і популярних алгоритмів будь-якої мови програмування. Але, якщо ви розробник JavaScript, ви можете почути про sort (), який вже доступний у JavaScript. Тоді ви могли подумати, у чому полягає потреба цього алгоритму швидкого сортування. Щоб зрозуміти це, спочатку нам потрібно, що таке сортування, а яке сортування за замовчуванням у JavaScript.

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

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

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

Як вже згадувалося раніше, JavaScript має sort () . Візьмемо приклад з кількома масивами елементів, таких як [5,3,7,6,2,9], і хочемо відсортувати ці елементи масиву за зростанням. Просто викликайте sort () для масиву items, і він сортує елементи масиву за зростанням.

Код:

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

Яка причина вибрати швидке сортування порівняно із типовим сортуванням () у JavaScript

Хоча sort () дає результат, який ми хочемо, проблема полягає в способі сортування елементів масиву. За замовчуванням сортування () у JavaScript використовує сортування за вставкою за V8 Engine Chrome та об’єднання за допомогою Mozilla Firefox та Safari .

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

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

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

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

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

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

Як працює QuickSort

Спочатку знайдіть елемент "pivot" у масиві.
Запустіть лівий покажчик з першого елемента масиву.
Запустіть правий покажчик на останньому елементі масиву.
Порівняйте елемент, що вказує, з лівим покажчиком, і якщо він менше, ніж елемент повороту, то перемістіть лівий вказівник праворуч (додайте 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;}

Виконайте рекурсивну операцію

Після виконання вищевказаних кроків буде повернуто індекс лівого вказівника, і нам потрібно використовувати це, щоб розділити масив і виконати швидке сортування для цієї частини. Отже, він називається алгоритмом Divide and Conquer.

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

Примітка: Швидке сортування виконується на тому самому масиві, і в процесі не створюються нові масиви.

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

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]