Bubble Sort

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);
	}
}

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *