Seçmeli sıralama

Seçmeli sıralama
Seçmeli sıralama algoritması
Sınıf	Sıralama algoritması
Veri yapısı	Dizi
Zaman karmaşıklığı	O(n²)
En iyi	Genellikle değil
Alan karmaşıklığı	toplamda О(n), ek alan O(1)

Seçmeli Sıralama, bilgisayar bilimlerinde kullanılan bir sıralama algoritmasıdır. Karmaşıklığı ${\displaystyle {\mathcal {O}}(n^{2})}$ olduğu için büyük listeler üzerinde kullanıldığında verim sağlamaz ve genel olarak benzeri olan eklemeli sıralamadan daha başarısızdır. Seçmeli sıralama yalın olduğu ve bazı durumlarda daha karmaşık olan algoritmalardan daha iyi sonuç verdiği için tercih edilebilir.

Algoritma aşağıdaki gibi çalışır:

1. Listedeki en küçük değerli öğeyi bul.
2. İlk konumdaki öğeyle bulunan en küçük değerli öğenin yerini değiştir.
3. Yukarıdaki adımları listenin ilk elemanından sonrası için (ikinci elemandan başlayarak) yinele.

A sıralanacak öğeler kümesi, n ise A'daki öğe sayısıdır. Dizi 0 numaralı dizinle başlamaktadır.

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]

int enkucuk, yedek;
for (int i = 0; i < dizi.Length-1; i++)
{
    enkucuk = i;
    for (int j = i+1; j < dizi.Length; j++)
    {
        if (dizi[j]<dizi[enkucuk])
        {
            enkucuk = j;
        }
    }

    if (enkucuk != i)
    {
        yedek = dizi[i];
        dizi[i] = dizi[enkucuk];
        dizi[enkucuk] = yedek;
    }               
}

public int[] secmeliSiralama(int[] dizi)
{
    int enkucuk, yedek;
    for (int i = 0; i < dizi.Length - 1; i++)
    {
         enkucuk = i;
         for (int j = i + 1; j < dizi.Length; j++)
             if (dizi[j] < dizi[enkucuk])
                 enkucuk = j;
         if (enkucuk != i)
         {
             yedek = dizi[i];
             dizi[i] = dizi[enkucuk];
             dizi[enkucuk] = yedek;
         }
     }
     return dizi;
}

Seçmeli 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. Seçmeli sıralama algoritması ${\textstyle n}$ elemanlı bir listede, en küçük eleman için ${\textstyle n-1}$ tane karşılaştırma yapar, ikinci en küçük eleman için ${\textstyle n-2}$ tane karşılaştırma yapar, diğer elemanlar için karşılaştırma sayısı ${\textstyle n-3}$, ${\textstyle n-4}$, ..., 2, 1, 0 şeklinde azalarak devam eder. Listedeki bütün elemanlar için yapılan karşılaştırmaların toplamı

$${\displaystyle (n-1)+(n-2)+(n-3)+(n-4)+...+2+1+0=n(n-1)/2}$$yapar.

Her bir eleman için bir kez yer değiştirme yapılır, tüm liste için toplam ${\textstyle n}$ tane yer değiştirme işlemi yapılır. Hesaplamalar sonucunda elde edilen

$${\displaystyle n+n(n-1)/2}$$değerlerinin asimptotik üst sınırı ${\textstyle O(n^{2})}$ değerini verir. Seçmeli sıralama algoritması listenin en küçük elemanının nerede olduğunu bilmediği ve her bir eleman için tüm elemanlarla karşılaştırma yaptığı için liste içindeki elemanların rastgele sıralanmış ya da eşit elemanlardan oluşmasını dikkate almaz, bu sebeple seçmeli sıralama algoritması her durumda ${\textstyle O(n^{2})}$ karmaşıklığıyla çalışır.^[1]

• Hızlı Sıralama
• Birleştirmeli Sıralama
• Kabarcık Sıralaması
• Kokteyl Sıralaması
• Tarak Sıralaması

• Analyze Selection Sort in an online JavaScript IDE
• Selection Sort in C++
• Selection Sort Demo7 Mart 2008 tarihinde Wayback Machine sitesinde arşivlendi.
• Selection Sort Demo^[]
• Selection Sort Demonstration
• Pointers to selection sort visualizations
• C++ Program - Selection Sort 12 Mart 2008 tarihinde Wayback Machine sitesinde arşivlendi.
• Selection sort explained and C++ source code
• A graphical demonstration and discussion of selection sort
• Selection sort in C