DAA - Kabarcık Sıralama

Bubble Sort, gerekirse bitişik öğeleri tekrar tekrar değiştirerek çalışan temel bir sıralama algoritmasıdır. Değişim gerekmediğinde, dosya sıralanır.

Bu, tüm sıralama algoritmaları arasında en basit tekniktir.

Algorithm: Sequential-Bubble-Sort (A) 
fori← 1 to length [A] do 
for j ← length [A] down-to i +1 do 
   if A[A] < A[j - 1] then 
      Exchange A[j] ↔ A[j-1]

Uygulama

voidbubbleSort(int numbers[], intarray_size) { 
   inti, j, temp; 
   for (i = (array_size - 1); i >= 0; i--) 
   for (j = 1; j <= i; j++) 
      if (numbers[j - 1] > numbers[j]) { 
         temp = numbers[j-1]; 
         numbers[j - 1] = numbers[j]; 
         numbers[j] = temp; 
      } 
}

Analiz

Burada, karşılaştırma sayısı

1 + 2 + 3 +...+ (n - 1) = n(n - 1)/2 = O(n²)

Açıkça, grafik, n² kabarcık türünün doğası.

Bu algoritmada, karşılaştırma sayısı veri setinden bağımsızdır, yani sağlanan giriş elemanlarının sıralı sırada mı yoksa ters sırada mı yoksa rastgele mi olduğu.

Bellek gereksinimi

Yukarıda belirtilen algoritmadan, balon sıralamanın fazladan bellek gerektirmediği açıktır.

Misal

Unsorted list:

5 2 1 4 3 7 6

1 ^st yineleme:

5 > 2 swap	2 5 1 4 3 7 6
5 > 1 swap	2 1 5 4 3 7 6
5 > 4 swap	2 1 4 5 3 7 6
5 > 3 swap	2 1 4 3 5 7 6
5 < 7 no swap	2 1 4 3 5 7 6
7 > 6 swap	2 1 4 3 5 6 7

2 ^nd yineleme:

2 > 1 swap	1 2 4 3 5 6 7
2 < 4 no swap	1 2 4 3 5 6 7
4 > 3 swap	1 2 3 4 5 6 7
4 < 5 no swap	1 2 3 4 5 6 7
5 < 6 no swap	1 2 3 4 5 6 7

3'te herhangi bir değişiklik yoktur ^rd , 4 ^th , 5 ^inci ve 6 ^inci yineleme.

En sonunda,

the sorted list is

1 2 3 4 5 6 7