Algorytm szybkiego sortowania w JavaScenariusz
Co to jest szybkie sortowanie?
Szybkie sortowanie algorytm stosuje podejście Dziel i zwyciężaj. Dzieli elementy na mniejsze części na podstawie pewnego warunku i wykonuje operacje sortowania na tych podzielonych mniejszych częściach.
Algorytm Quick Sort jest jednym z najczęściej używanych i najpopularniejszych algorytmów w dowolnym języku programowania. Ale jeśli jesteś JavaJeśli jesteś programistą skryptów, to pewnie słyszałeś o sortować() który jest już dostępny w JavaSkrypt. Wtedy pewnie zastanawiałeś się, po co ten algorytm Quick Sort. Aby to zrozumieć, najpierw musimy wiedzieć, czym jest sortowanie i jakie jest domyślne sortowanie w JavaScenariusz.
Co to jest sortowanie?
Sortowanie to nic innego jak układanie elementów w kolejności, w jakiej chcemy. Być może spotkałeś się z tym w szkole lub na studiach. Podobnie jak układanie liczb od mniejszej do większej (rosnąco) lub od większej do mniejszej (malejąco) to to, co widzieliśmy do tej pory i nazywa się to sortowaniem.
Domyślne sortowanie JavaScenariusz
Jak wcześniej wspomniano, JavaSkrypt ma sortować(). Weźmy przykład z kilkoma tablicami elementów, takimi jak [5,3,7,6,2,9] i chcemy posortować te elementy tablicy w kolejności rosnącej. Zadzwoń sortować() on items array i sortuje elementy tablicy w kolejności rosnącej.
Kod:
var items = [5,3,7,6,2,9]; console.log(items.sort()); //prints [2, 3, 5, 6, 7, 9]
Jaki jest powód, aby wybrać sortowanie szybkie zamiast sortowania domyślnego () w JAVASCRIPT
Chociaż metoda sort() daje pożądany wynik, problem leży w sposobie sortowania elementów tablicy. Domyślne sortowanie() w JavaSkrypt używa sortowanie przez wstawianie by Silnik V8 Chrome i Scal sortowanie by Mozilla Firefox i Safari.
Ale w innych przypadkach nie jest to odpowiednie, jeśli chcesz posortować dużą liczbę elementów. Rozwiązaniem jest więc 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 teraz szczegółowo.
Co to jest sortowanie szybkie?
Następuje szybkie sortowanie Dziel i rządź algorytm. Dzieli elementy na mniejsze części na podstawie pewnego warunku i wykonuje operacje sortowania na tych podzielonych mniejszych częściach. Dlatego działa dobrze w przypadku dużych zestawów danych. Oto kroki, jak działa szybkie sortowanie w prostych słowach.
- Najpierw wybierz element, który ma zostać wywołany jako przestawny elementem.
- Następnie porównaj wszystkie elementy tablicy z wybranym elementem obrotowym i ułóż je w taki sposób, aby elementy mniejsze od elementu obrotowego znajdowały się po jego lewej stronie, a większe niż element obrotowy po jego prawej stronie.
- Na koniec wykonaj te same operacje na elementach po lewej i prawej stronie elementu obrotowego.
Oto podstawowy zarys szybkiego sortowania. Oto kroki, które należy wykonać jeden po drugim, aby wykonać szybkie sortowanie.
Jak działa QuickSort
- Najpierw znajdź "sworzeń" element tablicy.
- Rozpocznij lewy wskaźnik od pierwszego elementu tablicy.
- Uruchom prawy wskaźnik na ostatnim elemencie tablicy.
- Porównaj element wskazujący lewym wskaźnikiem i jeśli jest mniejszy od elementu obrotowego, to przesuń lewy wskaźnik w prawo (dodaj 1 do lewego indeksu). Kontynuuj tę czynność, aż lewy element będzie większy lub równy elementowi obrotowemu.
- Porównaj element wskazujący prawym wskaźnikiem i jeśli jest większy od elementu obrotowego, to przesuń prawy wskaźnik w lewo (odejmij 1 do prawego indeksu). Kontynuuj tę czynność, 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 zamień elementy w lokalizacjach tych wskaźników.
- Zwiększ lewy wskaźnik i zmniejsz prawy wskaźnik.
- Jeżeli indeks lewego wskaźnika jest w dalszym ciągu mniejszy niż indeks prawego wskaźnika, to powtórz proces; w przeciwnym razie zwróć 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 obrotowy
Zanim jednak przejdziemy do sortowania szybkiego, główną rolę odgrywa wybranie elementu przestawnego. Jeśli wybierzesz pierwszy element jako element przestawny, uzyskasz najgorszą wydajność w posortowanej tablicy. Dlatego zawsze zaleca się wybranie środkowego elementu (długość tablicy podzielona przez 2) jako elementu obrotowego i robimy to samo.
Oto kroki, jak wykonać szybkie sortowanie pokazane na przykładzie [5,3,7,6,2,9].
KROK 1: Określ oś jako element środkowy. 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 o indeksie 0, na który wskazuje prawy wskaźnik 9 w indeksie 5.
KROK 3: Porównaj element przy lewym wskaźniku z elementem obrotowym. Ponieważ 5 < 6 przesuwa lewy wskaźnik w prawo do indeksu 1.
KROK 4: Teraz nadal 3 <6, więc przesuń lewy wskaźnik o jeden indeks w prawo. Więc teraz 7 > 6 przestań zwiększać lewy wskaźnik i teraz lewy wskaźnik jest na indeksie 2.
KROK 5: Teraz porównaj wartość po prawej stronie z elementem obrotowym. Ponieważ 9 > 6 przesuń prawy wskaźnik w lewo. Teraz, gdy 2 < 6, przestań 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 więcej.
KROK 8: Ponieważ 6 = 6, przesuń wskaźniki o jeszcze jeden krok i zatrzymaj się, gdy lewy wskaźnik przetnie prawy wskaźnik i zwróć indeks lewego wskaźnika.
Zatem tutaj, 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 JavaScenariusz
function swap(items, leftIndex, rightIndex){ var temp = items[leftIndex]; items[leftIndex] = items[rightIndex]; items[rightIndex] = temp; }
Kod wykonujący partycję zgodnie z powyższymi krokami
function partition(items, left, right) { var pivot = items[Math.floor((right + left) / 2)], //middle element i = left, //left pointer j = right; //right pointer while (i <= j) { while (items[i] < pivot) { i++; } while (items[j] > pivot) { j--; } if (i <= j) { swap(items, i, j); //swap two elements i++; j--; } } return i; }
Wykonaj operację rekurencyjną
Po wykonaniu powyższych kroków zostanie zwrócony indeks lewego wskaźnika, którego musimy użyć do podzielenia tablicy i wykonania szybkiego sortowania tej części. Dlatego nazywa się to algorytmem „Dziel i zwyciężaj”.
Zatem sortowanie szybkie jest wykonywane do momentu, aż wszystkie elementy lewej i prawej tablicy zostaną posortowane.
Uwaga: Sortowanie szybkie odbywa się na tej samej tablicy i nie są przy tym tworzone żadne nowe tablice.
Więc musimy to nazwać przegroda() wyjaśniono powyżej i na tej podstawie dzielimy szyk 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 partition if (left < index - 1) { //more elements on the left side of the pivot quickSort(items, left, index - 1); } if (index < right) { //more elements on the right side of the pivot quickSort(items, index, right); } } return items; } // first call to quick sort var result = quickSort(items, 0, items.length - 1);
Wypełnij 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 element i = left, //left pointer j = right; //right pointer while (i <= j) { while (items[i] < pivot) { i++; } while (items[j] > pivot) { j--; } if (i <= j) { swap(items, i, j); //sawpping two elements i++; j--; } } return i; } function quickSort(items, left, right) { var index; if (items.length > 1) { index = partition(items, left, right); //index returned from partition if (left < index - 1) { //more elements on the left side of the pivot quickSort(items, left, index - 1); } if (index < right) { //more elements on the right side of the pivot quickSort(items, index, right); } } return items; } // first call to quick sort var sortedArray = quickSort(items, 0, items.length - 1); console.log(sortedArray); //prints [2,3,5,6,7,9]
UWAGA: Szybkie sortowanie działa ze złożonością czasową O(nlogn).