Sıralama algoritmaları

Telefonundaki kişiler alfabetik sırayla, bir oyundaki skor tablosu puana göre, çevrim içi mağazadaki ürünler de fiyata göre dizilir. Bütün bu durumlarda bilgisayar sıralama yapar, yani öğeleri belirli bir kurala göre dizer. Üstelik önceki derste gördüğümüz gibi hızlı ikili arama yalnızca sıralı bir listede çalışır. Peki bilgisayar bir listeyi nasıl sıralar?

Kabarcık sıralaması

Kabarcık sıralamasında komşu elemanlar ikişer ikişer karşılaştırılır: soldaki sağdakinden büyükse yer değiştirirler. Listenin baştan sona bir kez gezilmesine geçiş denir. Her geçişten sonra kalanların en büyüğü, sudaki bir kabarcık gibi listenin sonuna “yükselir”. Bir geçişte hiç yer değiştirme olmazsa liste zaten sıralanmıştır.

def bubble_sort(a):
    a = a[:]
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break
    return a

print(bubble_sort([5, 1, 4, 2]))
print(sorted(['Murad', 'Aysel', 'Leyla', 'Elvin']))

[1, 2, 4, 5]
['Aysel', 'Elvin', 'Leyla', 'Murad']

Seçmeli sıralama

Seçmeli sıralamada listenin sıralanmamış kısmındaki en küçük eleman bulunur ve o kısmın ilk elemanıyla yer değiştirilir. Böylece soldaki sıralı kısım her adımda bir eleman büyür.

Eklemeli sıralama

Eklemeli sıralama, bir oyuncunun elindeki kartları dizmesine benzer: sıradaki kartı alır ve zaten sıralı olan kartların arasına doğru yere “ekler”. Liste neredeyse sıralıysa bu yöntem çok hızlı çalışır.

Hangi algoritma daha hızlı?

Sıralamanın hızı genellikle karşılaştırma sayısıyla ölçülür. Üç basit yöntemin her biri en kötü durumda yaklaşık n(n − 1) / 2 karşılaştırma yapar: n = 10 için 45, n = 1000 için ise 499.500. Liste 10 kat uzarsa iş yaklaşık 100 kat artar!