Sıralama Algoritmaları

Sıralama algoritmaları bilgisayar programcılığı açısından oldukça önemli bir konudur. Her ne kadar gelişmiş programlama dillerinde dizi elemanlarını sıralayan hazır fonksiyonlar olsada programcılığa yeni başlayanlar için programlama mantığının kavranması için önemli konulardır. Temel sıralama yöntemleri aşağıda kısaca anlatılmıştır.

Kabarcık Sıralama (Bubble Sort)

Hafıza bloğunda yada bir dizide ard arda gelen iki elemanın birbirileri ile karşılaştırılması ile yapılır. Artan yada azalan sıralama isteğine göre kodda "<" veya ">" operatörü kullanılır. Yavaş bir sıralama operatörüdür.

Ancak bazı durumlarda dizinin sıralanması yukarıda geçen sayı (n elemanlı bir dizi için n geçiş) kadar tekrarı gerektirmez. Bu durum sadece dizi tersten sıralıysa gerekir. Ayrıca dizi zaten sıralı ise ilk geçişten sonra sıralamanın durmasını bekleriz.

Bir diğer iyileştirme ise yukarıdaki örneğe dikkatle bakıldığında fark edilebilir. Kabarcık sıralamasında dizi üzerindeki her geçişten sonra dizinin en büyük elemanı dizinin sonuna atılmaktadır. Örneğin ilk geçişten sonra en büyük eleman, 2. geçişten sonra en büyük iki eleman 20. geçişten sonra en büyük 20 eleman gibi dizinin sonunda yerleşmekte ve bir daha hiç değişmemektedir. bu durumda örneğin 20. geçişte son 20 elemana bakmanın bir anlamı yoktur. Bu iyileştirme (optmisation) ile de hız kazanmak mümkündür. Bu sıralama yöntemi diğer yöntemlere göre biraz yavaştır, çok büyük dizilerde bu hız farkı hissedilebilir.

Bubble Sort

Beş elemanlı (random sayılardan oluşan) bir dizi için C++ kodları aşağıda verilmiştir.

 #include <iostream>  
 #include <ctime>  
 #include <cstdlib>  
 using namespace std;  
 int main() {  
      int dizi[5];  
      int i,j,temp;  
      srand(time(0));  
      for(i=0;i<5;i++)  
      {  
           dizi[i]=rand()%100+1;  
           printf("%d - ",dizi[i]);       
      }  
      for (i=0; i<5; i++)  
    {  
      for (j=0; j<5-i; j++)  
      {  
        if(dizi[j] > dizi[j+1])  
        {  
             temp = dizi [j];  
             dizi [j] = dizi [j+1];  
             dizi [j+1] = temp;  
        }  
      }  
    }  
      printf("\n");  
      for(i=0;i<5;i++) printf("%d - ",dizi[i]);  
 }  

Seçmeli Sıralama (Selecton Sort)

Listedeki en küçük veya en büyük elemanın seçilerek, diğer elemanların yer değiştirmesi prensibi ile çalışan algoritmadır. İşlem başlangıcında belirlenen en küçük sayıyı tutan değişkene dizinin ilk elemanı atanır ve dizi elemanları ile tek kıyaslanır.  Daha küçüğü bulunursa ordaki indis ile yer değiştirilir.

 Bubble sorttan daha hızlıdır fakat çok elemanlı listelerde efektif değildir. Çalışma prensibi aşağıdaki grafikteki gibidir.

Selection Sort

 Beş elemanlı (random sayılardan oluşan) bir dizi için C++ kodları aşağıda verilmiştir.

 #include <iostream>  
 #include <ctime>  
 #include <cstdlib>  
 using namespace std;  
 int main() {  
      int dizi[5];  
      int i,j,enkucuk,enbuyuk,yedek;  
      srand(time(0));  
      for(i=0;i<5;i++)  
      {  
           dizi[i]=rand()%100+1;  
           printf("%d - ",dizi[i]);       
      }  
      for (int i = 0; i < 5-1; i++)  
 {  
   enkucuk = i;  
   for (int j = i+1; j < 5; j++)  
   {  
     if (dizi[j]<dizi[enkucuk])  
     {  
       enkucuk = j;  
     }  
   }  
   if (enkucuk != i)  
   {  
     yedek = dizi[i];  
     dizi[i] = dizi[enkucuk];  
     dizi[enkucuk] = yedek;  
   }          
 }  
      printf("\n");  
      for(i=0;i<5;i++) printf("%d - ",dizi[i]);  
 }  

Eklemeli Sıralama (Insertion Sort)

Her adımda dizi elemanlarını sıralayan bir algoritmadır. Eklemeli sıralama algoritmasının zaman karmaşıklığı hesaplanırken, yapılan karşılaştırmalar ve yer değiştirmeler dikkate alınır. Eklemeli sıralama algoritması ${\textstyle n}$n elemanlı bir listede, ikinci eleman için en fazla 1 karşılaştırma ve 1 yer değiştirme yapar, üçüncü eleman için 2 karşılaştırma ve 2 yer değiştirme, dördüncü eleman için 3 karşılaştırma ve 3 yer değiştirme yapar. Kabarcık ve Seçmeli sıralamaya göre daha hızlıdır. Çalışma şekli aşağıdaki grafikteki gibidir.

Insertion Sort

Beş elemanlı (random sayılardan oluşan) bir dizi için C++ kodları aşağıda verilmiştir.

 #include <iostream>  
 #include <ctime>  
 #include <cstdlib>  
 using namespace std;  
 int main() {  
      int dizi[5];  
      int i,j,yedek;  
      srand(time(0));  
      for(i=0;i<5;i++)  
      {  
           dizi[i]=rand()%100+1;  
           printf("%d - ",dizi[i]);       
      }  
      for (int i = 0; i < 5; i++){  
           j = i;  
           while (j > 0 && dizi[j] < dizi[j-1]){  
                 yedek = dizi[j];  
                 dizi[j] = dizi[j-1];  
                 dizi[j-1] = yedek;  
                 j--;  
                 }  
           }  
      printf("\n");       
      for(i=0;i<5;i++)  
      {  
           printf("%d - ",dizi[i]);       
      }  
 }