Bubble Sort - Elemeli Sıralama

Bubble sort, eleman kümesindeki (array/dizi) elemanların ardışık olarak birbirleri ile karşılaştırılması ile gerçekleşen sıralama algoritmasıdır. Karşılaştırmalar ikişerli olarak yapılır ve büyük değer bir sonraki indise geçer. Yani ilk eleman ve ikinci eleman karşılaştırılır. Hemen ardından ikinci ve üçüncü eleman karşılaştırılır.

Ardışık kontrol yapılmasından dolayı bu algoritma baloncuğa benzetilmiştir  ve ismini  de buradan almıştır. ‘Bubble’ kelimesinin Türkçe karşılığı ise baloncuk/kabarcık olarak iki farklı şekilde çevrilmiştir.

En kötü durum performansı (worst-case performance) O(n²) ‘dir. En iyi durum performansı (best-case performance) O(n) ‘dir. Küçük problemlerde işlem, her bir eleman için 1 defa yapıldığından en iyi durum performansı doğrusaldır ve hızlı bir algoritmadır.  En kötü durum performansından bahsedecek olursak da N<1000 olduğu sürece hız anlamında sorun yaşatmayacaktır.

Bubble sort algoritmasını gösteren görsel animasyonu dikkatli biçimde izlerseniz çalışma prensibi hakkında biraz daha ön izlenim sahibi olacağınızı düşünüyorum. Bubble Sort algoritmasının dizi içerisinde sıralanması hakkında görsel sonuçlar veren bir animasyon daha paylaşmak istiyorum.

Hemen bir uygulama yapalım ve konuyu pekiştirelim. Not: Kopyala/Yapıştır yapmadan kendiniz yazmaya çalışırsanız daha sağlıklı olur.

C# Console Uygulaması

1 2 3 4 5 6 7 8 9 10 11 12 13 14

int[] Dizi = new int[] { 6, 5, 3, 1, 8, 7, 2, 4 }; int gecici; for (int i = 1; i < Dizi.Length; i++) {    for (int j = 0; j < Dizi.Length-i; j++)    {       if (Dizi[j]>Dizi[j+1])       {          gecici = Dizi[j+1];          Dizi[j+1] = Dizi[j];          Dizi[j] = gecici;       }    } }

C/C++ Kodu :

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18

void bubbleSort(int dizi[], int elemanSayisi) {      int temp;      int i, j;        for (i=1; i<elemanSayisi; i++)      {          for (j=0; j<elemanSayisi-i; j++)          {              if(dizi[j] > dizi[j+1])              {                         temp = dizi [j];                         dizi [j] = dizi [j+1];                         dizi [j+1] = temp;              }          }      } }

Java Kodu :

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16

public static void BubbleSort(int [] dizi) {     int temp;   // Yer değiştirmede kullanılacak geçici değişken     for (int i=1; i<dizi.length; i++)     {         for(int j=0; j<dizi.length-i; j++)         {             if (dizi[j] > dizi [j+1])             {                 temp = dizi [j];                 dizi [j] = dizi [j+1];                 dizi [j+1] = temp;             }//Önce gelen elaman bir sonrakinden büyükse ikisi yer değiştiriyor         }// Dizinin ardışık elamanlarını karşılaştırmak için kullandığımız döngü     }// Her karşılaştırmadan sonra yeniden kaldığımız yerden devam etmemizi sağlayan döngü }