Алгоритъм за бързо сортиране в JavaScript

Какво е бързо сортиране?

Алгоритъмът за бързо сортиране следва подхода Divide and Conquer. Той разделя елементите на по-малки части въз основа на някакво условие и извършване на операции за сортиране на тези разделени по-малки части.

Алгоритъмът за бързо сортиране е един от най-използваните и популярни алгоритми на всеки език за програмиране. Но ако сте разработчик на 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]

Каква е причината да изберете Бързо сортиране пред стандартното сортиране () в JavaScript

Въпреки че sort () дава желания резултат, проблемът е в начина, по който сортира елементите на масива. Сортирането по подразбиране () в JavaScript използва сортиране по вмъкване по V8 Engine на Chrome и обединяване по Mozilla Firefox и Safari .

Но друго това не е подходящо, ако трябва да сортирате голям брой елементи. И така, решението е да се използва бързо сортиране за голям набор от данни.

Така че, за да разберете напълно, трябва да знаете как работи Бързото сортиране и да го видим в детайли сега.

Какво е бързо сортиране?

Бързото сортиране следва алгоритъма Divide and Conquer . Той разделя елементи на по-малки части въз основа на някакво условие и извършва операции за сортиране на тези разделени по-малки части. Следователно, той работи добре за големи набори от данни. И така, ето стъпките как работи бързото сортиране с прости думи.

Първо изберете елемент, който трябва да бъде извикан като опорен елемент.
След това сравнете всички елементи на масива с избрания осев елемент и ги подредете по такъв начин, че елементите, по-малки от осевия елемент, са вляво и по-големи от pivot вдясно.
И накрая, извършете същите операции върху левия и десния страничен елемент с въртящия елемент.

И така, това е основният контур на Бързото сортиране. Ето стъпките, които трябва да бъдат изпълнени една по една, за да извършите бързо сортиране.

Как работи QuickSort

Първо намерете елемента "pivot" в масива.
Стартирайте левия указател в първия елемент на масива.
Стартирайте десния указател при последния елемент от масива.
Сравнете посочващия елемент с левия показалец и ако е по-малък от въртящия елемент, преместете левия показалец надясно (добавете 1 към левия индекс). Продължете това, докато левият страничен елемент е по-голям или равен на шарнирния елемент.
Сравнете посочващия елемент с десния показалец и ако той е по-голям от въртящия елемент, преместете десния показалец наляво (извадете 1 към десния индекс). Продължете това, докато десният страничен елемент е по-малък или равен на шарнирния елемент.
Проверете дали левият показалец е по-малък или равен на десния показалец, след това видя елементите в местоположенията на тези указатели.
Увеличаване на левия показалец и намаляване на десния показалец.
Ако индексът на левия показалец е все още по-малък от индекса на десния показалец, повторете процеса; иначе връща индекса на левия указател.

И така, нека видим тези стъпки с пример. Нека разгледаме масив от елементи, които трябва да сортираме, е [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 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]