Sortuj w dymku jest uważany za jeden z najprostszych algorytmów sortowania, który działa na zasadzie wielokrotnej zamiany sąsiednich elementów, jeśli są w złej kolejności. Dzięki algorytmowi sortowania bąbelkowego zobaczysz, że największy element (zakładając, że sortujemy od najmniejszego do największego) będzie „bąbelkowy” na górę listy lub tablicy.

Przykład:
Załóżmy, że chcemy posortować listę lub tablicę elementów w porządku rosnącym (od najmniejszego do największego): List = (3,1,2)

Ponieważ nie nastąpiła zamiana, oznacza to, że tablica jest już posortowane w kolejności rosnącej!

Najlepszy przypadek

Teraz wypróbujmy ten sam algorytm ponownie, ale tym razem używając najlepszego scenariusza, czyli gdy elementy są już posortowane w kolejności ( rosnąco) chcielibyśmy.

Ponieważ żadna zamiana nie nastąpiła, jesteśmy skończeni, a algorytm wykonał tylko 2 porównania i liczbę elementów w tablicy, którą nazwiemy n = 3. Więc widzimy, że dla n elementy w tym algorytmie w najlepszym przypadku przyjmie tylko n-1 porównań, n-1 = O (n)

Procedura lub algorytm, których użyliśmy jest poniżej:

Ten algorytm używa flagi aby stwierdzić, czy elementy zostały zamienione, czy nie , co pozwala algorytmowi sortowania bąbelkowego najlepszym przypadkiem być O (n) zamiast O (n²), jak w innej implementacji sortowania bąbelkowego.

Powyższy algorytm
Najgorszy przypadek = O (n²)
Najlepszy przypadek = O (n)

Przyjrzyjmy się innej implementacji algorytmu sortowania bąbelkowego:

BUBBLESORT(A)
1 for i = 1 to A.length - 1
2 for j = A.length downto i + 1
3 if A < A
4 exchange A with A

Powyższy algorytm
Najgorszy przypadek = O (n²)
Najlepszy przypadek = O (n²)

Najgorszy przypadek

Posortujmy tablicę lub listę = (3,2,1). Byłby to najgorszy przypadek, gdy lista jest w całkowicie odwrotnej kolejności niż chcemy (w porządku rosnącym) przy użyciu powyższego algorytmu.

Pierwszy przebieg:
(3,2,1) – > Porównanie elementów 3 & 2
(2,3 , 1) – > Zamień 3 & 2 od 2 < 3
( 2,3,1) – > Porównaj elementy 3 & 1
(2,1,3) – > Zamień 1 & 3 od 1 < 3

Drugi przebieg:
(2,1,3) – > Porównaj elementy 2 & 1
(1,2,3) – > Zamień 2 & 1 od 1 < 2
(1,2,3) – > Porównaj elementy 2 & 3
(1,2,3) – > PODMIANA nie jest wymagana od 2 < 3

Zakończyliśmy już przechodzenie przez obie pętle, więc tablica musi być posortowana w porządku rosnącym.

Zauważ, że w powyższym drugim przykładzie dokonaliśmy 4 porównań i liczba elementów w tablicy, którą nazwiemy „n” = 3, więc liczba wykonanych porównań to (n-1) ², a (n-1) ² = O (n²)

Również świetna książka przygotowująca Cię do wywiadów z zakresu kodowania / programowania nazywa się cracking the coding wywiad. Pomoże Ci to w zaznajomieniu się z algorytmami sortowania i rozwiązywaniu problemów, więc nie zapomnij go sprawdzić!

Dziękuję za przeczytanie tego artykułu Mam nadzieję, że jest on pomocny dla wszystkich! Kontynuuj naukę, a jeśli chcesz więcej filmów z analizą algorytmów, odwiedź i zasubskrybuj moje kanały YouTube (randerson112358 & compsci112358)

Sprawdź następujące więcej treści / filmów na temat analizy algorytmów i programowania:

Kanał YouTube:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:

Witryna:

Samouczki wideo dotyczące relacji nawrotów:

Samouczek wideo dotyczący analizy algorytmów:

Twitter: