Algorytm szybkiego sortowania 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.

Code:

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 oraz Scal sortowanie by Mozilla Firefox oraz 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.

1. Najpierw wybierz element, który ma zostać wywołany jako przestawny elementem.
2. 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.
3. 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

1. Najpierw znajdź "sworzeń" element tablicy.
2. Rozpocznij lewy wskaźnik od pierwszego elementu tablicy.
3. Uruchom prawy wskaźnik na ostatnim elemencie tablicy.
4. 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.
5. Porównaj element wskazujący prawym wskaźnikiem i jeśli jest większy od elementu obrotowego, przesuń prawy wskaźnik w lewo (subtract 1 do prawego indeksu). Kontynuuj tak, aż element po prawej stronie będzie mniejszy lub równy elementowi obrotowemu.
6. Sprawdź, czy lewy wskaźnik jest mniejszy lub równy prawemu wskaźnikowi, a następnie zamień elementy w lokalizacjach tych wskaźników.
7. Zwiększ lewy wskaźnik i zmniejsz prawy wskaźnik.
8. 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.

Tak więc, bazując na powyższym podejściu, musimy napisać kod do zamianyping elementy i partycjonowanie tablicy, jak opisano w powyższych krokach.

Code zamienić dwa numery JavaScenariusz

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

Code aby wykonać partycjonowanie 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).