Sortowanie Bąbelkowe

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.