Wprowadzenie do szybkiego sortowania w JavaScript
Algorytm sortowania jest jedną z ważnych części struktury danych. Sortowanie to sposób porządkowania grupy przedmiotów w określony sposób. Ilekroć omawiamy algorytmy szybszego sortowania, w grę wchodzi szybkie sortowanie. Jest to jedna z najpopularniejszych technik sortowania pod względem czasu wykonania. Jest to stosunkowo lepszy wybór dowolnego programisty lub kodera ze względu na jego wydajność. Szybkie sortowanie działa na zasadzie dzielenia i podbijania. Oznacza to, że dzieli listę na dwie, a następnie dwie listy dalej dzieli się na 4 rekurencyjnie i tak dalej. W tym artykule zobaczymy, jak szybkie sortowanie działa również z przykładowym kodem. Zobaczymy też, jak to jest szybsze w porównaniu do innych różnych algorytmów sortowania. Zobaczymy różne elementy tego szybkiego algorytmu sortowania.
Operacje w szybkim sortowaniu
W skrypcie JavaScript szybkiego sortowania istnieją trzy główne operacje:
- Partycjonowanie listy: Dzielenie lub lista tablic za pomocą dzielenia i podbijania. To pierwszy krok w tej technice sortowania. W tym celu potrzebujemy elementu przestawnego (element środkowy lub blisko elementu środkowego).
- Zamiana pozycji: Jest to główny cel każdego algorytmu sortującego, aby dotrzeć do listy życzeń jako wynik. Jest to mechanizm sortowania, zastępujący wartości od jednego do drugiego. Na przykład A = 10; B = 20; Jeśli ktoś poprosi o zamianę, wartość A wyniesie 20, a B wyniesie 10.
- Operacja rekurencyjna: Odgrywa wielką rolę w Szybkim sortowaniu. Robienie rzeczy raz po raz nie jest tak bardzo możliwe i niezawodne bez funkcji rekurencyjnej. Jest to coś, co wywołuje sama funkcja (ta sama funkcja), aby wykonać zadanie. Odgrywa to wielką rolę, gdy wykonujemy dowolne zadanie ciągle z tym samym podejściem i w tym samym kontekście.
Porównanie algorytmu sortowania
Istnieje różnego rodzaju algorytm sortowania. Ponieważ JavaScript jest językiem programowania, obsługuje wszystkie algorytmy sortowania. Każdy algorytm sortowania ma swoje zalety i wady. Oto lista algorytmów sortowania i jego wydajności oraz innych macierzy:
Algorytm sortowania | Złożoność czasu | ||
Najlepszy przypadek | Średnia sprawa | Najgorszy przypadek | |
Sortowanie bąbelkowe | Ω (N) | Θ (N 2 ) | O (N 2 ) |
Sortuj wybór | Ω (N 2 ) | Θ (N 2 ) | O (N 2 ) |
Sortowanie przez wstawianie | Ω (N) | Θ (N 2 ) | O (N 2 ) |
Scal sortowanie | Ω (N log N) | Θ (N log N) | O (N log N) |
Sortuj sterty | Ω (N log N) | Θ (N log N) | O (N log N) |
Szybkie sortowanie | Ω (N log N) | Θ (N log N) | O (N 2 ) |
Jak widzimy na liście, SZYBKIE sortowanie jest szybsze niż Sortowanie bąbelkowe, Sortowanie selekcji, Sortowanie wstawiania.
Jak działa szybkie sortowanie w JavaScript?
Krok 1 : Aby uzyskać element Pivot - w dowolnym Dzieleniu i podboju wybór odpowiedniej Pivot odgrywa istotną rolę. Zwykle więc staramy się uzyskać środkowy element tablicy jako element przestawny. Jest to element, z którego dzielimy pojedynczą tablicę na pokój dwóch, aby przetworzyć sortowanie.
Krok 2 : Uruchom lewe wskaźniki jako pierwszy element tablicy wejściowej.
Krok 3 : Rozpocznij właściwe wskaźniki jako ostatni element tablicy wejściowej.
Krok 4 : Teraz porównujemy elementy przy lewym wskaźniku z wybranym elementem przestawnym i zamieniamy wartość, jeśli jest to wymagane, zgodnie z wymaganiami biznesowymi. Następnie porównujemy odpowiedni wskaźnik z elementem Pivot.
Krok 5: Przenieś oba do następnego. Wszystkie powyższe kroki następują wielokrotnie, stosując podejście rekurencyjne.
Przykład szybkiego sortowania w JavaScript
Jest to funkcja umożliwiająca szybkie sortowanie w JavaScript. W ten sposób przekażemy pełną listę tablic jako dane wejściowe i otrzymamy posortowaną tablicę jako dane wyjściowe.
Quick Sort in JavaScript
function quick_Sorting(array) (
if (array.length <= 1) (
return array; // if there is only one element then return the same
) else
(
var left = ();
var right = ();
var outputArray = ();
var pivot = array.pop();
var length = array.length;
for (var i = 0; i < length; i++) (
if (array(i) <= pivot) (
left.push(array(i));
) else (
right.push(array(i));
)
)
return outputArray.concat(quick_Sorting(left), pivot, quick_Sorting(right));
)
)
var myList = (3, 10, 2, 5, -5, 4, 7, 1);
alert("Input Array List: " + myList);
var sortedList = quick_Sorting(myList);
alert("Output Array List: " + sortedList);
Ze względu na jego oszałamiającą wydajność większość programistów wykorzystuje tę technikę sortowania do wdrożenia wbudowanej funkcji sortowania. W różnych językach programowania zastosowano wbudowane funkcje sortowania szybkiego sortowania. Istnieje wiele innych sposobów na napisanie programu do wykonywania operacji szybkiego sortowania, a wszystkie funkcje spotykają się w punkcie podziału i podboju. Tak więc, Dziel i rządź jest zasadą, którą można przetwarzać za pomocą szybkiego sortowania w JavaScript. Nie tylko w JavaScript, ale także we wszystkich językach programowania.
Wynik:
Polecane artykuły
Jest to przewodnik po Szybkim sortowaniu w JavaScript. Tutaj omawiamy, jak działa szybkie sortowanie w javascript, jego operacje i porównanie algorytmu sortowania wraz z przykładem. Możesz także przejrzeć następujące artykuły, aby dowiedzieć się więcej -
- Przykłady implementacji szybkiego sortowania w Javie
- Co to jest instrukcja Case w JavaScript?
- Właściwości sortowania scalonego w JavaScript
- Typy konstruktorów w JavaScript
- Sortuj sterty w Pythonie
- Zamiana w PHP
- Wstawianie Sortuj w JavaScript
- Funkcja rekurencyjna w C.
- Funkcja rekurencyjna w JavaScript