Temel sıralama tasarımı

Sıralama, veriyi bir ölçüte göre dizmektir: sayıları küçükten büyüğe, öğrencileri nota göre, ürünleri fiyata göre. Python’da bu iş için hazır araçlar var, onları gelecek hafta göreceğiz. Bu hafta önce bir sıralama algoritmasının adım adım nasıl çalıştığına bakacağız.

Kodunu yazacağımız algoritma insertion sort: elemanları tek tek alıp sıralı bölümde yerine sokar. Selection sort ile bubble sort’un kodunu yazmayacağız. Hazır kodlarını adım adım izleyip insertion sort ile karşılaştıracağız.

1 Bu hafta neleri yapabilmelisiniz?

Bölümün sonunda:

• Sıralama probleminin girdisini ve ölçütünü açıklayabilmeli,
• Insertion sort’u kodlayabilmeli,
• Ara durumları izleyerek algoritmanın nasıl ilerlediğini gösterebilmeli,
• Insertion sort’un sıralı, ters sıralı ve yaklaşık sıralı veride neden farklı miktarda iş yaptığını açıklayabilmeli,
• Selection sort ile bubble sort’un temel fikirlerini karşılaştırabilmeli,
• Karşılaştırma ile yer değiştirmeyi (swap) ayırt edebilmeli,
• Yerinde sıralama (in-place), kararlılık (stability) ve adaptive davranış kavramlarını tanıma düzeyinde açıklayabilmeli,
• Temel sıralamaların en kötü durumda neden O(n²) iş yaptığını açıklayabilmelisiniz.

2 Sıralama neyi değiştirir?

Küçükten büyüğe sıralanınca liste şöyle olur:

[1, 3, 5, 7, 9]

Bu hafta sonuçtan çok, oraya giden yolla ilgileneceğiz:

Algoritma bu düzene hangi ara adımlarla ulaşıyor?

3 Insertion sort nasıl çalışır?

Insertion sort’u elde tuttuğunuz iskambil kâğıtlarını sıraya sokmaya benzetebilirsiniz:

1. Soldaki bölümün sıralı olduğunu kabul et,
2. Sıradaki elemanı al,
3. Soldaki sıralı bölümde doğru konuma yerleştir,
4. Tüm elemanlar bitene kadar devam et.

flowchart LR
    A["[3] | 7 4 2"] --> B["[3 7] | 4 2"]
    B --> C["[3 4 7] | 2"]
    C --> D["[2 3 4 7]"]

Köşeli parantez içindeki kısım, her adımda sıralı bölgeyi gösterir. Dikey çizginin sağında henüz yerleştirilmemiş elemanlar durur.

4 Insertion sort kodu

Bu fonksiyon verilen listeyi yerinde değiştirir: yeni bir liste oluşturmaz, elemanları aynı listenin içinde yer değiştirir. Sonucu doğrudan yazdırabilmek için aynı listeyi ayrıca döndürüyoruz.

5 Ara durumları izleyelim

Çalıştırmadan önce her turun sonunda listenin nasıl görüneceğini tahmin etmeye çalışın.

6 Neden current değişkeni gerekli?

İlk kaydırmada values[i] konumuna soldaki eleman yazılır. Yerleştireceğimiz değeri önceden bir değişkene koymazsak üzerine yazılır ve kaybolur. current bu değeri kaydırma bitene kadar saklar.

7 Alıştırma: insertion sort’u tamamla

Kaydırma yaptıktan sonra j değerini azaltmayı unutmayın. while bittikten sonra current için doğru konum j + 1 olacaktır.

def insertion_sort(values):
    for i in range(1, len(values)):
        current = values[i]
        j = i - 1

        while j >= 0 and values[j] > current:
            values[j + 1] = values[j]
            j -= 1

        values[j + 1] = current

    return values

8 Aynı algoritma her girdide aynı işi yapmaz

Insertion sort’un ne kadar iş yapacağı, verinin başlangıçtaki düzenine göre değişir.

8.1 Zaten sıralı veri

[1, 2, 3, 4, 5, 6]

Her current değeri zaten doğru yerdedir. while koşulu çoğu turda ilk kontrolde yanlış çıkar, neredeyse hiç kaydırma yapılmaz. Yapılan iş, eleman sayısıyla aşağı yukarı aynı oranda artar. Buna en iyi durum O(n) denir.

8.2 Ters sıralı veri

[6, 5, 4, 3, 2, 1]

Her yeni eleman, soldaki sıralı bölümün en başına gitmek zorundadır. Bunun için sıralı bölümdeki elemanların hepsi birer sağa kaydırılır. Çok sayıda karşılaştırma ve kaydırma gerekir. Bu, en kötü durum O(n²) davranışına bir örnektir.

8.3 Yaklaşık sıralı veri

[1, 2, 4, 3, 5, 6]

Yalnızca birkaç eleman yanlış yerdeyse insertion sort az sayıda kaydırmayla işi bitirebilir. Bu yüzden insertion sort’a adaptive (girdiye uyum sağlayan) bir algoritma denir: girdi kısmen sıralıysa daha az iş yapar.

Important

“Insertion sort O(n²)’dir” demek eksik kalır. Daha doğrusu şöyle: en kötü durumda O(n²), veri zaten sıralıysa (en iyi durum) O(n). Gerçekte ne kadar iş yapılacağı, verinin başlangıçtaki düzenine göre değişebilir.

9 İşlem sayısını veri düzenine göre karşılaştıralım

Çıktıda özellikle kaydırma sayısına bakın. Üç listede de 8 eleman (n = 8) var, ama kaydırma sayıları çok farklı.

10 Selection sort fikri

Selection sort başka bir yol izler:

1. Sıralanmamış bölümde en küçük elemanı bul,
2. Onu sıralanmamış bölümün ilk elemanıyla yer değiştir,
3. Kalan bölüm için tekrarla.

Insertion sort sıradaki elemanı alır ve kaydırarak yerine koyar. Selection sort ise kalanların en küçüğünü seçer ve öne alır.

11 Bubble sort fikri

Bubble sort yan yana duran iki elemanı karşılaştırır. Yanlış sıradaysalar yerlerini değiştirir. Büyük değerler her turda, sudaki kabarcık (bubble) gibi sağ uca doğru ilerler:

Bubble sort’un kodunu ezberlemeniz beklenmez. Verilen kodun ara durumlarını okuyabilmeniz ve “komşuları karşılaştır, yanlış sıradaysa yer değiştir (swap)” fikrini açıklayabilmeniz yeterlidir.

12 Karşılaştırmayı ve yer değiştirmeyi ayrı sayın

Selection sort bir turda çok sayıda karşılaştırma yapabilir, ama tur sonunda tek bir swap yapar. Bubble sort ise aynı turda birden çok swap yapabilir. Bir algoritmanın ne kadar iş yaptığını anlamak için döngüleri saymak yetmez. Hangi işlemin kaç kez yapıldığına da bakın.

13 İşlem sayısını gözlemlemek

Eleman sayısı iki katına çıkınca karşılaştırma sayısı yaklaşık dört katına çıkar: 10, 45, 190. O(n²) bu büyümeyi anlatır.

14 Neden O(n²)?

Selection sort gibi temel sıralamalarda hesap kabaca şöyledir:

n eleman için yaklaşık n tur
her turda yaklaşık n karşılaştırma
→ yaklaşık n × n = n²

Insertion sort da en kötü durumda aynı biçimde, n² ile büyür. Ama az önce gördüğümüz gibi, onda başlangıç düzeninin etkisi çok daha büyüktür.

15 Yerinde sıralama (in-place)

Bir algoritma veriyi aynı listenin içinde düzenliyor ve eleman sayısıyla büyüyen ayrı bir sonuç listesi oluşturmuyorsa ona genellikle in-place (yerinde) denir.

Insertion sort örneğimizde şu çağrıdan sonra numbers listesinin kendisi değişir:

numbers = [4, 2, 3]
insertion_sort(numbers)

Bu davranışın bir yan etkisi var:

backup aynı listeyi gösterdiği için o da sıralanmış görünür (2. haftadaki aliasing). Orijinal sırayı saklamanız gerekiyorsa önce listenin kopyasını alın.

16 Kararlılık (stability)

Sıralama anahtarı (sıralamada karşılaştırılan değer) aynı olan kayıtlar, sıralamadan sonra da aralarındaki eski sırayı koruyorsa bu sıralamaya kararlı sıralama denir.

Örneğin:

(Ayşe, 80)   önce
(Bora, 90)
(Cem, 80)    sonra

Notlara göre küçükten büyüğe sıralıyoruz. Ayşe’nin de Cem’in de notu 80. Kararlı bir sıralamada Ayşe yine Cem’den önce gelir.

Insertion sort kodumuzdaki koşul şu:

while j >= 0 and values[j] > current:

Değerler eşitse > koşulu yanlış çıkar ve soldaki eşit eleman boş yere sağa kaydırılmaz. Bu, kararlılığı korumaya yardım eder.

Koşulu dikkatsizce >= yaparsak eşit anahtarlı elemanları da kaydırmaya başlarız ve aralarındaki eski sırayı bozabiliriz.

16.1 Kararlılığı gözlemleyelim

Aşağıdaki küçük sürüm yalnızca grade alanına göre sıralıyor:

Ayşe ile Cem’in notu eşit, ama çıktıda Ayşe yine Cem’den önce geliyor.

17 Tahmin et: hangi girdi daha az iş yaptırır?

Aşağıdaki üç listeyi insertion sort ile sıraladığınızı düşünün. Çalıştırmadan önce en az kaydırmadan en çok kaydırmaya doğru sıralayın:

A = [1, 2, 3, 4, 5]
B = [1, 2, 4, 3, 5]
C = [5, 4, 3, 2, 1]

Beklenen cevap:

A → en az iş
B → arada
C → en çok iş

Üç listede de 5 eleman var. Yine de bazı algoritmalarda yapılan iş yalnızca eleman sayısına (n) değil, girdinin düzenine de bağlıdır.

18 Üç algoritma yan yana

Algoritma	Ana fikir	Veri düzenine duyarlılık	Bu dersteki düzey
insertion sort	sıradaki öğeyi sıralı bölgeye yerleştir	belirgin; yaklaşık sıralı veriden yararlanır	uygulama
selection sort	kalanların en küçüğünü seç	karşılaştırma sayısı başlangıç düzeninden az etkilenir	kod izleme
bubble sort	komşuları karşılaştır ve değiştir	sürüme göre erken durma eklenebilir	kod izleme

19 Bölüm özeti

• Sıralama, veriyi belirli bir ölçüte göre düzenler.
• Insertion sort’ta sıralı bölge soldan başlar ve her turda bir eleman büyür.
• Insertion sort zaten sıralı veride yaklaşık O(n), en kötü durumda O(n²) iş yapar.
• Yaklaşık sıralı veriden yararlanabildiği için insertion sort adaptive bir algoritma örneğidir.
• Selection sort her turda kalan bölümün minimumunu seçer.
• Bubble sort komşu elemanları karşılaştırır.
• Basit bir sıralama algoritmasını değerlendirirken tek bir Big-O etiketi yetmez. Girdinin düzenine ve hangi işlemin kaç kez yapıldığına da bakın.
• In-place sıralama mevcut listeyi değiştirir.
• Kararlı sıralamada eşit anahtarlı kayıtlar aralarındaki eski sırayı korur. Insertion sort’taki > karşılaştırması bunu korumaya yardım eder.

20 Kendinizi kontrol edin

1. Insertion sort’ta “sıralı bölüm” hangi tarafta büyür?
2. Zaten sıralı veri insertion sort için neden daha kolaydır?
3. Ters sıralı veride neden çok sayıda kaydırma gerekir?
4. Insertion sort için kullanılan adaptive sözcüğü ne anlatır?
5. Selection sort her turda neyi seçer?
6. Bubble sort hangi elemanları karşılaştırır?
7. Aynı listeyi gösteren iki değişken varken in-place sıralama nasıl bir yan etkiye yol açar?
8. Kararlı sıralama neyi korur ve > ile >= arasındaki fark neden önemli olabilir?