Sortowanie bąbelkowe (Bubble Sort)
Sortowanie bąbelkowe to najprostszy algorytm sortowania, który działa poprzez wielokrotne zamianie sąsiednich elementów, jeśli są one w niewłaściwej kolejności.
Przykład: Dane wejściowe – (5 1 4 2 8)
Pierwsze przejście:
(5 1 4 2 8) -> (1 5 4 2 8), tutaj algorytm porównuje pierwsze dwa elementy i zamienia jeśli 5 > 1.
(1 5 4 2 8) -> (1 4 5 2 8), Zamień jeśli 5 > 4
(1 4 5 2 8) -> (1 4 2 5 8), Zamień jeśli 5 > 2
(1 4 2 5 8) -> (1 4 2 5 8), Teraz, ponieważ te elementy są już w porządku 8 > 5, algorytm ich nie zamienia.
Drugie przejście:
(1 4 2 5 8) -> (1 4 2 5 8)
(1 4 2 5 8) -> (1 2 4 5 8), Zamień 4 > 2
(1 2 4 5 8) -> (1 2 4 5 8)
(1 2 4 5 8) -> (1 2 4 5 8)
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:
(1 2 4 5 8) -> (1 2 4 5 8)
(1 2 4 5 8) -> (1 2 4 5 8)
(1 2 4 5 8) -> (1 2 4 5 8)
(1 2 4 5 8) -> (1 2 4 5 8)
using System;
class Program
{
// Sortowania bąbelkowego (of Bubble Sort)
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();
}
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);
}
}