Seçmeli sıralamanın gerçekleşimini gösteren animasyon

Seçmeli arama (selection sort) her bir adım sonunda en küçük değerin en başa getirildiği sıralama algoritmasıdır. Dizi içinde dolaşılarak en küçük değer en başa getirilir. Dizideki eleman sayısı N kadar dolaşma işlemi tekrarlandığında dizi üzerinde sırama ede edilmiş olur.

Performans

Dizimiz üzerinde N tane eleman olsun. Bu durumda N kadar kontrol döngüsü çalıştırılır. Bu döngülerden 1. için N, 2.iin N-1 … N-1. için 2, N.için 1 adet kontrol yapılır. Yani bu sayıları dizi toplamı alırsak N x(N+1)/2 = (N²+N)/2 kontrol yapılmış olur. Bu da worst-case O (n²) karmaşıklık anlamına gelir.

Buradan seçmeli sıralamanın çok performanslı bir sıralama olmadığını görebiliriz. Bu yüzden büyük diziler yerine, minik dizilerde kulanılması daha mantıklı olacaktır. Tercih sebebi ise yazımı çok kolay bil algoritmaya sahip olmasıdır.

Adım-Adım Uygulama

Elimizde  5 1 4 2 8 değerlerine sahip 5 elemanlı bir dizi olsun. Bunu selection sort kullanarak adım adım sıralayalım:

İlk döngü:
( 5 1 4 2 8 )
( 5 1 4 2 8 )
( 5 1 4 2 8 )
( 5 1 4 2 8 )
( 5 1 4 2 8 ) –>( 1 5 4 2 8 )

İkinci döngü:
( 1 5 4 2 8 )
( 1 5 4 2 8 )
( 1 5 4 2 8 )
( 1 5 4 2 8 ) –> ( 1 2 4 5 8 )

Üçüncü Döngü:
( 1 2 4 5 8 )
( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Dördüncü Döngü:
( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Sıralı dizim : ( 1 2 4 5 8 )

Algoritma gösterilirken, altı çizili değerler o an en küçük kontrolünün yapıldığı değerlerdir. kırmızılarsa o ana kadar karşılaşılan en küçük değer indexini tutar.

Ayrıca dikat edilirse, 2.döngüde sıralı dizi elde edilmesine rağmen iki döngü daha yapılmıştır.Bu yüzden en iyi durumda bile (best-case) algoritma O (n²) zaman karmaşıklığında çalışmaktadır

Pseudocode

[Sıralı arama algoritmasına ait pseudocode]
    for i ← 0 to n-2 do
    min ← i
    for j ← (i + 1) to n-1 do
        if A[j] < A[min]
            min ← j
    swap A[i] and A[min]

Kaynaklar

http://en.wikipedia.org/wiki/Selection_sort