Sortowanie Bąbelkowe

Sortowanie bąbelkowe to jeden z najprostszych oraz najbardziej klasycznych algorytmów służących do porządkowania zbiorów danych. Jego intuicyjna koncepcja opiera się na porównywaniu sąsiadujących ze sobą elementów i odpowiednim ich przestawianiu. Działanie tego algorytmu można zobrazować poprzez uruchomienie serii iteracji przez listę wartości, gdzie w każdej iteracji porównywane są pary sąsiadujących elementów. Jeśli element znajdujący się na lewym miejscu jest większy od elementu po prawej, są one zamieniane miejscami.

Ten proces jest powtarzany w ramach wielu przejść, aż do momentu, gdy nie będzie potrzeby przeprowadzania kolejnych zamian, co oznacza, że lista została skutecznie uporządkowana. Kluczowym aspektem sortowania bąbelkowego jest jego prostota, a także fakt, że nie wymaga on dodatkowej pamięci, co sprawia, że jest algorytmem miejscowym. Pomimo tych zalet, algorytm cechuje się relatywnie niską efektywnością, szczególnie w przypadku dużych zbiorów danych, gdyż jego złożoność czasowa wynosi O(n^2) w najgorszym przypadku.

Sortowanie bąbelkowe jest często wykorzystywane w celach edukacyjnych, aby pomóc początkującym programistom zrozumieć podstawowe zasady działających algorytmów i procesów związanych z sortowaniem. Jego zastosowanie w praktyce jest jednak ograniczone, dlatego można zauważyć, że inne algorytmy sortowania, takie jak sortowanie przez wstawianie czy sortowanie szybkie, są bardziej efektywne i używane w realnych aplikacjach. Niemniej jednak, znajomość sortowania bąbelkowego jest wartościowa, gdyż stanowi solidną podstawę do nauki bardziej zaawansowanych koncepcji algorytmicznych.

Sortowanie bąbelkowe to najprostszy algorytm sortowania, który działa poprzez wielokrotne zamienianie sąsiednich elementów, jeśli są one w niewłaściwej kolejności.

Przykład:   Dane wejściowe – (75 21 54 32 88)

Pierwsze przejście:

(75 21 54 32 88) -> (21 75 54 32 88), tutaj algorytm porównuje pierwsze dwa elementy i zamienia jeśli 75 > 21.
(21 75 54 32 88) -> (21 54 75 32 88), Zamień jeśli 75 > 54
(21 54 75 32 88) -> (21 54 32 75 88), Zamień jeśli 75 > 32
(21 54 32 75 88) -> (21 54 32 75 88), Teraz, ponieważ te elementy są już w porządku 88 > 75, algorytm ich nie zamienia.

Drugie przejście:

(21 54 32 75 88) -> (21 54 32 75 88)
(21 54 32 75 88) -> (21 32 54 75 88), Zamień 54 > 32
(21 32 54 75 88) -> (21 32 54 75 88)
(21 32 54 75 88) -> (21 32 54 75 88)
Teraz tablica jest już posortowana, ale nasz algorytm nie wie, czy jest zakończony. Algorytm wymaga jednego całego przejścia bez wymiany, aby wiedzieć, że tablica jest posortowana.

Trzeci przebieg:

(21 32 54 75 88) -> (21 32 54 75 88)
(21 32 54 75 88) -> (21 32 54 75 88)
(21 32 54 75 88) -> (21 32 54 75 88)
(21 32 54 75 88) -> (21 32 54 75 88)

Implementacja w kodzie C#

public class Program
{
   public static void Main()
   {
       int[] arr = { 79, 86, 97, 43, 64, 25, 12, 22, 11, 7, 23, 5 };

	BubbleSort(arr);
	Console.WriteLine("Posortowana tablica");
	PrintArray(arr);
   }

   static void BubbleSort(int[] arr)
   {
      int n = arr.Length;

      for (int i = 0; i < n - 1; i++)
         for (int j = 0; j < n - i - 1; j++)
	    if (arr[j] > arr[j + 1])
	    {
	        int temp = arr[j];
		arr[j] = arr[j + 1];
		arr[j + 1] = temp;
	    }
   }

   static void PrintArray(int[] arr)
   {
      int n = arr.Length;

      for (int i = 0; i < n; ++i)
	 Console.Write(arr[i] + " ");

      Console.WriteLine();
   }
}

Wyjście:

5 7 11 12 22 23 25 43 64 79 86 97 

Kiedy możemy zastosować

Ze względu na swoją prostotę, sortowanie bąbelkowe jest często używane do wprowadzenia koncepcji algorytmu sortowania. W grafice komputerowej jest popularny ze względu na możliwość wykrywania bardzo małych błędów, takich jak zamiana tylko dwóch elementów w prawie posortowanych tablicach.

Cechy algorytmu sortowania bąbelkowego

Algorytm sortowania bąbelkowego, znany także jako bubble sort, jest jednym z najstarszych i najprostszych algorytmów sortujących. Jego główną cechą jest niezwykła prostota implementacji. Bubble sort działa na zasadzie porównywania par sąsiadujących elementów zbioru i wymiany ich miejscami, jeśli są ułożone w niewłaściwej kolejności. Proces ten powtarzany jest wielokrotnie, aż do momentu, gdy cała lista zostanie posortowana. Z tego względu algorytm ten jest nie tylko łatwy do zrozumienia, ale także do nauczenia się, co czyni go popularnym wśród początkujących programistów.

Jednakże, mimo swojej prostoty, algorytm sortowania bąbelkowego ma swoje wady. Przede wszystkim, nie jest on szczególnie efektywny w porównaniu do bardziej zaawansowanych algorytmów sortujących, takich jak quick sort czy merge sort. W najgorszym przypadku jego złożoność czasowa wynosi O(n²), co sprawia, że dla większych zbiorów danych jego wydajność spada. W przypadku niewielkich zbiorów danych bubble sort może być wystarczający, ale w miarę wzrostu ich rozmiaru lepiej jest rozważyć inne algorytmy.

Pomimo swoich ograniczeń, algorytm sortowania bąbelkowego znajduje zastosowanie w specyficznych sytuacjach, gdzie prostota kodu i czytelność mają kluczowe znaczenie. Idealnie nadaje się do środowisk edukacyjnych, w których zrozumienie zasady działania algorytmu sortowania jest pierwszym krokiem w nauce programowania. Dodatkowo, ze względu na swoją łatwość w implementacji, bubble sort może być używany w kontekstach, w których efektywność czasowa nie jest kluczowa, na przykład w zadaniach związanych z nauką lub wizualizacją algorytmów sortujących.