Home / Algoritmalar / Selection Sort Algoritması – Örnekli Anlatım – C kodu

Selection Sort Algoritması – Örnekli Anlatım – C kodu

Selection Sort tıpkı Bubble Sort gibi lineer bir arama algoritmasıdır. Ancak mantığı daha farklıdır. İnsan aklının algoritmaya dönüşmüş halidir gibi de denebilir. Çünkü uygulaması ve anlaşılması çok kolaydır.

Her adımda dizideki en küçük eleman bulunur ve dizinin ilgili indisine yerleştirilir. İlgili indisi 0’dan başlar (0. indis) ve her adımda kendisinden sonraki sayılara bakılır ve en küçük eleman bulunur, yer değiştirme yapılır. (Swap) Eğer kendisinden daha küçüğü bulunmazsa yer değiştirme yapılmaz. Kendisine eşit bir sayı bulsak da swap yapmayız. Çünkü bu saçma olur. Swap sayısını ne kadar az tutarsak o kadar iyidir.

Selection Sort Algoritması Sözde (Pseudo) Kodu

Pseudo kodlar çok can sıkıcı şekilde yazıldığından daha anlaşılır bir şekilde yazacağım, nasıl olsa sözde kod değil mi 🙂

  1. ilk sayıdan başlayarak sayıyı elinde tut
  2. Elinde tuttuğun sayıların sağındaki sayılar içindeki en küçük sayıyı bul
  3. Elinde tuttuğun sayıyla en küçük sayıyı yer değiştir.
  4. Bir Sağdaki sayıya geç.

Bu kadar basit mi? evet bu kadar basit. Şimdi örnek üzerinde görelim.

Selection Sort Örneği

Tüm adımları anlatmak için yalnızca 5 tane sayıyla örnek verelim.

“32 16 44 8 5” sayılarımız olsun.

  1. adım: Anahtar değer i = 0 olmak üzere i. indisi anahtar değer olarak belirleriz. Diğer tüm sayılarla karşılaştırarak dizideki en küçük sayıyı bulur. En küçük sayı 5’tir. O halde 0. indisteki 32 sayısı ile 5 sayısı yer değiştirir. “5 16 44 8 32
  2. Adım: Anahtar değer i = 1 olur. Bu sefer 1. indisteki değer ile (16) diğer sayıları karşılaştırırız. En küçük değer 8’dir. 16 ile 8 yer değiştirir. “5 8 44 16 32
  3. Adım: Anahtar değer i = 2 olur. 2. indisteki değer ile (44) sağındaki sayılar karşılaştırılır. En küçük 16 olarak bulunur ve yer değiştirme yapılır.  “5 8 16 44 32
  4. Adım: Anahtar değer i = 3 olur. 3. indisteki değer ile (44) sağındaki sayılar (sayı) karşılaştırılır. 32 en küçüğüdür. Yer değiştirme yapılır. “5 8 16 32 44

Tahmin edeceğiniz üzere yukarıdaki işlemler yazılımla iç içe for döngüsü ile yapılır. Yukarıdaki her adım için for döngüsü gerekir. For döngüsü (eleman sayısı – 1) kere döner. İçteki karşılaştırmalar için de ayrı bir döngü gerekmektedir. Bu döngüde karşılaştırmalar her adımda sağındaki değerlerle karşılaştırılma yapılacağı için bir azalır. n(

Selection Sort – En iyi – En Kötü durum Analizi

Selection sort açıkçası pek de iyi bir sıralama algoritması değildir. Tüm durumlar için eşit performans gösterir. O(n²) durumu best case, avarage case ve worst case durumları için de eşittir. Ancak bilinmesi gerekir ki, Seçme Sıralama (Selection Sort) algoritması küçük listelerde uygulanabilecek ve gayet de hızlı çalışabilecek bir algoritmadır.

Peki ​n² nederen geliyor derseniz hemen hesaplayalım. Bu algoritma her döngüde bir karşılaştırma az yapmaktadır. Yani (n -1)+ (n -2) +  (n – 3) + … + 2 + 1 = n (n – 1) / 2 gelir.

Yukarıdaki formülden n²/2 – n/2 geldiğini görebiliriz. Bizim için önemli olan n² değeridir. Bu yüzden performansı rahatlıkla O(n²) olarak nitelendirebiliriz.

 

Selection Sort C Kodu


#include <stdio.h>
#define SIZE 10000

//Dizimizi oluşturduk ve 10.000 eleman alacak şekilde boyut verdik.
int myArray[SIZE - 1];

//fonksiyonuma dizi parametresi gönderiyoruz.
void selectionSort(int x[])
{
    //iç döngü ve dış döngü için değişkenker.
    int i, j;
    //Anahtar değer.
    int key;

    //Dış döngümüz başlıyor.
    for( i = 0; i < SIZE; i++)
    {
        //Her adımda anahtar değer belirliyoruz
        key = i;

        //Anahtar değerin sağındaki sayılarla karşılaştırma yapacağımız için i+1'den başlıyoruz.
        //Soldaki sayılar zaten sıralı hale geliyor.
        for(j = i + 1; j < SIZE; j++) { if(myArray[key] > myArray[j])
            {
                //dizide key değerinden daha küçük bir sayı bulduğumuzda key değerine atıyoruz.
                key = j;
            }

        }
        //Yer değiştirme fonksiyonumuzu çağırıyoruz. Dikkat edin parametre olarak sayıları değil, indisleri gönderiyoruz.
        swapf(i, key);
    }
}

//x ve y parametleri indistir, dizinin ilgili indislerindeki değerleri swap eden fonksiyon.
void swapf(int x, int y)
{
    int temp;
    temp = myArray[x];
    myArray[x] = myArray[y];
    myArray[y] = temp;

}


//Sıralanmış diziyi ekrana bastıran fonksiyon.
void printSorted()
{
    int i;
    for( i = 0; i < SIZE - 1; i++)
    {
        printf("%d\n", myArray[i]);
    }
}


//Bize random olarak 10.000 tane sayı oluşturan fonksiyon.
void init()
{
    int i;
    for( i = 0; i < SIZE - 1; i++)
    {
        myArray[i] = rand()%10000;
    }
}

//Bu da bizim main fonksiyonu, yalnızca oluşturduğumuz fonksiyonları çağırıyoruz.
int main()
{
    init();
    selectionSort(myArray);
    printSorted();
    return 0;
}

 

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir