Алгоритам КуицкСорт у ЈаваСцрипт-у

Шта је брзо сортирање?

Алгоритам брзог сортирања следи приступ поделе и освајања. Елементе дели на мање делове на основу неког стања и извршавајући операције сортирања на тим подељеним мањим деловима.

Алгоритам брзог сортирања је један од најчешће коришћених и најпопуларнијих алгоритама у било ком програмском језику. Ако сте програмер ЈаваСцрипт-а, можда сте чули за сорт () који је већ доступан у ЈаваСцрипт-у. Тада сте можда размишљали шта је потреба овог алгоритма за брзо сортирање. Да бисмо то разумели, прво нам треба шта је сортирање и шта је подразумевано сортирање у ЈаваСцрипт-у.

Шта је сортирање?

Сортирање није ништа друго него слагање елемената по редоследу који желимо. Можда сте на ово наишли у школским или факултетским данима. Попут распоређивања бројева од мањег до већег (растућег) или од већег према мањем (опадајућег) је оно што смо до сада видели и назива се сортирање.

Подразумевано сортирање у ЈаваСцрипт-у

Као што је раније поменуто, ЈаваСцрипт има сорт () . Узмимо пример са неколико низова елемената попут [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]

Који је разлог да у ЈаваСцрипт-у изаберете Брзо сортирање у односу на подразумевано сортирање ()

Иако сорт () даје резултат који желимо, проблем лежи у начину сортирања елемената низа. Подразумевана сорта () у ЈаваСцрипт-у користи сортирање уметања по В8 Енгинеу Цхроме- а и Мерге сортирање по Мозилла Фирефок-у и Сафари-ју .

Али, друго ово није погодно ако треба да сортирате велики број елемената. Дакле, решење је коришћење брзог сортирања за велике скупове података.

Дакле, да бисте у потпуности разумели, морате знати како функционише Брзо сортирање и дозволите нам да то сада детаљно видимо.

Шта је брзо сортирање?

Брзо сортирање следи алгоритам Дивиде анд Цонкуер . Он дели елементе на мање делове на основу неког стања и изводи операције сортирања на тим подељеним мањим деловима. Отуда добро функционише за велике скупове података. Дакле, ево корака како брзо сортирање функционише једноставним речима.

Прво одаберите елемент који треба позвати као стожерни елемент.
Даље, упоредите све елементе низа са изабраним пивот елементом и распоредите их на такав начин да су елементи мањи од пивот елемента лево, а већи од пивот десно.
На крају, изводите исте операције на левом и десном бочном елементу до пивот елемента.

Дакле, то је основни приказ брзе сорте. Ево корака које треба пратити један по један да бисте извршили брзо сортирање.

Како функционише КуицкСорт

Прво пронађите елемент „пивот“ у низу.
Покрените леви показивач на првом елементу низа.
Покрените десни показивач на последњем елементу низа.
Упоредите елемент који показује са левим показивачем и ако је мањи од пивот елемента, померите леви показивач удесно (додајте 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, померите показиваче на још један корак и зауставите се док леви показивач прелази десни показивач и враћа индекс левог показивача.

Дакле, овде на основу горњег приступа, морамо да напишемо код за замену елемената и партиционирање низа као што је поменуто у горњим корацима.

Код за замену два броја у ЈаваСцрипт-у:

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;}

Извршите рекурзивну операцију

Једном када извршите горње кораке, вратит ће се индекс лијевог показивача и то морамо користити да подијелимо низ и извршимо брзо сортирање на том дијелу. Отуда се назива алгоритам Дивиде анд Цонкуер.

Дакле, брзо сортирање се изводи све док се не сортирају сви елементи у левом и десном низу.

Напомена: Брзо сортирање се врши на истом низу и у том процесу се не креирају нови низови.

Дакле, ову партицију () треба да позовемо горе објашњено и на основу тога делимо низ на делове. Дакле, овде је код где га користите,

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]