Verimli sıralama algoritmaları

Kabarcık sıralaması bir milyon kaydı sıralamak için yaklaşık 5 · 10¹¹ karşılaştırma yapar; saniyede 10⁸ karşılaştırmayla bu bir saati aşar. Birleştirmeli sıralama aynı işi yaklaşık 2 · 10⁷ karşılaştırmayla, saniyenin bir kesrinde yapar. Fark bilgisayarda değil, fikirdedir: böl ve yönet. Bu derste iki temel n log n algoritmasını, karşılaştırmalı sıralamanın daha hızlı olamayacağının ispatını ve bu yasağı nasıl “atlatacağımızı” öğreneceğiz.

Birleştirmeli sıralama (merge sort)

1. Böl: diziyi ortadan iki yarıya ayır.
2. Çöz: her yarıyı özyinelemeli sırala (tek elemanlı dizi zaten sıralıdır).
3. Birleştir: iki sıralı yarının baştaki elemanlarını karşılaştırıp küçüğü sonuca aktararak birleştir; doğrusal süre O(n).

comparisons = 0

def merge(left, right):
    global comparisons
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        comparisons += 1
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    return out + left[i:] + right[j:]

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    return merge(merge_sort(a[:mid]), merge_sort(a[mid:]))

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
comparisons = 0
merge_sort([(i * 37) % 1024 for i in range(1024)])
print('n = 1024:', comparisons, 'comparisons; n log2 n =', 1024 * 10)

[3, 9, 10, 27, 38, 43, 82]
n = 1024: 8161 comparisons; n log2 n = 10240

Hızlı sıralama (quicksort)

Hızlı sıralama işi ters sırayla yapar: önce bir pivot (dayanak elemanı) seçilir ve dizi bölümlenir; pivottan küçük ya da eşit olanlar sola, büyükler sağa gider. Pivot son yerine oturur, ardından iki parça özyinelemeli sıralanır; birleştirme gerekmez. Yerinde çalışır (ek dizi gerekmez) ve uygulamada çok hızlıdır ama kararlı değildir.

comparisons = 0

def partition(a, lo, hi):
    global comparisons
    pivot, i = a[hi], lo - 1
    for j in range(lo, hi):
        comparisons += 1
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    return i + 1

def quicksort(a, lo, hi):
    if lo < hi:
        p = partition(a, lo, hi)
        quicksort(a, lo, p - 1)
        quicksort(a, p + 1, hi)

a = [7, 2, 9, 4, 3, 8, 5]
print(partition(a, 0, 6), a)
for name, data in [('mixed', [(i * 37) % 200 for i in range(200)]), ('sorted', list(range(200)))]:
    comparisons = 0
    quicksort(data, 0, len(data) - 1)
    print(name, comparisons, data == sorted(data))

3 [2, 4, 3, 5, 9, 8, 7]
mixed 1542 True
sorted 19900 True

Alt sınır: Ω(n log n)

Yalnızca “a ≤ b mi?” sorusunu soran herhangi bir sıralama algoritmasını bir karar ağacı olarak düşünelim: her iç düğüm bir karşılaştırma, her yaprak bir cevaptır, yani elemanların bir dizilişidir. n farklı eleman n! biçimde dizilebilir ve her biri farklı bir yaprağa götürmelidir. h yüksekliğindeki bir ikili ağacın en fazla 2ʰ yaprağı vardır; demek ki 2ʰ ≥ n!.

Sayarak sıralama: sınırı aşmak

Ω(n log n) sınırı yalnızca karşılaştırmaya dayalı algoritmalar için geçerlidir. Anahtarlar 0 … k aralığında tam sayılarsa, sayarak sıralama hiç karşılaştırma yapmaz: her değerin kaç kez geçtiğini sayar, sonra değerleri sayıları kadar sırayla yazar. Süre ve bellek O(n + k)'dir. Kararlı sayarak sıralamanın basamak basamak tekrarlanmasına taban sıralaması (radix sort) denir: d basamaklı sayılar için O(d · (n + k)).

import math

def counting_sort(a, k):
    count = [0] * (k + 1)
    for x in a:
        count[x] += 1
    out = []
    for value, c in enumerate(count):
        out.extend([value] * c)
    return count, out

print(counting_sort([2, 5, 3, 0, 2, 3, 0, 3], 5))
for n in [3, 4, 5, 10, 1000]:
    print(n, math.ceil(math.log2(math.factorial(n))))

([2, 0, 2, 3, 0, 1], [0, 0, 2, 2, 3, 3, 3, 5])
3 3
4 5
5 7
10 22
1000 8530