Scal sortowanie w JavaScript - Różne rodzaje właściwości

Spisie treści:

Anonim

Wprowadzenie do sortowania korespondencji seryjnej w JavaScript

Algorytmy sortowania są bardzo ważne w informatyce. Wynikiem sortowania jest ułożenie elementów listy w określonej kolejności (rosnącej lub malejącej). Scal sortowanie w JavaScript jest jednym z najbardziej wydajnych dostępnych algorytmów sortowania, ponieważ opiera się na koncepcji dzielenia i zdobywania. Jak sama nazwa wskazuje, najpierw podziel większy problem na małe problemy niż rozwiąż mniejsze problemy, aby rozwiązać większy problem. Pod względem koncepcyjnym sortowanie metodą scalania jest kombinacją dwóch podstawowych algorytmów o nazwie MERGE i MERGE_SORT.

który działa w następujący sposób:

  1. Podziel nieposortowaną listę na n list podrzędnych zawierających pojedyncze elementy (n to całkowita liczba elementów na nieposortowanej liście).
  2. Wielokrotnie łącz podlisty w posortowane listy podrzędne, aż pojawi się tylko jedna posortowana lista.

Implementacja Merge Sort w JavaScript

Algorytm MERGE postępuje zgodnie z procedurą łączenia dwóch posortowanych list w jedną posortowaną listę.

Przykład: Załóżmy, że istnieją dwie listy, tj. Lista 1 (1, 5, 3) i Lista 2 (7, 2, 9).

1. Najpierw posortuj obie listy.

Teraz zobaczymy i zastosujemy na nim technikę E.

2. Następnie utworzymy nową listę o rozmiarze x + y, gdzie x to liczba elementów na liście 1, a y to liczba elementów na liście 2.

W naszym przypadku x = 3 iy = 3, więc x + y = 6.

3. Teraz mamy dwa wskaźniki.
Pierwszy wskaźnik wskazujący na pierwszą pozycję Listy 1 i Drugi wskaźnik wskazujący na pierwszej pozycji Listy 2.

4. Następnie porównamy wartość obu wskaźników. Wskaźnik o mniejszej wartości, skopiuj ten element do listy 3 i przesuń wskaźnik na prawo od listy o mniejszej wartości i wynikowej liście (tj. Liście 1 i liście 3)

5. Podobnie, wykonaj krok 4 raz za razem.

Dalsze przechodzenie…

Uwaga : Jeśli jedna z list (tj. Lista 1 lub lista 2) zostanie w pełni przemierzona, jak w przypadku, skopiuj całą zawartość innej listy ze wskaźnika do listy wyników (tj. Listy 3) w następujący sposób.

Pseudo kod

Function merge (sublist1, sublist2) (
Create var for result list
While sublist1 length > 0 and sublist2 length > 0
If sublist1(0) < sublist2(0) Copy the sublist1 pointer value to result list and Shift pointer of sublist1 to right
else
Copy the sublist2 pointer value to result list and Shift pointer of sublist2 to right
Return concat sublist1 or sublist2 (depending if node1 is empty or not)

Algorytm MERGE_SORT dzieli podaną nieposortowaną listę na minimalny rozmiar, a następnie wywołuje algorytm MERGE w celu połączenia listy w nową posortowaną listę.

Pseudo kod

function mergeSort(list) (
If list length < 2
Return list
Create var for middle index of list
Create var for left index of list
Create var for right index of list
Recursively call mergeSort function
)

Przykład

Tutaj śledzimy implementację sortowania korespondencji seryjnej z góry. Zaczyna się u góry i przechodzi w dół, z każdym zakrętem rekurencyjnym zadając to samo pytanie „Co należy zrobić, aby posortować listę?”, A odpowiedź brzmi: „Podziel listę na dwie części, wykonaj rekurencyjne połączenie i połącz wyniki ”.

Kod w JavaScript

// Split the list into halves and merge them recursively
function mergeSort (list) (
if (list.length < 2) (
return list;// return once we hit a list with a single element
)
var mid = Math.floor(list.length / 2);
var left = mergeSort(list.slice(0, mid));
var right = mergeSort(list.slice(mid));
return merge(left, right);
)
// compare the lists element by element and return the concatenated resultList
function merge (sublist1, sublist2) (
var resultList = ();
while (sublist1.length > 0 && sublist2.length > 0)
resultList.push(sublist1(0) < sublist2(0)? sublist1.shift() : sublist2.shift());
return resultList.concat(sublist1.length? sublist1 : sublist2);
)
const list = (6, 5, 3, 1, 8, 7, 2, 4, 2, 5, 1, 2, 3) console.log(mergeSort(list)) //( 1, 1, 2, 2, 2, 3, 3, 4, 5, 5, 6, 7, 8 )

Główna funkcja sortowania korespondencji seryjnej dzieli daną listę na mniejsze listy w każdej iteracji wywołania rekurencyjnego. Nie zapominaj, że rekurencja wymaga warunku podstawowego, aby uniknąć nieskończonej rekurencji. W naszym przypadku mamy:

if (list.length < 2) (
return list;// return once we hit a list with a single element
)

Po skonfigurowaniu warunku podstawowego dla rekurencji zidentyfikujemy środkowy indeks, aby podzielić daną listę na lewą i prawą listę podrzędną, jak widać powyżej na przykładowym diagramie. Następnie musimy scalić lewą listę podrzędną i prawą listę podrzędną, którą będziemy teraz przeglądać. W powyższej funkcji scalania musimy upewnić się, że sortujemy wszystkie elementy z lewej podlisty i prawej pod- lista. Sposób, w jaki to zrobimy, polega na użyciu pętli while. W pętli while porównamy jeden po drugim element z lewej listy podrzędnej i element z prawej listy podrzędnej. Możemy przesunąć mniejszą z dwóch na listę wyników i odpowiednio przesunąć kursor lewej podlisty i prawej podlisty. Wreszcie musimy połączyć listę wyników. To jest bardzo ważne! Jeśli nie zrobimy tego ostatniego kroku tutaj, na końcu będziemy mieć niepełną listę elementów, ponieważ warunek pętli while nie powiedzie się, gdy którykolwiek z dwóch wskaźników osiągnie koniec.

Wynik:

Właściwości sortowania scalonego

  1. Sortowanie po scaleniu jest stabilne, ponieważ ten sam element w tablicy zachowuje swoje pierwotne pozycje względem siebie.
  2. Sortowanie po scaleniu nie jest „na miejscu”, ponieważ podczas łączenia tworzy kopię całej listy. Z tego powodu złożoność przestrzeni (O (n)) tego algorytmu jest w rzeczywistości większa niż innych i nie należy jej stosować w złożonych problemach, w których przestrzeń jest premium.
  3. Ogólna złożoność czasowa sortowania korespondencji seryjnej wynosi O (nLogn). Jest bardziej wydajny, ponieważ w najgorszym przypadku środowisko wykonawcze to O (nlogn).

Wniosek

Scal sortowanie najlepiej, najgorszy i średni czas trwania sprawy są takie same, co czyni go bardziej wydajnym algorytmem. Działa szybciej niż inne techniki sortowania. Sortowanie według scalania można zastosować do plików o dowolnym rozmiarze. Jest wysoce paralelny dzięki zastosowaniu metody dziel i zwyciężaj. Aby rozwinąć solidne podstawy informatyki, zaleca się dokładne zrozumienie różnych algorytmów sortowania.

Polecany artykuł

Jest to przewodnik po sortowaniu korespondencji seryjnej w JavaScript. Tutaj omawiamy wprowadzenie do sortowania scalonego w JavaScript i implementację wraz z właściwościami. Możesz także przejrzeć nasze inne sugerowane artykuły, aby dowiedzieć się więcej -

  1. Funkcje matematyczne JavaScript
  2. Wprowadzenie do JavaScript
  3. Najlepsze ramy JavaScript
  4. Narzędzia JavaScript
  5. Top 6 algorytm sortowania w JavaScript