Sortowanie insercji w JavaScript

SORTESERTING jest prostym i stabilnym algorytmem sortowania, który wybiera element z nieprojektowanej listy i wprowadza go do posortowanej listy w odpowiedniej pozycji. Podczas gdy termin stabilny algorytm odnosi się do scenariusza, w którym dwa równoważne elementy pojawiają się identycznie, wówczas stabilny algorytm utrzymuje elementy na ich względnych pozycjach po zakończeniu algorytmu sortowania.

Algorytm sortowania wstawiania jest bardzo pomocny w tych przypadkach, w których mamy mniejszą liczbę elementów na liście lub gdzie większość listy jest już sortowana i mniej elementów jest zgubionych.

Jak działa sortowanie insercji

Rozważmy przykład, aby lepiej zrozumieć logikę za wstawieniem. Załóżmy, że mamy nieposortowaną tablicę 6 elementów i musimy je sortować za pomocą sortowania wstawiania:

Teraz, aby uporządkować powyższą tablicę, iterujemy tablicę od indeksu 1 do ostatniego indeksu. Początkowo zakładamy, że 0. wskaźnik tablicy jest sortowany, a następnie dokonamy porównania bieżącego elementu z jego poprzednim elementem. Jeśli bieżący element jest mniejszy niż poprzedni element, zamienimy ich pozycje.

Pierwszy krok
W pierwszym etapie porównamy indeks 1 z indeksem 0, wartość pierwszego indeksu „47” jest większa niż wartość indeksu 0., więc nie będzie żadnej zmiany w pierwszym kroku (elementy nie zamieniłyby):

Drugi krok
Teraz, w drugim etapie, założymy, że pierwsze dwa elementy są sortowane, więc kursor będzie na indeksie 2 i porównamy indeks 2 z jego wcześniejszymi elementami:

Ponieważ „25” jest mniejsze niż „47”, zamień „25” i „47”. Następnie „25” jest również porównywane z wartością indeksu 0. „25” jest większe niż „15”, więc nie zostałby zamieniony.

Tablica po drugim kroku zostanie zaktualizowana jako:

Trzeci krok
Tutaj w trzecim etapie rozważamy pierwsze trzy wartości, a kursor będzie na trzecim indeksie. Porównamy więc trzeci indeks z jego wcześniejszymi wartościami:

W indeksie 3 „55” jest porównywana z każdym elementem jeden po jednym, ale jest większy niż wszystkie jego poprzednie elementy, więc nie będzie żadnych zmian w pozycji elementów tablicy.

Czwarty krok
Teraz jesteśmy na indeksie 4, gdzie mamy wartość „20” i musimy porównać ją ze wszystkimi wcześniejszymi elementami tablicy:

Ponieważ „20” jest mniej niż „25”, „47” i „55”, więc zostaną wstawione do pierwszego indeksu, a „25”, „47” i „55” zostaną przeniesione na prawą stronę o jeden indeks jeden indeks (I+1 indeks) z ich bieżących indeksów.

Zaktualizowana tablica będzie:

Piąty krok
Teraz jesteśmy w indeksie 5, w którym bieżąca wartość wynosi „10”, która jest najmniejsza spośród wszystkich wartości tablicy, więc zostanie ona wstawiona na indeksie 0.

W ten sposób cała tablica zostanie sortowana za pomocą sortowania insercji:

Jak to robimy z koncepcyjną częścią sortowania insercji, teraz zaimplementujemy tę koncepcję w JavaScript.

Wdrożenie sortowania insercji w JavaScript

Kod wdrażania sortowania wstawiania w JavaScript jest następujący:

funkcja insertion_sort (input_array, array_length)

Niech i, Pivot_Value, J;
dla (i = 1; i = 0 && input_array [j]> Pivot_Value)

input_array [j + 1] = input_array [j];
j = j - 1;

Input_Array [J + 1] = Pivot_Value;

return input_array;

Let Input_Array = [15 47,25,55,20,10];
Niech array_length = input_array.długość;
insertion_sort (input_array, array_length);
konsola.log („Final Sorted Array:”, Input_Array);

W powyższym kodzie stworzyliśmy funkcję „sortowanie przez wstawianie”I przekazał mu tablicę wejściową i długość tablicy. Następnie iterowaliśmy pętlę do długości tablicy.

Wewnątrz pętli wybraliśmy 'PIVOT_VALUE = Input_Array [i]„Jako wartość obrotowa do porównania bieżącego elementu z jego wcześniejszymi elementami i zestawem”J = i-1”, Który reprezentuje ostatni element naszej posortowanej tablicy.

Tutaj, w każdej iteracji, bieżący element jest przypisany do wartości obrotu, a wartość obrotu będzie uważana za pierwszy element nieporozumienia na każdym kroku.

Korzystamy z pętli do sortowania elementów tablicy, tutaj w tej pętli porównujemy bieżący element z jego wcześniejszymi elementami. Jeśli bieżący element jest mniejszy niż którykolwiek z poprzednich elementów, i znaleźliśmy odpowiednią pozycję do włożenia tego elementu do posortowanej tablicy, wkładamy ten element w odpowiedniej pozycji. A całe zjawisko powtarza się dla każdego kroku, aż tablica zostanie całkowicie posortowana.

Wyjście

Wreszcie nazywamy „sortowanie przez wstawianie”Funkcjonuj i wydrukuj posortowaną tablicę w konsoli przeglądarki za pomocą„konsola.dziennik" metoda. Wyjście algorytmu sortowania wstawienia będzie:

Wniosek

SORTESERTION to algorytm sortowania, który sortuje jeden element na raz. Wkłada element w odpowiedniej pozycji jeden po drugim, aby utworzyć jedną sortowaną tablicę. Zapewnia wydajne wyniki, jeśli liczba elementów macierzy jest niewielka, a większość elementów tablicy jest już sortowana.

W tym artykule rozważyliśmy przykład ustalenia logiki sortowania wstawienia, omówiliśmy działanie algorytmu sortowania wstawiania w odniesieniu do każdego kroku i przedstawili zaktualizowaną tablicę po każdym kroku. I wreszcie, kiedy zauważyliśmy pomysł sortowania wstawienia, wdrożyliśmy go w JavaScript.