Algorytm QuickSort w JavaScript

Co to jest szybkie sortowanie?

Algorytm szybkiego sortowania jest zgodny z podejściem dziel i zwyciężaj. Dzieli elementy na mniejsze części na podstawie pewnych warunków i wykonywania operacji sortowania na tych podzielonych mniejszych częściach.

Algorytm szybkiego sortowania jest jednym z najczęściej używanych i popularnych algorytmów w każdym języku programowania. Ale jeśli jesteś programistą JavaScript, być może słyszałeś o sort (), który jest już dostępny w JavaScript. Wtedy być może zastanawiałeś się, jaka jest potrzeba tego algorytmu szybkiego sortowania. Aby to zrozumieć, najpierw potrzebujemy sortowania i domyślnego sortowania w JavaScript.

Co to jest sortowanie?

Sortowanie to nic innego jak układanie elementów w dowolnej kolejności. Mogłeś się z tym spotkać w szkole lub na studiach. Sortowanie liczb od mniejszych do większych (rosnąco) lub od większych do mniejszych (malejąco) jest tym, co widzieliśmy do tej pory i nazywa się sortowaniem.

Domyślne sortowanie w JavaScript

Jak wspomniano wcześniej, JavaScript ma funkcję sort () . Weźmy przykład z kilkoma tablicami elementów, takich jak [5,3,7,6,2,9] i chcemy posortować te elementy tablicy w porządku rosnącym. Po prostu wywołaj sort () na tablicy items i sortuje elementy tablicy w porządku rosnącym.

Kod:

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

Jaki jest powód wyboru szybkiego sortowania zamiast domyślnego sortowania () w JavaScript

Chociaż sort () daje oczekiwany wynik, problem leży w sposobie sortowania elementów tablicy. Domyślne sortowanie () w JavaScript używa sortowania przez wstawianie według silnika V8 przeglądarki Chrome i sortowania według scalania według Mozilla Firefox i Safari .

Ale inne to nie jest odpowiednie, jeśli chcesz posortować dużą liczbę elementów. Tak więc rozwiązaniem jest użycie szybkiego sortowania dla dużego zbioru danych.

Aby więc w pełni zrozumieć, musisz wiedzieć, jak działa szybkie sortowanie, i przyjrzyjmy się temu szczegółowo.

Co to jest szybkie sortowanie?

Szybkie sortowanie jest zgodne z algorytmem Dziel i rządź . Dzieli elementy na mniejsze części na podstawie pewnych warunków i wykonuje operacje sortowania na tych podzielonych mniejszych częściach. W związku z tym działa dobrze w przypadku dużych zbiorów danych. Oto kroki, jak działa szybkie sortowanie w prostych słowach.

Najpierw wybierz element, który ma być nazywany elementem obrotowym .
Następnie porównaj wszystkie elementy tablicy z wybranym elementem pivot i ułóż je w taki sposób, aby elementy mniejsze niż element pivot znajdowały się po jego lewej stronie i większe niż element pivot po jego prawej stronie.
Na koniec wykonaj te same operacje na elementach po lewej i prawej stronie elementu obrotowego.

To jest podstawowy zarys szybkiego sortowania. Oto kroki, które należy wykonać pojedynczo, aby wykonać szybkie sortowanie.

Jak działa QuickSort

Najpierw znajdź element „pivot” w tablicy.
Uruchom lewy wskaźnik na pierwszym elemencie tablicy.
Uruchom prawy wskaźnik na ostatnim elemencie tablicy.
Porównaj element wskazujący z lewym wskaźnikiem i jeśli jest mniejszy niż element pivot, przesuń lewy wskaźnik w prawo (dodaj 1 do lewego indeksu). Kontynuuj, aż lewy element boczny będzie większy lub równy elementowi obrotowemu.
Porównaj element wskazujący z prawym wskaźnikiem i jeśli jest większy niż element pivot, przesuń prawy wskaźnik w lewo (odejmij 1 do prawego indeksu). Kontynuuj, aż prawy element boczny będzie mniejszy lub równy elementowi obrotowemu.
Sprawdź, czy lewy wskaźnik jest mniejszy lub równy prawemu wskaźnikowi, a następnie zobacz elementy w lokalizacjach tych wskaźników.
Zwiększaj lewy wskaźnik i zmniejszaj prawy wskaźnik.
Jeśli indeks lewego wskaźnika jest nadal mniejszy niż indeks prawego wskaźnika, powtórz proces; w przeciwnym razie zwraca indeks lewego wskaźnika.

Zobaczmy więc te kroki na przykładzie. Rozważmy tablicę elementów, które musimy posortować, to [5,3,7,6,2,9].

Określ element Pivot

Ale zanim przejdziemy do sortowania szybkiego, wybranie elementu obrotowego odgrywa główną rolę. Jeśli wybierzesz pierwszy element jako element przestawny, będzie on miał gorszą wydajność w posortowanej tablicy. Dlatego zawsze dobrze jest wybrać środkowy element (długość tablicy podzielona przez 2) jako element przestawny i robimy to samo.

Oto kroki, aby wykonać szybkie sortowanie, które jest pokazane na przykładzie [5,3,7,6,2,9].

KROK 1: Określ pivot jako element środkowy. Tak więc 7 jest elementem obrotowym.

KROK 2: Rozpocznij lewy i prawy wskaźnik odpowiednio jako pierwszy i ostatni element tablicy. Zatem lewy wskaźnik wskazuje 5 pod indeksem 0, a prawy wskaźnik wskazuje 9 pod indeksem 5.

KROK 3: Porównaj element po lewej stronie wskaźnika z elementem obrotowym. Ponieważ 5 <6 przesuń wskaźnik w lewo w prawo do indeksu 1.

KROK 4: Teraz nadal 3 <6, więc przesuń lewy wskaźnik do jeszcze jednego indeksu w prawo. Więc teraz 7> 6 przestań zwiększać lewy wskaźnik, a teraz lewy wskaźnik znajduje się w indeksie 2.

KROK 5: Teraz porównaj wartość przy prawym wskaźniku z elementem pivot. Ponieważ 9> 6 przesuń prawy wskaźnik w lewo. Teraz, gdy 2 <6 przestaje przesuwać prawy wskaźnik.

KROK 6: Zamień ze sobą obie wartości obecne przy lewym i prawym wskaźniku.

KROK 7: Przesuń oba wskaźniki o jeden krok.

KROK 8: Ponieważ 6 = 6, przesuń wskaźniki do jeszcze jednego kroku i zatrzymaj się, gdy lewy wskaźnik przecina prawy wskaźnik i zwróć indeks lewego wskaźnika.

Tak więc, w oparciu o powyższe podejście, musimy napisać kod do zamiany elementów i partycjonowania tablicy, jak wspomniano w powyższych krokach.

Kod do zamiany dwóch liczb w JavaScript:

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

Kod do wykonania partycji, jak wspomniano w powyższych krokach:

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

Wykonaj operację rekurencyjną

Po wykonaniu powyższych kroków zostanie zwrócony indeks lewego wskaźnika i musimy go użyć do podzielenia tablicy i wykonania szybkiego sortowania na tej części. Dlatego nazywa się to algorytmem Podziel i zwyciężaj.

Tak więc sortowanie szybkie jest wykonywane, dopóki wszystkie elementy w lewej tablicy i prawej tablicy nie zostaną posortowane.

Uwaga: Szybkie sortowanie jest wykonywane na tej samej tablicy i nie są tworzone żadne nowe tablice.

Musimy więc wywołać tę partycję () wyjaśnioną powyżej i na tej podstawie podzielimy tablicę na części. Oto kod, w którym go używasz,

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

Kompletny kod szybkiego sortowania:

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]