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 -

  1. Przykłady implementacji szybkiego sortowania w Javie
  2. Co to jest instrukcja Case w JavaScript?
  3. Właściwości sortowania scalonego w JavaScript
  4. Typy konstruktorów w JavaScript
  5. Sortuj sterty w Pythonie
  6. Zamiana w PHP
  7. Wstawianie Sortuj w JavaScript
  8. Funkcja rekurencyjna w C.
  9. Funkcja rekurencyjna w JavaScript