Selection Sort Algoritması

Selection Sort Algoritması Açıklaması

Selection Sort, bir dizinin sıralanmamış kısmından en küçük elemanı tekrar tekrar bularak başlangıca yerleştiren basit bir sıralama algoritmasıdır. Her geçişte algoritma bir sonraki doğru elemanı seçtiği için Selection Sort (Seçmeli Sıralama) olarak adlandırılır.

Selection Sort, büyük veri kümeleri için verimli olmasa da, sıralama algoritmalarının nasıl çalıştığını öğrenmek için çok faydalıdır. Yeni başlayanların karşılaştırma tabanlı sıralama, dizi geçişi, eleman değiştirme (swapping), yerinde algoritmalar ve zaman karmaşıklığı analizini anlamalarına yardımcı olur.

Giriş

Sıralama, bilgisayar bilimleri ve programlamanın en önemli konularından biridir. Birçok gerçek uygulama, verileri verimli bir şekilde arama, görüntüleme, filtreleme, sıralama veya işleme tabi tutmadan önce sıralanmış olmasını gerektirir.

Merge Sort, Quick Sort veya Heap Sort gibi gelişmiş sıralama algoritmalarını öğrenmeden önce, yeni başlayanlar genellikle Bubble Sort, Selection Sort ve Insertion Sort gibi daha basit algoritmalarla başlarlar. Bu algoritmalar, mantıkları adım adım manuel olarak izlenebildiği için anlaşılması daha kolaydır.

Selection Sort, fikri doğrudan olduğu için özellikle faydalıdır: en küçük değeri bul, doğru konuma taşı ve ardından kalan sıralanmamış elemanlar için aynı süreci tekrarla.

Selection Sort Nedir?

Selection Sort, karşılaştırma tabanlı bir sıralama algoritmasıdır. Diziyi iki bölüme ayırır: sıralanmış kısım ve sıralanmamış kısım.

Başlangıçta sıralanmış kısım boştur ve tüm dizi sıralanmamış kabul edilir. Her geçişte, algoritma en küçük elemanı bulmak için sıralanmamış kısmı tarar. Bulduktan sonra, algoritma bu elemanı sıralanmamış kısmın ilk elemanıyla yer değiştirir (swap).

Her geçişten sonra, bir eleman daha nihai sıralanmış konumuna yerleştirilir.

Selection Sort şu şekilde özetlenebilir:

• Dizinin ilk konumundan başlayın.

• Geçerli konumun en küçük değeri içerdiğini varsayın.

• Gerçek en küçük değeri bulmak için kalan elemanları tarayın.

• En küçük değeri geçerli konumla yer değiştirin.

• Bir sonraki konuma geçin ve süreci tekrarlayın.

Selection Sort Nasıl Çalışır?

Selection Sort, doğru elemanı doğru konuma adım adım yerleştirerek çalışır. Yan yana elemanları tekrar tekrar yer değiştiren Bubble Sort'un aksine, Selection Sort önce minimum elemanı arar ve her geçişte yalnızca bir yer değiştirme işlemi yapar.

Artan sırada sıralanacak bir dizi için, Selection Sort en küçük elemanı bulur ve 0. dizine yerleştirir. Ardından ikinci en küçük elemanı bulur ve 1. dizine yerleştirir. Daha sonra üçüncü en küçük elemanı bulur ve 2. dizine yerleştirir. Bu işlem dizi sıralanana kadar devam eder.

Önemli fikir şudur ki, her geçişten sonra dizinin sol tarafı sıralanmış hale gelir ve tekrar değiştirilmemelidir.

Selection Sort Algoritması Adımları

Selection Sort'un temel adımları basittir:

1. Diziyi ilk elemandan sondan bir önceki elemana kadar döngüye alın.

2. Geçerli dizini minimum elemanın dizini olarak ayarlayın.

3. Dizinin kalan sıralanmamış kısmını döngüye alın.

4. Daha küçük bir eleman bulunursa, minimum dizini güncelleyin.

5. Sıralanmamış kısmı taradıktan sonra, geçerli elemanı minimum elemanla yer değiştirin.

6. Tüm elemanlar doğru konumlarına gelene kadar tekrarlayın.

Bu süreç, dizinin sıralanmış kısmını soldan sağa doğru kademeli olarak oluşturur.

Manuel Çalıştırma Örneği

Bu diziyi kullanarak Selection Sort'u manuel olarak izleyelim:

[29, 10, 14, 37, 13]

Amaç, diziyi artan sırada sıralamaktır.

Başlangıç Dizisi

[29, 10, 14, 37, 13]

Bu noktada, dizinin tamamı sıralanmamıştır.

Geçiş 1

0. dizinden başlıyoruz. Mevcut değer 29. 29'un en küçük değer olduğunu varsayıyoruz, sonra kalan elemanları tarıyoruz.

• 29'u 10 ile karşılaştırın. 10 daha küçük olduğu için minimum 10 olur.

• 10'u 14 ile karşılaştırın. Minimum 10 olarak kalır.

• 10'u 37 ile karşılaştırın. Minimum 10 olarak kalır.

• 10'u 13 ile karşılaştırın. Minimum 10 olarak kalır.

Sıralanmamış kısımdaki en küçük değer 10'dur. 29 ve 10'u yer değiştiriyoruz.

Before swap: [29, 10, 14, 37, 13]
After swap:  [10, 29, 14, 37, 13]

Şimdi 10 doğru nihai konumunda.

Geçiş 2

Şimdi 1. dizine geçiyoruz. Sıralanmış kısım:

[10]

Sıralanmamış kısım:

[29, 14, 37, 13]

Sıralanmamış kısımdaki en küçük değerin 29 olduğunu varsayıyoruz, sonra kalan elemanları tarıyoruz.

• 29'u 14 ile karşılaştırın. 14 daha küçük olduğu için minimum 14 olur.

• 14'ü 37 ile karşılaştırın. Minimum 14 olarak kalır.

• 14'ü 13 ile karşılaştırın. 13 daha küçük olduğu için minimum 13 olur.

Sıralanmamış kısımdaki en küçük değer 13'tür. 29 ve 13'ü yer değiştiriyoruz.

Before swap: [10, 29, 14, 37, 13]
After swap:  [10, 13, 14, 37, 29]

Şimdi 10 ve 13 doğru konumlarında.

Geçiş 3

Sıralanmış kısım:

[10, 13]

Sıralanmamış kısım:

[14, 37, 29]

2. dizinden başlıyoruz. Mevcut değer 14. Sıralanmamış kısımdaki en küçük değerin 14 olduğunu varsayıyoruz.

• 14'ü 37 ile karşılaştırın. Minimum 14 olarak kalır.

• 14'ü 29 ile karşılaştırın. Minimum 14 olarak kalır.

En küçük değer zaten doğru konumda, bu yüzden gerçek bir yer değiştirme (swap) gerekmiyor.

Array remains: [10, 13, 14, 37, 29]

Şimdi 10, 13 ve 14 sıralandı.

Geçiş 4

Sıralanmış kısım:

[10, 13, 14]

Sıralanmamış kısım:

[37, 29]

3. dizinden başlıyoruz. Mevcut değer 37. Bunu kalan değer 29 ile karşılaştırıyoruz.

• 37'yi 29 ile karşılaştırın. 29 daha küçük olduğu için minimum 29 olur.

37 ve 29'u yer değiştiriyoruz.

Before swap: [10, 13, 14, 37, 29]
After swap:  [10, 13, 14, 29, 37]

Dizi şimdi sıralandı.

Nihai Sıralanmış Dizi

[10, 13, 14, 29, 37]

Bu manuel çalıştırma, Selection Sort'un ana davranışını göstermektedir. Her geçişte, algoritma sıralanmamış kısımdan en küçük elemanı seçer ve doğru konuma taşır.

Selection Sort Sözde Kodu

Sözde kod, belirli bir programlama diline odaklanmadan algoritmayı açıklamaya yardımcı olur.

selectionSort(array):
    n = length(array)

    for i from 0 to n - 2:
        minIndex = i

        for j from i + 1 to n - 1:
            if array[j] < array[minIndex]:
                minIndex = j

        if minIndex is not i:
            swap array[i] and array[minIndex]

    return array

Dış döngü mevcut konumu kontrol eder. İç döngü, dizinin sıralanmamış kısmındaki en küçük elemanı arar.

PHP'de Selection Sort Örneği

Aşağıdaki örnek, PHP'de Selection Sort'u uygular. Fonksiyon, bir sayı dizisi alır ve sıralanmış diziyi döndürür.

<?php

function selectionSort(array $numbers): array
{
    $count = count($numbers);

    for ($i = 0; $i < $count - 1; $i++) {
        $minIndex = $i;

        for ($j = $i + 1; $j < $count; $j++) {
            if ($numbers[$j] < $numbers[$minIndex]) {
                $minIndex = $j;
            }
        }

        if ($minIndex !== $i) {
            $temp = $numbers[$i];
            $numbers[$i] = $numbers[$minIndex];
            $numbers[$minIndex] = $temp;
        }
    }

    return $numbers;
}

$numbers = [29, 10, 14, 37, 13];
$sortedNumbers = selectionSort($numbers);

print_r($sortedNumbers);

Çıktı şöyle olacaktır:

Array
(
    [0] => 10
    [1] => 13
    [2] => 14
    [3] => 29
    [4] => 37
)

Bu uygulama, elemanları değiştirmek için geçici bir değişken kullanır. Ayrıca, yer değiştirme işleminden önce minimum dizinin geçerli dizinden farklı olup olmadığını kontrol eder, bu da gereksiz yer değiştirmeleri önler.

JavaScript'te Selection Sort Örneği

Aynı algoritma, JavaScript'te diziler ve iç içe döngüler kullanılarak da uygulanabilir.

function selectionSort(numbers) {
    const result = [...numbers];
    const count = result.length;

    for (let i = 0; i < count - 1; i++) {
        let minIndex = i;

        for (let j = i + 1; j < count; j++) {
            if (result[j] < result[minIndex]) {
                minIndex = j;
            }
        }

        if (minIndex !== i) {
            const temp = result[i];
            result[i] = result[minIndex];
            result[minIndex] = temp;
        }
    }

    return result;
}

const numbers = [29, 10, 14, 37, 13];
console.log(selectionSort(numbers));

Çıktı şöyle olacaktır:

[10, 13, 14, 29, 37]

Bu JavaScript versiyonunda, orijinal dizi önce spread operatörü kullanılarak kopyalanır. Bu, fonksiyonun orijinal giriş dizisini doğrudan değiştirmesini engeller.

Zaman Karmaşıklığını Anlamak

Zaman karmaşıklığı, bir algoritmanın çalışma süresinin giriş boyutu arttıkça nasıl arttığını tanımlar. Selection Sort için ana maliyet, iç içe döngülerdeki karşılaştırmalardan gelir.

Selection Sort, minimum elemanı bulmak için dizinin kalan sıralanmamış kısmını her zaman tarar. Bu, dizi zaten sıralanmış olsa bile gerçekleşir.

n elemanlı bir dizi için:

• Geçiş 1, n - 1 karşılaştırma yapar.

• Geçiş 2, n - 2 karşılaştırma yapar.

• Geçiş 3, n - 3 karşılaştırma yapar.

• Bu, son geçiş 1 karşılaştırma yapana kadar devam eder.

Toplam karşılaştırma sayısı:

(n - 1) + (n - 2) + (n - 3) + ... + 1

Bu toplam şuna eşittir:

n(n - 1) / 2

Big O notasyonunu analiz ederken, sabitleri ve daha küçük terimleri göz ardı ederiz. Bu nedenle, zaman karmaşıklığı şu hale gelir:

O(n²)

En İyi Durum Zaman Karmaşıklığı

En iyi durum, dizi zaten sıralanmış olduğunda gerçekleşir.

[10, 13, 14, 29, 37]

Ancak, Selection Sort, geçerli elemanın en küçük olduğunu doğrulamak için her geçiş sırasında sıralanmamış kısmı taramaya devam eder. Bu nedenle, karşılaştırma sayısı değişmez.

Best Case Time Complexity: O(n²)

Bu, Selection Sort ve optimize edilmiş Bubble Sort arasındaki önemli farklardan biridir. Optimize edilmiş Bubble Sort, yer değiştirme olmazsa erken durabilirken, temel Selection Sort aynı karşılaştırma yapısını gerçekleştirmeye devam eder.

Ortalama Durum Zaman Karmaşıklığı

Ortalama durum, elemanlar rastgele sırada olduğunda gerçekleşir.

[29, 10, 14, 37, 13]

Selection Sort, minimum değeri bulmak için sıralanmamış kısmı tekrar tekrar aramalıdır. Karşılaştırma sayısı n² ile orantılı kalır.

Average Case Time Complexity: O(n²)

En Kötü Durum Zaman Karmaşıklığı

En kötü durum, dizi ters sırada sıralandığında gerçekleşir.

[37, 29, 14, 13, 10]

Bu durumda bile Selection Sort, en iyi ve ortalama durumlardakiyle aynı sayıda karşılaştırma yapar.

Worst Case Time Complexity: O(n²)

Girdinin sırası yer değiştirme sayısını etkiler, ancak standart Selection Sort algoritmasındaki karşılaştırma sayısını değiştirmez.

Alan Karmaşıklığı

Selection Sort, yerinde (in-place) bir sıralama algoritmasıdır. Bu, sıralanmış sonucu depolamak için başka bir diziye ihtiyaç duymadığı anlamına gelir. Elemanları aynı dizi içinde yer değiştirerek sıralar.

Kullanılan tek ekstra bellek, döngü sayaçları, minimum dizin ve yer değiştirme için geçici bir değişken gibi birkaç değişkendir.

Space Complexity: O(1)

Bu, Selection Sort'u büyük diziler için zaman açısından verimli olmasa da bellek açısından verimli hale getirir.

Selection Sort'ta Yer Değiştirme Sayısı

Selection Sort'un faydalı özelliklerinden biri, Bubble Sort'a kıyasla az sayıda yer değiştirme yapmasıdır. Her geçişte en fazla bir yer değiştirme işlemi yapar.

n eleman için, Selection Sort en fazla şu kadar yer değiştirme yapar:

n - 1 swaps

Bu, yer değiştirme işleminin pahalı olduğu durumlarda faydalı olabilir. Ancak, çoğu modern uygulamada, yüksek sayıda karşılaştırma, Selection Sort'u büyük veri kümeleri için daha gelişmiş sıralama algoritmalarından daha yavaş hale getirir.

Selection Sort Kararlı mıdır?

Kararlı bir sıralama algoritması, eşit elemanların orijinal sırasını korur. Standart Selection Sort kararlı değildir, çünkü yer değiştirme eşit elemanları birbirinin önüne veya arkasına taşıyabilir.

Örneğin, aynı puana sahip ancak farklı orijinal konumlara sahip iki kaydı düşünün. Normal bir yer değiştirme işlemi onların göreceli sırasını değiştirebilir.

Selection Sort, kararlı hale getirmek için değiştirilebilir, ancak standart uygulama genellikle kararsız kabul edilir.

Selection Sort Yerinde (In-Place) midir?

Evet, Selection Sort yerinde (in-place) bir algoritmadır. Diziyi giriş boyutuna orantılı ek depolama gerektirmeden sıralar.

Bu, giriş dizisi büyüdüğünde bile bellek kullanımının sabit kaldığı anlamına gelir.

In-place: Yes
Extra memory: Constant
Space complexity: O(1)

Selection Sort ve Bubble Sort Karşılaştırması

Selection Sort ve Bubble Sort, her ikisi de basit karşılaştırma tabanlı sıralama algoritmalarıdır. Her ikisi de iç içe döngüler kullandığı ve O(n²) zaman karmaşıklığına sahip olduğu için genellikle birlikte öğretilirler.

Ancak, farklı çalışırlar.

• Bubble Sort: Yan yana elemanları tekrar tekrar karşılaştırır ve yanlış sıradaysa yer değiştirir.

• Selection Sort: Sıralanmamış kısımdaki en küçük elemanı bulur ve doğru konumuna yerleştirir.

Bubble Sort tek bir geçişte çok sayıda yer değiştirme yapabilirken, Selection Sort her geçişte en fazla bir yer değiştirme yapar. Öte yandan, optimize edilmiş Bubble Sort dizi zaten sıralanmışsa erken durabilirken, Selection Sort genellikle taramaya devam eder.

Selection Sort'un Avantajları

Selection Sort'un, özellikle eğitim amaçlı ve küçük veri kümeleri için çeşitli avantajları vardır.

• Anlaşılması ve uygulanması kolaydır.

• Yerinde (in-place) çalışır ve sabit miktarda ekstra bellek gerektirir.

• Sınırlı sayıda yer değiştirme işlemi yapar.

• Yeni başlayanların iç içe döngüleri ve minimum değer aramasını anlamalarına yardımcı olur.

• Temel algoritma analizini açıklamak için kullanışlıdır.

Bu avantajlar, Selection Sort'u üretim düzeyinde sıralama için genellikle en iyi seçenek olmasa da, iyi bir öğrenme algoritması haline getirir.

Selection Sort'un Dezavantajları

Selection Sort'un ana dezavantajı, büyük veri kümelerindeki düşük performansıdır. İç içe döngüler kullandığı için, giriş boyutu arttıkça karşılaştırma sayısı hızla artar.

• En iyi, ortalama ve en kötü durumlarda O(n²) zaman karmaşıklığına sahiptir.

• Zaten sıralanmış girdiden doğal olarak fayda sağlamaz.

• Genellikle Merge Sort, Quick Sort ve yerleşik dil sıralama fonksiyonlarından daha yavaştır.

• Standart uygulama kararlı değildir.

• Büyük gerçek dünya veri kümeleri için uygun değildir.

Bu sınırlamalar nedeniyle, Selection Sort esas olarak öğrenim, gösterimler ve çok küçük koleksiyonlar için kullanılır.

Geliştiriciler Selection Sort'u Ne Zaman Kullanmalı?

Geliştiriciler, amaç öğrenmek, öğretmek veya performansın kritik olmadığı çok küçük dizilerle çalışmak olduğunda Selection Sort'u kullanmalıdır.

Selection Sort şu durumlarda kabul edilebilir olabilir:

• Veri kümesi çok küçük olduğunda.

• Amaç, sıralamayı manuel olarak açıklamak olduğunda.

• Bellek kullanımının sabit kalması gerektiğinde.

• Yer değiştirme sayısının sınırlı olması gerektiğinde.

• Kod, eğitim örnekleri veya algoritma pratiği için kullanıldığında.

Büyük veri kümeleri veya üretim uygulamaları için geliştiriciler genellikle yerleşik sıralama fonksiyonlarını veya daha verimli algoritmaları kullanmalıdır.

Selection Sort Ne Zaman Kullanılmamalı?

Selection Sort, performansın önemli olduğu ve veri kümesinin büyüyebileceği durumlarda kullanılmamalıdır. O(n²) zaman karmaşıklığı, onu gelişmiş sıralama algoritmalarına kıyasla verimsiz hale getirir.

Geliştiriciler şu durumlarda Selection Sort'tan kaçınmalıdır:

• Dizi binlerce veya milyonlarca eleman içerdiğinde.

• Uygulama hızlı sıralama gerektirdiğinde.

• Girdi zaten sıralanmış olabileceği ve erken durmanın önemli olduğu durumlarda.

• Kararlı sıralama gerektiğinde.

• Bir dilin yüksek düzeyde optimize edilmiş yerleşik bir sıralama fonksiyonu sağladığı durumlarda.

Profesyonel projelerde, yerleşik sıralama fonksiyonları genellikle daha iyidir çünkü optimize edilmiş, test edilmiş ve gerçek dünya kullanımına uygundur.

Selection Sort Uygularken Yapılan Yaygın Hatalar

Yeni başlayanlar Selection Sort'u uygularken genellikle küçük hatalar yaparlar. Bu hatalar genellikle yanlış döngü sınırları veya yanlış yer değiştirme (swap) mantığı nedeniyle meydana gelir.

Yaygın hatalar şunları içerir:

• İç döngüyü i + 1 yerine 0'dan başlatmak.

• Minimum dizini güncellemeyi unutmak.

• Minimum bulunduktan sonra değil, iç döngü içinde yer değiştirme yapmak.

• Minimum dizin yerine minimum değeri kullanmak.

• Dış döngüyü bir adım fazla çalıştırmak.

• Kopyalanmış bir dizi beklenirken orijinal diziyi değiştirmek.

En önemli kural şudur: önce minimum dizini bulun, ardından iç döngü bittikten sonra bir kez yer değiştirme yapın.

Selection Sort'u Anlamak İçin Pratik Kontrol Listesi

Selection Sort'u anladığınızdan emin olmak için şu soruları sorun:

• Algoritmanın neden Selection Sort olarak adlandırıldığını açıklayabilir miyim?

• Dizinin sıralanmış ve sıralanmamış kısımlarını ayırt edebilir miyim?

• Algoritmanın her geçişini manuel olarak takip edebilir miyim?

• Zaman karmaşıklığının neden O(n²) olduğunu açıklayabilir miyim?

• Alan karmaşıklığının neden O(1) olduğunu açıklayabilir miyim?

• Selection Sort ve Bubble Sort arasındaki farkı açıklayabilir miyim?

• Selection Sort'u iç döngü içinde yer değiştirme yapmadan uygulayabilir miyim?

Bu soruları yanıtlayabiliyorsanız, Selection Sort hakkında sağlam bir anlayışa sahipsiniz demektir.

Gerçek Yazılım Projelerinde Selection Sort

Selection Sort, modern üretim sistemlerinde doğrudan nadiren kullanılır, çünkü çoğu programlama dili zaten verimli yerleşik sıralama yöntemleri sunar. Örneğin, PHP'de sort, usort ve arsort gibi sıralama fonksiyonları bulunur. JavaScript diziler için sort yöntemini sağlar.

Ancak, Selection Sort'u öğrenmek hala değerlidir. Geliştiricilere algoritmaların verileri nasıl işlediğini, karmaşıklığın neden önemli olduğunu ve doğru algoritmayı seçmenin uygulama performansını neden etkileyebileceğini öğretir.

Basit algoritmaları anlamak aynı zamanda geliştiricileri teknik mülakatlara, problem çözme görevlerine ve daha gelişmiş algoritma konularına hazırlar.

Sonuç

Selection Sort, bir dizinin sıralanmamış kısmından en küçük elemanı tekrar tekrar seçen ve doğru konumuna yerleştiren basit bir sıralama algoritmasıdır. Anlaşılması kolay, uygulanması kolay ve sıralama temelleri ile algoritma analizini öğrenmek için faydalıdır.

Algoritma, iç içe döngüler kullanarak elemanları her zaman karşılaştırdığı için en iyi, ortalama ve en kötü durumlarda O(n²) zaman karmaşıklığına sahiptir. Giriş boyutuna orantılı ek bellek gerektirmeden diziyi yerinde (in-place) sıraladığı için O(1) alan karmaşıklığına sahiptir.

Selection Sort, büyük veri kümeleri için en iyi seçenek değildir, ancak yeni başlayanlar için mükemmel bir algoritmadır. Geliştiricilerin sıralama mantığını, manuel takibi, karşılaştırmaları, yer değiştirmeleri (swaps), yerinde işlemeyi ve Big O notasyonunu anlamalarına yardımcı olur.

Selection Sort'u öğrendikten sonra geliştiriciler, sıralama algoritmalarının nasıl tasarlandığı ve analiz edildiği konusunda daha güçlü bir anlayışla Insertion Sort, Merge Sort, Quick Sort ve Heap Sort gibi daha verimli algoritmalara geçebilirler.