Bubble Sort w JavaScript

SORT BUBBLE jest jednym z najprostszych algorytmów sortowania, które porównuje dwa elementy obok siebie i sortuje tablicę w kolejności rosnącej lub w kolejności. 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.

Załóżmy, że mamy nieustanną tablicę i jesteśmy proszeni o sortowanie tablicy w dowolnej zamierzonej kolejności (i.mi. wznoszenie się lub zstępujące). Następnie mamy wiele algorytmów sortowania, aby sortować tę tablicę, taką jak sort. W tym celu możemy użyć dowolnego z tych algorytmów, ponieważ wszystkie algorytmy dają ten sam wynik. Ten artykuł zajmie się sortowaniem bańki z przykładami.

Działanie bańki

Zaczyna działać, porównując lewy wskaźnik z prawym indeksem. Początkowo porównuje dwa pierwsze wskaźniki tablicy (wartość umieszczona w indeksie 0 zostanie porównana z wartością umieszczoną w indeksie 1). 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. Więc początkowo w indeksie 0 wartość wynosi 8. Wartość indeksu 1 wynosi 3, a 1 jest umieszczany w indeksie 3 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. indeksu i.mi. 3 z wartością 3. indeksu, który wynosi -1. Wartości zostaną ponownie zamienione, ponieważ 3 jest większe niż -1:

Wartość trzeciego indeksu jest 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 0. wynosi 1, która jest 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 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, mniejsza niż wartość pierwszego indeksu, który wynosi 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:

funkcja bubbleSort (ARY)
Niech ja, j;
var flag = false;
dla (i = 0; i < ary.length; i++)

flaga = fałsz;
dla (j = 0; j ary [j + 1])

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


Jeśli(!flaga)

przerwa;


konsola.Log (Ary)

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

W powyższym kodzie utworzyliśmy tablicę o nazwie „ARY” i przypisaliśmy do niej niektóre dane. Następnie utworzyliśmy funkcję o nazwie BubbleSort i przekazaliśmy jej tablicę. Zmienna o nazwie „Flaga” jest początkowo przypisywana wartością „Fałsz”. Następnie pętla jest inicjowana z 0 i będzie wykonywana, aż będzie mniejsza niż długość tablicy. Zagnieżdżone w pętli są wykorzystywane 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 wartość zostanie zamieniona podczas iteracji. Wreszcie tablica jest wywoływana za pomocą funkcji bąbelkowej. 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.