Bubble Sort Algoritması

Bubble sort algoritması, ardışık iki veriyi sıra ile birbiri ile karşılaştırır. Yani, önce ilk ikiyi veriyi karşılaştırır, sonra ikinci ve üçüncü elemanı karşılaştırır. Eğer önde olan eleman, önceki elemandan küçükse yer değiştirme yapılır. Aşağıda, bu algoritmanın çalışma mantığını gösteren ufak bir gif var

Gördüğünüz gibi gayet kolay. n eleman üzerinden n-1 kez geçiş yapar, dolayısı ile zaman karmaşıklığı;

n x (n-1) = O(n2)

olur. Hafızada kapladığı alan ise, sadece dizinin veri uzunluğu kadar kaplaması yeterli olduğu için O(n) olarak bulunabilir.

Peki, bu algoritmayı programlama dilinde nasıl ifade edebiliriz? İsterseniz, ilk olarak Java örneğini görelim.

package bubblesort; public class BubbleSort { public static void main(String[] args) { int dizi[] = {5, 3, 10, 20, 45, 1, 8}; System.out.println("Dizi:"); for (int i = 0; i < dizi.length; i++) { System.out.print(dizi[i] + " "); } bubbleSort(dizi); System.out.println("Sıralama:"); for (int i = 0; i < dizi.length; i++) { System.out.print(dizi[i] + " "); } } static void bubbleSort(int[] dizi) { int n = dizi.length; int temp = 0; for (int i = 0; i < n; i++) { for (int j = 1; j < (n - i); j++) { if (dizi[j - 1] > dizi[j]) { // Elemanlar yer değiştiriyor temp = dizi[j - 1]; dizi[j - 1] = dizi[j]; dizi[j] = temp; } } } } }
Aynı algoritmayı Python üzerinde görelim

# coding: utf-8 # coderistan # Bubble Sort def bubbleSort(dizi): for i in range(len(dizi)-1,0,-1): for k in range(i): if dizi[k]>dizi[k+1]: temp = dizi[k] dizi[k] = dizi[k+1] dizi[k+1] = temp dizi = [5, 3, 10, 20, 45, 1, 8] bubbleSort(dizi) print(dizi)
Burda, neden her seferinde dizinin sonuna kadar değilde, sadece n-i değerine kadar gittiğimizi şöyle açıklayalım. Gördüğünüz gibi, ilk sıralamayı yaptığımızda en büyük sayı dizinin sonuna kadar gider. Ve hep orda kalır. Yani artık o elemana tekrar uğramaya gerek yok. Her seferinde bir büyük eleman dizinin sonuna doğru ilerleyeceği için kontrol edeceğimiz eleman sayısı da n-i olur.

Evet, kısa bir şekilde anlatmaya çalıştık. Umarım anlaşılır olmuştur. Görüşmek üzere :)