Selection Sort Nasıl Çalışır? Seçmeli Sıralama Adım Adım Örnek

Selection sort, her turda dizinin sıralanmamış bölümündeki en küçük elemanı bulur ve bu elemanı o bölümün ilk elemanıyla yer değiştirir. Böylece dizinin başındaki sıralı bölüm her turda bir eleman büyür. Seçmeli sıralamayı anlamanın en kolay yolu, bu iki bölümün nasıl değiştiğini adım adım izlemektir.

Algoritma, örneğin başında sıralı bir bölüm olmadığını kabul eder. Her turda geriye kalan bölüm baştan sona taranır, en küçük değer belirlenir ve tarama tamamlandıktan sonra uygun konuma taşınır. Bu nedenle bulunan değer, tarama sürerken her küçük değerle hemen yer değiştirmez.

Selection sort diziyi sıralı ve sıralanmamış bölümlere ayırır

Selection sort dizinin başında giderek büyüyen bir sıralı bölüm ve bu bölümün sağında kalan bir sıralanmamış bölüm oluşturur. İlk turda sıralı bölüm boştur. Algoritma, tüm diziyi tarayıp en küçük elemanı bulduktan sonra bu elemanı ilk konuma alır.

İkinci turda ilk eleman artık doğru konumdadır ve tarama ikinci elemandan başlar. En küçük değer, sıralanmamış bölümün ilk elemanıyla yer değiştirir. Aynı işlem her turda tekrarlandığı için sıralı bölüm soldan sağa doğru genişler.

Buradaki önemli ayrıntı, her turda sıralanmamış bölümün tamamının incelenmesidir. Örneğin tarama sırasında daha küçük bir değer bulunursa yalnızca geçici olarak “en küçük değer” olarak tutulur. Yer değiştirme, tarama bittikten sonra yapılır. Bu yaklaşım, algoritmanın hangi değeri hangi konuma taşıyacağını açıkça takip etmeyi sağlar.

Beş elemanlı diziyi dört turda nasıl izleriz?

Örnek dizimiz başlangıçta [29, 10, 14, 37, 13] olsun. Python’daki gibi sıfırdan başlayan indeksleri kullanırsak ilk elemanın indeksi 0, ikinci elemanın indeksi 1 olur. Her turda sıralanmamış bölüm taranır ve en küçük elemanın indeksi belirlenir.

İlk turda tüm dizi tarandığı için en küçük değer olan 10, indeks 1’den indeks 0’a taşınır. İkinci turda 10 artık sıralı bölümde kalır ve kalan dört eleman arasındaki en küçük değer 13 olur. Bu değer indeks 4’ten alınarak indeks 1’e yerleştirilir.

Üçüncü turda sıralanmamış bölümün ilk elemanı 14’tür ve taranan bölümdeki en küçük değer yine 14 çıkar. Değer zaten doğru konumda olduğu için algoritma bu turda ek bir yer değiştirme yapmadan ilerleyebilir. Son turda ise 29, 37 ile yer değiştirerek dizinin sıralı hâlini oluşturur.

Python kodunda iç içe döngüler ne yapar?

Selection sort algoritmasında dış döngü, sıralı bölümün başlayacağı konumu belirler. İç döngü ise bu konumun hemen sonrasından dizinin sonuna kadar ilerleyerek en küçük elemanın indeksini arar. Tarama tamamlandığında bulunan eleman, sıralanmamış bölümün ilk elemanıyla bir kez yer değiştirir.

def selection_sort(numbers):
    for i in range(len(numbers) - 1):
        min_index = i

        for j in range(i + 1, len(numbers)):
            if numbers[j] < numbers[min_index]:
                min_index = j

        if min_index != i:
            numbers[i], numbers[min_index] = numbers[min_index], numbers[i]

    return numbers


data = [29, 10, 14, 37, 13]
print(selection_sort(data))

İlk turda i değeri 0'dır. Bu nedenle algoritma, dizinin tamamını tarar ve en küçük değer olan 10'un indeksini min_index içinde tutar. Tarama sona erince 10 ile 29 yer değiştirir. İkinci turda i değeri 1 olur ve iç döngü yalnızca 2. konumdan başlayarak kalan bölümü inceler.

min_index değişkeni en küçük değerin kendisini değil, dizide bulunduğu konumu saklar. Değiş tokuş yapabilmek için bu bilgi gerekir. Örneğin en küçük değer 10 olsa bile 10'un dizinin hangi konumunda bulunduğunu bilmeden onu sıralı bölümün başına taşıyamazsın.

Sık yapılan üç hata

• Her karşılaştırmada hemen yer değiştirmek: İç döngüde daha küçük bir değer bulunduğu anda değiş tokuş yapmak, algoritmanın önce tüm bölümü tarayıp en küçük elemanı seçme mantığını bozar. Örneğin [4, 1, 3, 2] dizisinde ilk tur boyunca birden fazla değiş tokuş yapılabilir. Selection sort ise en küçük elemanı belirleyip tur sonunda tek değiş tokuş yapmayı hedefler.
• İç döngüyü sıfırdan başlatmak: İç döngü j = 0 ile başlarsa daha önce sıralanmış bölüm de yeniden taranır. İkinci turda 0. konumdaki 10, 1. konumdaki 13'ten küçük olduğu için seçilebilir ve sıralı bölüm yeniden bozulabilir. Bu yüzden başlangıç noktası her zaman i + 1 olmalıdır.
• Yalnızca en küçük değeri takip etmek: En küçük değeri bir değişkende saklamak, onun dizideki yerini göstermez. Bu durumda değiş tokuş için diziyi ikinci kez aramak gerekir. Eşit değerler bulunduğunda ilk eşleşen konumu seçmek de yanlış elemana müdahale edilmesine yol açabilir.

Karşılaştırma sayısı neden her durumda O(n²) olur?

Selection sort, dizi sıralı, ters sıralı veya karışık olsa da her turda sıralanmamış bölümün tamamını tarar. Bu nedenle algoritmanın yaptığı karşılaştırma sayısı giriş dizisinin düzenine göre azalmaz.

Beş elemanlı dizide ilk turda 4, ikinci turda 3, üçüncü turda 2 ve son turda 1 karşılaştırma yapılır. Toplam sayı 4 + 3 + 2 + 1 = 10 olur. Eleman sayısı n olduğunda toplam karşılaştırma sayısı n(n - 1) / 2 biçimindedir.

Her turda taranan bölüm küçülse de bu toplam, eleman sayısı büyüdükçe karesel biçimde artar. Bu nedenle selection sort için zaman karmaşıklığı O(n²) olarak ifade edilir. Big O gösterimini daha geniş örneklerle incelemek için algoritma ve programlama yazılarına göz atabilirsin.

Karşılaştırma sayısı ile yer değiştirme sayısı aynı değildir. Verilen örnekte yalnızca gerekli konumlarda değiş tokuş yapılır ve üç yer değiştirme gerçekleşir. Genel olarak en fazla n - 1 yer değiştirme yapılabilir; buna karşılık karşılaştırmalar her turda sürer.

Selection sort neden kararlı değildir ve diğerlerinden nasıl ayrılır?

Selection sort genel olarak kararlı bir sıralama algoritması sayılmaz. Kararlılık, eşit anahtara sahip elemanların başlangıçtaki göreli sırasının korunmasıdır.

Örneğin (2, A), (2, B), (1, C) dizisinde ilk turda en küçük değer olan (1, C) seçilir ve dizinin başındaki (2, A) ile yer değiştirir. Dizi (1, C), (2, B), (2, A) hâline gelir. İki elemanın değeri eşit olmasına rağmen A ve B etiketlerinin sırası değiştiği için bu uygulama kararlı değildir.

Karşılaştırmada < ya da <= kullanılması, eşit değerler arasından hangi elemanın seçileceğini etkileyebilir. Elemanın doğrudan yer değiştirilmesi yerine araya taşınması gibi uygulama ayrıntıları da sonucu değiştirebilir. Bu nedenle belirli bir selection sort uyarlamasının kararlılığı, yalnızca algoritmanın adına bakılarak değerlendirilmemelidir.

Bubble sort komşu elemanları karşılaştırarak gerektiğinde yer değiştirir. Insertion sort ise her yeni elemanı daha önce sıralanmış bölüme yerleştirir ve uygun uygulandığında eşit elemanların sırasını koruyabilir. Bubble sort, insertion sort, merge sort ve quick sort konularındaki ayrıntılı açıklamalara Berk Akademi sıralama algoritmaları yazılarından ulaşabilirsin.

Sık Sorulan Sorular

Selection sort her turda mutlaka yer değiştirme yapar mı?

Selection sort her turda mutlaka fiziksel olarak yer değiştirme yapmak zorunda değildir. Sıralanmamış bölümün ilk elemanı zaten en küçük elemansa, algoritma aynı konumu kendisiyle değiştirebilir veya bu işlemi koşulla atlayabilir.

Selection sort içinde iç döngü neden i + 1 konumundan başlar?

İç döngü i + 1 konumundan başlar çünkü i konumundaki eleman o turda incelenen bölümün ilk elemanıdır. Daha soldaki elemanlar önceki turlarda yerleştiği için yeniden karşılaştırılmaları gerekmez.

Selection sort neden kararlı bir sıralama algoritması sayılmaz?

Selection sort, seçtiği en küçük elemanı sıralanmamış bölümün başındaki elemanla doğrudan yer değiştirebilir. Bu işlem, değeri eşit olan elemanların başlangıçtaki sırasını bozabildiği için standart uygulama kararlı kabul edilmez.

Selection sort karşılaştırma sayısı neden giriş dizisinin sırasından etkilenmez?

Selection sort her turda sıralanmamış bölümün tamamını tarayarak en küçük elemanın konumunu bulur. Dizi önceden sıralı olsa bile bu tarama sürdüğü için karşılaştırma sayısı girişin düzeninden çok eleman sayısına bağlıdır.

Selection sort, her turda en küçük elemanı doğru konuma taşıma fikrini ve iç içe döngülerin görev paylaşımını anlamak için sade bir örnektir.