Bubble Sort w JavaScript

Załóżmy, że mamy nieprojektowaną tablicę i jesteśmy proszeni o uporządkowanie tablicy w dowolnej kolejności rosnącej lub malejącej. SORT BUBBLE jest jednym z najprostszych algorytmów sortowania, które porównuje dwa elementy obok siebie i sortuje tablicę. Dostępnych jest wiele algorytmów do sortowania tablic, takich jak sort. W tym artykule dowiemy się, jak korzystać z sortowania bańki, aby sortować elementy tablicy.

Działanie bańki

Załóżmy, że chcemy sortować naszą tablicę w kolejności rosnącej. Zaczyna działać, porównując lewy wskaźnik z prawym indeksem. Początkowo porównuje wartości dwóch pierwszych indeksów tablicy. Wartość indeksu 0. zostanie zastąpiona tylko wtedy, gdy pierwszy indeks niesie mniejszą wartość niż wartość indeksu 0. Następnie porówna wartość indeksu 1 z wartością indeksu 2 i tak dalej.

Załóżmy, że mamy następującą nieporadowaną tablicę:

Wiemy, że w tablicach indeksowanie rozpoczyna się od 0. Tak początkowo, „8” jest przechowywany na 0. indeksie, „3” jest przechowywany w pierwszym indeksie, „1” jest przechowywany w drugim indeksie i tak dalej. Teraz musimy sortować tę tablicę w kolejności rosnącej, jak pokazano w poniżej podanej tablicy:

Teraz wyjaśnimy działanie sortowania bańki krok po kroku.

Krok 1

Na początku indeks 0 przenosi 8, a indeks 1 przenosi 3. Ponieważ musimy sortować tablicę w kolejności rosnącej, wartość indeksu 0 zostanie zastąpiona wartością indeksu 1. Teraz zaktualizowana tablica będzie:

Teraz wartość indeksu 1 zostanie porównana z wartością indeksu 2. Wartość indeksu 1 wynosi 8, podczas gdy wartość indeksu 2 wynosi 1, która jest mniejsza niż 8, więc zostanie zamieniona, a tablica zostanie zmodyfikowana jako:

Teraz dokonamy porównania między indeksem 2 a indeksem 3. Wartość wskaźnika 2 wynosi 8, która jest większa niż wartość indeksu 3, która wynosi 2, więc wartości zostaną zamienione:

Teraz porównaj wartość indeksu 3 z wartością indeksu 4. W indeksie 3 Wartość wynosi 8, podczas gdy wartość indeksu 4 wynosi -1, co oznacza, że ​​obie te wartości zostaną zamienione:

Wreszcie wartość indeksu 4 zostanie porównana z wartością indeksu 5. Ponownie 8 jest większy niż 7, więc zostanie zastąpiony 7:

Teraz pierwsza iteracja jest zakończona, a „8” osiąga odpowiednią pozycję. Tak więc, w następnym kroku, porównania będą dokonywane do czwartego indeksu, ponieważ wartość ostatniego indeksu jest sortowana.

Krok 2:

Teraz zostaną porównane dwa pierwsze indeksy. Wartość pierwszego wskaźnika jest mniejsza niż wartość 0. wskaźnika, dlatego są zamienione wartości:

Następnie porównamy wartość pierwszego indeksu z wartością 2. indeksu. Tutaj 3 jest większe niż 2, więc zostanie zastąpiony 2:

Teraz porównamy wartość 2 i 3. indeksu I.mi. 3 (przy 2. indeksie) z wartością trzeciego indeksu, który wynosi -1. Wartości zostaną ponownie zamienione, ponieważ 3 jest większe niż -1:

Wartość 3. indeksu jest już niższa niż wartość 4. indeksu, więc pozostanie taka sama:

Teraz dwa ostatnie indeksy są sortowane, a wartości są prawidłowo umieszczone w czwartym i 5 indeksach.

Krok 3:

Teraz w tej iteracji początkowo wartość 0. wskaźnika zostanie porównana z wartością pierwszego indeksu. Tutaj wartość indeksu 0th wynosi 1, która jest już mniejsza niż wartość pierwszego indeksu, który wynosi 2. Tak więc wartości te pozostaną takie same.

Następnie porównaj następne dwa indeksy, tutaj wartość pierwszego indeksu jest większa niż wartość 2. indeksu, dlatego ich wartości zostaną zamienione:

Wartość 2. indeksu jest już mniejsza niż wartość 3 wskaźnika, dlatego ich wartości nie zostaną zamienione:

Krok 4:

Porównaj pierwsze dwa indeksy. Wartość indeksu 0. wynosi 1, która jest mniejsza niż wartość pierwszego indeksu (-1), więc zostanie zamieniony:

Następnie porównamy wartość pierwszego indeksu z wartością 2. indeksu. Są już posortowani, więc pozostaną takie same:

Wreszcie, nasza tablica jest sortowana w kolejności rosnącej.

Implementacja sortowania bańki w JavaScript

Ponieważ zrozumieliśmy, jak działa sortowanie bąbelków, teraz zaimplementujemy tę logikę w JavaScript za pomocą zagnieżdżonych pętli:

FunkctionBubblesort (ARY)
Leti, J;
varflag = false;
dla (i = 0; i
flaga = fałsz;
dla (j = 0; jary [j + 1])

vartemp = ary [j]
Ary [J] = Ary [J+1];
Ary [j+1] = temp;
flaga = prawda;


Jeśli(!flaga)

przerwa;


konsola.Log (Ary)

varary = [8, 3, 1, 2, -1, 7];
BubbleSort (ARY);

W powyższym kodzie utworzyliśmy tablicę o nazwie „Ary” i przypisał do tego niektóre dane. Następnie stworzyliśmy funkcję o nazwie BubbleSort i przekazaliśmy do niego tablicę. Zmienna o nazwie 'flaga' jest początkowo przypisywany wartością 'FAŁSZ'. Ta flaga zostanie użyta do weryfikacji, czy tablica jest całkowicie rozwiązana, czy nie. Następnie pętla jest inicjowana z 0 i będzie wykonywana, aż będzie mniejsza niż długość tablicy.

Zagnieżdżona w pętli jest wykorzystywana do narysowania porównania wartości we bieżącym wskaźniku z wartością w sąsiednim indeksie, wartości zostaną zamienione tylko wtedy, gdy wartość bieżącego wskaźnika jest wyższa niż wartość obecna w sąsiednim indeksie. Wartość flagi zostanie zastąpiona true, jeśli jakakolwiek wartość zostanie wymieniona podczas iteracji.

Po zakończeniu pętli wewnętrznej zmienna flagi jest sprawdzana. Jeśli zmienna flagi pozostaje fałszywa, oznacza to, że tablica jest już rozwiązana, a wewnętrzna pętla niczego nie zmieniła. W takim przypadku po prostu złam pętlę.

Wreszcie tablica jest przekazywana do BubbleSort () funkcjonować. Wyjście będzie:

Wniosek

SORT BUBBLE to podstawowy algorytm sortowania, który zamienia elementy obok siebie. W tym artykule przedstawiliśmy wszystkie podstawy i podstawową wiedzę potrzebną do zrozumienia pojęcia bańki w JavaScript. Począwszy od wprowadzenia opisującego, czym jest sortowanie bańki i jak to działa. Potem wzięliśmy przykład, aby zrozumieć koncepcję sortowania bańki. Ponadto wdrożyliśmy ten sam przykład w JavaScript i szczegółowo omówiliśmy jego działanie.