Algoritmalar Bölüm 1 - Seçme Sıralaması(Selection Sort)

ÖNEMLİ : Kendim için aldığım notlar. Umarım size de bir faydası olur. Kullanılan her bir makale referans olarak eklenmiştir.

Seçme Sıralaması (Selection Sort)

Aşağıdaki kart oyunu, seçme algoritmasının(selection algorithm) nasıl çalıştığını basitçe açıklamaktadır. Oyun çok basit; dağınık kartları küçükten büyüğe olacak şekilde birbirleriyle karşılaştırarak sıralamak istiyoruz.

Bunu yapmak için; öncelikle ilk konumdaki ögeyle başlamalı ve en küçük ögeyi bulmak için bu ögeyi diğer ögelerle karşılaştırmalıyız. Bu durumda ilk ögemiz, varsa, listedeki en küçük ögenin yerini alacağı için bizim referans değerimiz olacaktır. Her neyse, listedeki ilk konum dışındaki en küçük ögeyi bulursak, onu ilk ögeyle değiştirmemiz gerekir(tabii ki bulunan bu değer ilk ögeden küçükse!). Listedeki en küçük ögeyi ilk pozisyona yerleştirdikten sonra benzer işlemleri 2. pozisyondan başlayarak devam edeceğiz. Bu durumda ise referansımız 2.öge olur. Karşılaştırma, ve varsa yer değiştirme işlemleri bittikten sonra, benzer işlemleri sırasıyla listenin sondan bir önceki elemanına kadar devam ettirmemiz gerekiyor. Özetle seçme sıralaması algoritması bu şekilde gerçekleşir.

Seçme Sıralamasına Bir Örnek

Örneğin, bunun gibi sıralanmamış bir listemiz var;

9 - 4 - 3 - 1

Amacımız

Sayıları birbiriyle karşılaştırarak küçükten büyüğe doğru sıralamak.

Seçme sıralama algoritması nasıl uygulanır

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class SelectionSort {
    public static void main(String[] args) {
        int[] list = {9,4,3,1};
        for(int i=0; i< list.length-1; i++) {
            boolean hasSmallestBeenFounded = false;
            int smallest = i;
            for(int j=i; j< list.length-1; j++){
                if (list[j + 1] < list[smallest]) {
                    smallest = j + 1;
                    hasSmallestBeenFounded = true;
                }
            }
            if(hasSmallestBeenFounded){
                int tempValue = list[i];
                list[i] = list[smallest];
                list[smallest] = tempValue;
            }
        }
//       Arrays.stream(list)
//      .forEach(value -> System.out.print(value + " - "));
    }
}

1. Seçme sıralamasını listeme uygulamak için iki tane iç içe geçmiş for döngüsüne ihtiyacım var(elbette for döngüsü kullanmak şart değildir). Dıştaki for döngüm, tutmak istediğim konumu takip ederek listenin başından başlar(yani yukarıdaki tanıma göre bizim referans değerimiz oluyor). Algoritmanın en başında bu konum elbette “0” olacaktır. Öte yandan, içteki for döngüm ise, en küçük ögeyi bulmak için dıştaki for döngüsünün tuttuğu konumdaki öge dışındaki diğer ögeleri kontrol eder.
2. Bulunan her yeni en küçük değer için int “smallest” değeri içteki for döngüsü boyunca güncellenecektir.
3. “smallest” ve “hasSmallestBeenFounded” değerlerinin siz içteki for döngüsüne girmeden hemen önce güncellendiğini fark edeceksiniz. Çünkü içteki for döngüsünün amacı en küçük değeri bulmak ve referans değerle karşılaştırmaktır. Şayet içteki döngünün dışına çıktığımızda, bu değerlerin görevlerini yerine getirmiş olduğunu varsayarak, bu iki değeri sonraki en küçük değeri bulmak için sıfırlarız.
4. İçteki for döngüsü çalışmasını bitirdiğinde, en azından bir tane bile en küçük değer bulunsa, “hasSmallestBeenFounded” boolean değeri true olarak işaretlenir. Çünkü içteki döngü boyunca smallest değeri değişebilir. Şayet, en küçük değer bulunmazsa, “hasSmallestBeenFounded” değeri false olarak kalır ve döngünün dışındaki “if” ifadesinin içine girilmez.
5. İçteki döngünün içinde bir “if” ifadesi var, if (list[j + 1] < list[smallest]). Burada, en küçük değeri temsil etmesi beklenen smallest ile içteki döngünün takip ettiği “j + 1” konumundaki değerler karşılaştırılır. Eğer, “j + 1” konumunun işaret ettiği değer mevcut “smallest” değerden daha küçükse, bu “smallest” değeri “j+1” konumunu temsil eden değer ile güncelleriz. smallest değeri geçici en küçük değer gibi düşünebilirsiniz.
6. İçteki döngü, bir tane bile en küçük değer bulsa, içteki döngünün dışında bulunan “if” ifadesinin içine girer, bu da bulunan en küçük değeri ilk konumdaki değerle değiştirir (ki bu elbette dış döngü aracılığıyla tuttuğum konumdur)).
7. Dış döngümün ilk konumu bulunan en küçük değerle(varsa) değiştirildikten sonra, i sayısını bir artırarak dış döngümün 2. konumu ile aynı işlemi tekrarlarız. Daha sonra dış döngümün sondan bir önceki konumuna(list.length-1) kadar aynı işlemler devam eder.

Seçme Sıralamasının Zaman Karmaşıklığı Nedir? (Time Complexity of Selection Sort?)

Seçme sıralamasının zaman verimliliği ikinci derecedendir(quadratic).

Seçme Sıralamasının En İyi Durum Zaman Karmaşıklığı

O(n²) karşılaştırma, O(1) yer değiştirme,

En iyi durum zaman karmaşıklığında, listenin zaten sıralı olduğunu düşünürüz. Yer değiştirme olmayacağı için O(n) 1 olur. Ancak listenin sıralı olup olmadığını öğrenmek için her durumda karşılaştırma olacaktır. Bu, quadratic zaman karmaşıklığını beraberinde getirir, yani, O(n²). Çünkü 2 tane iç içe for döngümüz bulunmaktadır.

2 tane iç içe for döngüsü her zaman O(n²) quadratic zaman karmaşıklığını beraberinde getirmez. Bazı durumlarda yanıltıcı sorularla karşılaşabilirsiniz.

Seçme Sıralamasının En Kötü Durum Zaman Karmaşıklığı

O(n²) karşılaştırma, O(n) yer değiştirme,

Yazılım geliştiriciler genellikle sadece en kötü durumun çalışma zamanını bulmak üzerine yoğunlaşır çünkü n boyutlu herhangi bir girdi için en uzun çalışma zamanı odur. Tıpkı en iyi durum zaman karmaşıklığında olduğu gibi, karşılaştırma ikinci dereceden(quadratic) zaman karmaşıklığında gerçekleşir. Ama en kötü senaryoda elbette listemiz sıralı olmayacak. Çünkü en kötü senaryo bunu gerektirir. Bu yüzden yer değiştirme O(n) zamanda gerçekleşir.

Seçme Sıralamasının Ortalama Durum Zaman Karmaşıklığı

O(n²) karşılaştırma, O(n) yer değiştirme,

Ortalama süredeki adım sayısı en kötü durumun yarısı olsa bile sabitler(constants) formülasyonda dikkate alınmayacağından sonuç yine en kötü durumla aynı olacaktır.

Referanslar:

• selection sort pseudocode
• selection sort wiki
• Introduction to Algorithms third edition