Szybkie sortowanie w JavaScript

Algorytm Quicksort dzieli listę na pod liściami, a następnie łączy te podmioty, aby osiągnąć posortowaną listę. Wykorzystuje podejście podziału i podbijania do sortowania elementów tablicy. Istnieje wiele algorytmów do sortowania listy, ale Quicksort jest uważany za jeden z najlepszych wśród tych wszystkich algorytmów.

Jak działa algorytm szybkiego sortowania

Algorytm Quicksort wybiera element i uważa go za element obrotowy; Teraz element obrotu jest zarezerwowany.

Następnie weźmiemy dwa wskazówki „P” i „Q”.

Wskaźnik „P” przesunie się z lewej strony po prawej stronie i nie zatrzyma.

Drugi wskaźnik „Q” przesunie się z prawej strony po lewej stronie i przestanie wyszukiwać, gdy znajdzie element mniejszy lub równy elementowi obrotowego.

Tak więc, „P” sortuje mniejsze elementy po lewej stronie, a „Q” sortuje większe elementy po prawej stronie.

Teraz zrozumiemy działanie algorytmu szybkiego sortowania za pomocą przykładu:

Załóżmy, że mamy szereg sześciu elementów i chcemy to sortować w kolejności rosnącej za pomocą algorytmu Quicksort:

W początkowym etapie wybieramy „36” jako element obrotowy (element środkowy):

W następnym kroku wybieramy nasze wskaźniki, wskaźnik „P”, aby przesunąć się od lewej do prawej i wskaźnik „Q”, aby przesunąć się z prawej strony na lewą stronę:

Teraz wartość lewego wskaźnika „P” zostanie porównana z wartością obrotu, ponieważ „35” jest mniejsza niż „36” przenieś wskaźnik „P” do sąsiedniego elementu. Z drugiej strony, porównaj wartość prawego wskaźnika „Q” z wartością obrotową, „39” jest większy niż „36”, więc wskaźnik „Q” przesunie się w lewy sąsiedni element:

Teraz wskaźnik „p” wskazuje na „33” i jest porównywany z obrotem „36”, wartość wskaźnika „p” jest mniejsza niż wartość obrotu, dlatego wskaźnik „p” zostanie przesunięty na przylegający element. Podczas gdy wartość wskaźnika „Q” 32 ”jest mniejsza niż wartość obrotowa„ 36 ”, więc zatrzyma się tutaj:

Wartość lewego wskaźnika „37” jest większa niż wartość obrotu „36”, więc też się zatrzyma. Teraz „P” zatrzymuje się na „37” i „Q” zatrzymuje się na „32”.

Teraz sprawdzimy, czy wskaźnik „P” przecina wskaźnik „Q”, czy nie. W takim przypadku do tej pory „P” nie przekracza wskaźnika „Q”, więc zamienimy wartość wskaźnika „P” z wartością wskaźnika „Q”:

Teraz „P” i „Q” wskazują odpowiednio na „32” i „37”, przesuwają wskaźniki jeszcze raz, teraz p = q ('36 '=' 36 '):

Poruszaj wskaźniki jeszcze raz, gdy wskaźnik „P” przecina wskaźnik „Q”, więc tutaj zatrzyma się i zwróci indeks wskaźnika „P”. Do tej pory element obrotu znajduje się w prawej pozycji, a wszystkie elementy większe niż element obrotu znajdują się po prawej stronie obrotu, a wszystkie elementy mniejsze niż elementy obrotowe znajdują się po lewej stronie obrotu. W ten sposób sortujemy całą listę.

Teraz wdrożymy tę koncepcję w JavaScript. Po pierwsze, kod do zamiany elementów:

funkcja swap_elements (elementy, left_index, prawy_index)
var temp = elementy [left_index];
elementy [left_index] = elementy [right_index];
elementy [prawe_index] = temp;

Następnie kod podzielony listę na podmioty:

funkcja sub_lists (elementy, lewy_pointer, right_pointer)
var pivot = elementy [matematyka.podłoga ((prawe_pointer + lewy_pointer) / 2)],
i = left_pointer,
j = prawy_pointer;
podczas gdy ja <= j)
while (elementy [i] obrotowe)
J--;

if (i 1)
index = sub_Lists (elementy, lewy_pointer, prawy_pointer);
if (left_pointer < index - 1)
Quick_Sort (elementy, left_pointer, indeks - 1);

if (indeks < right_pointer)
Quick_Sort (elementy, indeks, prawy_pointer);


elementy zwrotne;

Utworzyliśmy funkcję, która przyjmuje trzy parametry w ramach funkcji. Dzielimy całą listę na sub-listę i dowiadujemy się o lewym wskaźniku i prawym wskaźniku i piszemy kod, aby zwiększyć lewy wskaźnik, jeśli jest mniej niż element obrotowy i zmniejszamy prawy wskaźnik, jeśli jest większy niż element obrotu:

Teraz napiszemy kod, aby obsłużyć zachowanie rekurencyjne szybkiego rodzaju. Ponieważ w powyższym kroku po lewej stronie jest zwracany i wykorzystamy go do podzielenia listy na podlity i zastosowanie Quicksort na tych podlicach:

funkcja Quick_Sort (elementy, lewy_pointer, prawy_pointer)
indeks var;
if (elementy.długość> 1)
index = sub_Lists (elementy, lewy_pointer, prawy_pointer);
if (left_pointer < index - 1)
Quick_Sort (elementy, left_pointer, indeks - 1);

if (indeks < right_pointer)
Quick_Sort (elementy, indeks, prawy_pointer);


elementy zwrotne;

Kompletny fragment kodu pójdzie w ten sposób:

elementy var = [35,33,37,36,32,39];
funkcja swap_elements (elementy, left_index, prawy_index)
var temp = elementy [left_index];
elementy [left_index] = elementy [right_index];
elementy [prawe_index] = temp;

funkcja sub_lists (elementy, lewy_pointer, right_pointer)
var pivot = elementy [matematyka.podłoga ((prawe_pointer + lewy_pointer) / 2)],
i = left_pointer,
j = prawy_pointer;
podczas gdy ja <= j)
while (elementy [i] obrotowe)
J--;

if (i 1)
index = sub_Lists (elementy, lewy_pointer, prawy_pointer);
if (left_pointer < index - 1)
Quick_Sort (elementy, left_pointer, indeks - 1);

if (indeks < right_pointer)
Quick_Sort (elementy, indeks, prawy_pointer);


elementy zwrotne;

var sorted_array = Quick_Sort (elementy, 0, elementy.długość - 1);
konsola.log („Sortowana lista:”, sorted_array);

Zainicjowaliśmy nieprojektowaną tablicę na początku programu i na końcu programu nazwaliśmy funkcję „Quick_Sort ()”, aby uzyskać ostateczną tablicę sortowanej:

Wreszcie, kiedy uruchamiamy ten kod, otrzymujemy wynikowe dane wyjściowe jako:

Wniosek:

Quicksort to algorytm sortowania, który działa na filozofię podziału i pokonuje i dzieli problem na mniejsze subproblemy. I kontynuuj ten proces, aż osiągniesz wynikowy cel. W tym artykule omawiamy, jak działa Quicksort i wdraża tę koncepcję do JavaScript, aby uporządkować dowolną tablicę w najbardziej wydajny sposób.