QuickSort algoritmus a JavaScript-ben

Mi a gyors rendezés?

A Gyors rendezés algoritmus a Divide and Conquer megközelítést követi. Ezeket az elemeket valamilyen feltétel alapján kisebb részekre osztja, és a felosztott kisebb részeken elvégzi a rendezési műveleteket.

A Quick Sort algoritmus az egyik leggyakrabban használt és legnépszerűbb algoritmus minden programozási nyelven. De ha Ön JavaScript fejlesztő, akkor hallhat a sort () -ról, amely már elérhető a JavaScript-ben. Akkor gondolkodhatott azon, hogy mire van szüksége ennek a Gyors rendezés algoritmusnak. Ennek megértéséhez először arra van szükségünk, hogy mi a rendezés és mi az alapértelmezett rendezés a JavaScript-ben.

Mi a rendezés?

A rendezés nem más, mint az elemek elrendezése a kívánt sorrendben. Talán találkozhatott ezzel az iskolai vagy főiskolai napjaiban. Mint a számok kisebbről nagyobbra (növekvő) vagy nagyobbról kisebbre (csökkenő) rendezését láttuk, ezt láttuk eddig, és rendezésnek nevezzük.

Alapértelmezett rendezés a JavaScript-ben

Mint korábban említettük, a JavaScript-nek van sort () . Vegyünk egy példát néhány olyan tömb elemmel, mint az [5,3,7,6,2,9], és ezt a tömb elemet növekvő sorrendben szeretnénk rendezni. Csak hívja meg a sort () elemet a tömbön, és a tömb elemeit növekvő sorrendbe rendezi.

Kód:

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

Mi az oka annak, hogy a Gyors rendezés helyett az alapértelmezett rendezést () választja a JavaScript-ben

Bár a sort () megadja a kívánt eredményt, a probléma abban rejlik, hogy miként rendezi a tömb elemeket. Default sort () JavaScript használ behelyezés sorrend szerint V8 motor Chrome és egyesítése rendezés által Mozilla Firefox és Safari .

De más, ez nem megfelelő, ha nagy számú elemet kell rendezni. Tehát a megoldás a Gyors rendezés használata nagy adatkészlethez.

Tehát a teljes megértéshez tudnia kell, hogyan működik a Gyors rendezés, és ezt most részletesen lássuk.

Mi a Gyors rendezés?

A gyors rendezés a Divide and Conquer algoritmust követi . Elemeket oszt meg kisebb részekre valamilyen feltétel alapján, és elvégzi a rendezési műveleteket az osztott kisebb részeken. Ezért jól működik nagy adatkészleteknél. Tehát íme a gyors rendezés egyszerű szavakkal történő lépése.

Először válasszon ki egy elemet, amelyet pivot elemként kell meghívni .
Ezután hasonlítsa össze az összes tömb elemet a kiválasztott pivot elemmel, és rendezze őket úgy, hogy a pivot elemnél kisebb elemek balra, a pivotnál pedig nagyobbak legyenek jobbra.
Végül hajtsa végre ugyanazokat a műveleteket a bal és a jobb oldali elemeken az elforduló elemig.

Tehát ez a Quick sort alapvázlata. Itt vannak azok a lépések, amelyeket egyenként kell követni a gyors rendezéshez.

Hogyan működik a QuickSort

Először keresse meg a "pivot" elemet a tömbben.
Indítsa el a bal mutatót a tömb első eleménél.
Indítsa el a jobb mutatót a tömb utolsó eleménél.
Hasonlítsa össze a mutatót a bal mutatóval, és ha ez kisebb, mint a forgó elem, akkor mozgassa a bal mutatót jobbra (adjon 1-et a bal indexhez). Addig folytassa ezt, amíg a bal oldali elem nagyobb vagy egyenlő, mint az elforduló elem.
Hasonlítsa össze a mutatót a jobb mutatóval, és ha nagyobb, mint a forgó elem, akkor mozgassa a jobb mutatót balra (vonja le az 1-et a jobb indexre). Folytassa ezt addig, amíg a jobb oldali elem kisebb vagy egyenlő, mint az elforduló elem.
Ellenőrizze, hogy a bal mutató kisebb vagy egyenlő-e a jobb mutatóval, majd látta meg az elemeket ezen mutatók helyén.
Növelje a bal és a jobb mutatót.
Ha a bal mutató mutatója még mindig kisebb, mint a jobb mutató indexe, akkor ismételje meg a folyamatot; másként adja vissza a bal mutató indexét.

Tehát nézzük meg ezeket a lépéseket egy példával. Vegyük fontolóra azon elemek tömbjét, amelyeket rendezni kell [5,3,7,6,2,9].

Határozza meg a Pivot elemet

De mielőtt továbblépnénk a Gyors rendezésre, a forgó elem kiválasztása játszik nagy szerepet. Ha az első elemet választja el forgó elemként, akkor az a legrosszabb teljesítményt nyújtja a rendezett tömbben. Tehát mindig tanácsos a középső elemet (a tömb hosszát elosztani 2-vel) kiválasztani forgó elemként, és mi is ezt tesszük.

Az alábbiakban bemutatjuk a [5,3,7,6,2,9] példával bemutatott gyors rendezés végrehajtásának lépéseit.

1. LÉPÉS: Határozza meg a forgást középső elemként. Tehát a 7 a forgó elem.

2. LÉPÉS: Indítsa el a bal és a jobb mutatót a tömb első és utolsó elemeként. Tehát a bal mutató 5-re mutat a 0 indexen, a jobb mutató pedig 9-re mutat az 5-ös indexen.

3. LÉPÉS: Hasonlítsa össze az elemet a bal mutatóban az elforduló elemmel. Mivel 5 <6 tolja bal mutatót jobbra az 1 indexeléshez.

4. LÉPÉS: Most még mindig 3 <6, így tolja a bal mutatót egy másik indexre jobbra. Tehát most 7> 6 lépéssel növekszik a bal mutató, és most a bal mutató a 2. indexen van.

5. LÉPÉS: Most hasonlítsa össze a jobb mutató mutatóját az elforduló elemmel. Mivel 9> 6 mozgatja a jobb mutatót balra. Most, amikor 2 <6 megállítja a jobb mutató mozgatását.

6. LÉPÉS: Cserélje meg egymással a bal és a jobb mutatóban lévő értékeket.

7. LÉPÉS: Mozgassa mindkét mutatót még egy lépéssel.

8. LÉPÉS: Mivel 6 = 6, vigye a mutatókat még egy lépésre, és álljon le, amikor a bal mutató keresztezi a jobb mutatót, és adja vissza a bal mutató indexét.

Tehát itt a fenti megközelítés alapján kódot kell írnunk az elemek cseréjéhez és a tömb particionálásához, a fenti lépésekben említettek szerint.

Kód két szám cseréjéhez a JavaScript-ben:

function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}

Kód a partíció végrehajtásához a fenti lépések szerint:

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

Végezze el a rekurzív műveletet

Miután végrehajtotta a fenti lépéseket, a bal mutató mutatója visszatér, és ezt fel kell használnunk a tömb felosztásához és a gyors rendezéshez ezen a részen. Ezért Divide and Conquer algoritmusnak hívják.

Tehát a Gyors rendezés addig hajtódik végre, amíg a bal és a jobb tömb összes eleme rendbe nem kerül.

Megjegyzés: A gyors rendezés ugyanazon tömbön történik, és a folyamat során nem hoznak létre új tömböket.

Tehát meg kell hívnunk ezt a partíciót () , amelyet fentebb ismertettünk, és ennek alapján felosztjuk a tömböt részekre. Tehát itt van a kód, ahol használod,

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

Teljes Gyors rendezési kód:

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]