Quick Sort, Introsort ve Counting/Radix Sort: .NET'in Array.Sort'u Nasıl Sıralar

Sürüm notu: Bu yazıdaki kodlar .NET 10 ve C# 14 ile derlenip xUnit v3 4.0.2 testleriyle doğrulanmıştır; ölçümler BenchmarkDotNet 0.15.8 ile alınmıştır.

Önce Tahmin Et

Ders kitabındaki quick sort'u, son element'i pivot seçen versiyonuyla yazdın ve rastgele 10.000 fiyatta Array.Sort'tan yalnızca yüzde 45 yavaş çıktı. Fena değil. Aynı kod, zaten sıralı gelen 10.000 fiyatı sıralarken ne kadar sürer: yine aynı mı, iki kat mı, yüzlerce kat mı?

İkinci soru: bir geliştirici sıralama için (a, b) => a - b comparison'ını yazıyor; kısa ve "sayısal fark" mantığına uygun. [int.MaxValue, -10, int.MinValue, 5] array'i bununla sıralanınca sonuç doğru olur mu?

Partition: Quick Sort'un Kalbi

Quick sort da divide and conquer ama merge sort'un tersine işi bölerken yapıyor: bir pivot seç, array'i pivot'tan küçükler solda, büyükler sağda kalacak şekilde yeniden düzenle (partition), sonra iki tarafı recursive sırala. Birleştirme adımı yok; partition bittiğinde pivot zaten son yerinde. En basit partition Lomuto'nunki:

// çağrıdan sonra: a[lo..p-1] < pivot, a[p] == pivot, a[p+1..hi] >= pivot
public static int LomutoPartition(int[] a, int lo, int hi)
{
    int pivot = a[hi];
    int i = lo; // pivot'tan küçük bir sonraki element'in yazılacağı yer
    for (int j = lo; j < hi; j++)
    {
        if (a[j] < pivot)
        {
            (a[i], a[j]) = (a[j], a[i]);
            i++;
        }
    }
    (a[i], a[hi]) = (a[hi], a[i]); // pivot son yerine
    return i;
}

Döngü boyunca array dört bölgeye ayrılıyor: [lo, i) pivot'tan küçükler, [i, j) pivot'tan büyük ya da eşitler, [j, hi) henüz bakılmamışlar ve en sonda pivot. Her adım bu invariant'ı koruyor: j'deki element küçükse i'deki ilk "büyük" ile yer değiştiriyor ve küçükler bölgesi bir büyüyor. Döngü bitince pivot'u i'ye koymak yeterli. Test, şekildeki örneği aynen doğruluyor:

[Fact]
public void LomutoPartition_PlacesPivotAtFinalIndex()
{
    int[] prices = [42, 15, 77, 8, 30, 61, 25];

    int p = QuickSort.LomutoPartition(prices, 0, prices.Length - 1);

    Assert.Equal(2, p);
    Assert.Equal(25, prices[p]);
    Assert.All(prices[..p], x => Assert.True(x < 25));
    Assert.All(prices[(p + 1)..], x => Assert.True(x >= 25));
}

Quick Sort ve Kötü Girdi

Partition'ı recursive çağırınca quick sort hazır. Recursion derinliğini ölçmek için küçük bir sayaç ekledik:

public static int MaxDepth { get; private set; } // yazı için ölçüm

// Lomuto partition, pivot son element: ders kitabı versiyonu
public static void Lomuto(int[] items)
{
    MaxDepth = 0;
    LomutoSort(items, 0, items.Length - 1, 1);
}

private static void LomutoSort(int[] a, int lo, int hi, int depth)
{
    if (lo >= hi) return;
    MaxDepth = Math.Max(MaxDepth, depth);
    int p = LomutoPartition(a, lo, hi);
    LomutoSort(a, lo, p - 1, depth + 1);
    LomutoSort(a, p + 1, hi, depth + 1);
}

Pivot array'i iki eşit yarıya bölerse recursion derinliği log₂ n ve toplam iş n log n. Sorun, pivot'un her seferinde en küçük ya da en büyük element olduğu girdi. Sıralı bir array'de son element her zaman en büyük; partition sağ tarafı boş, sol tarafı n − 1 elemanlı bırakıyor. Derinlik n, toplam karşılaştırma n²/2. Test bunu sayıyla gösteriyor:

[Fact]
public void Lomuto_SortedInput_RecursesNTimes_HoareStaysShallow()
{
    int[] sorted = [.. Enumerable.Range(0, 5_000)];

    QuickSort.Lomuto([.. sorted]);
    int lomutoDepth = QuickSort.MaxDepth;
    QuickSort.Hoare([.. sorted]);
    int hoareDepth = QuickSort.MaxDepth;

    Assert.Equal(4_999, lomutoDepth);
    Assert.True(hoareDepth <= 13, $"hoare depth {hoareDepth}");
}

5.000 elemanlık sıralı girdide derinlik 4.999. Bu yalnızca yavaşlık değil: serinin beşinci yazısında gördüğümüz gibi derinlik birkaç on bine çıkınca process stack overflow ile ölür. Sıralı ya da neredeyse sıralı girdi gerçek hayatta en yaygın girdilerden biri; veritabanından ORDER BY ile gelen bir listeyi tekrar sıralamak tam bu durum.

İlk çare pivot'u rastgele seçmek. Rastgele pivot'la hiçbir sabit girdi sürekli kötü değil; beklenen derinlik O(log n). Yine de şanssız bir koşu ihtimali sıfır değil ve sonuç tekrarlanabilir değil:

// rastgele pivot: hiçbir sabit girdi her zaman kötü değil
public static void RandomPivot(int[] items, Random random)
{
    RandomSort(items, 0, items.Length - 1, random);
}

private static void RandomSort(int[] a, int lo, int hi, Random random)
{
    if (lo >= hi) return;
    int r = random.Next(lo, hi + 1);
    (a[r], a[hi]) = (a[hi], a[r]); // rastgele pivot'u sona taşı, sonra her zamanki Lomuto
    int p = LomutoPartition(a, lo, hi);
    RandomSort(a, lo, p - 1, random);
    RandomSort(a, p + 1, hi, random);
}

Hoare Partition ve Median-of-Three

İkinci çare pivot'u daha akıllıca seçmek ve partition'ı daha verimli yapmak. Hoare'un orijinal partition'ı iki uçtan içeri doğru ilerleyen iki pointer kullanıyor; yanlış tarafta duran iki element'i bulunca yer değiştiriyor. Lomuto'ya göre ortalama üç kat daha az swap yapıyor ve eşit değerlerle dolu bir array'de dengeli bölüyor. Pivot olarak ilk, orta ve son element'in medyanını almak (median-of-three) sıralı ve ters sıralı girdiyi en iyi duruma çeviriyor:

// median-of-three pivot'lu Hoare partition; küçük tarafa recursion, büyük tarafa döngü
public static void Hoare(int[] items)
{
    MaxDepth = 0;
    HoareSort(items, 0, items.Length - 1, 1);
}

private static void HoareSort(int[] a, int lo, int hi, int depth)
{
    while (lo < hi)
    {
        MaxDepth = Math.Max(MaxDepth, depth);
        int p = HoarePartition(a, lo, hi);
        // küçük yarı recursion ile, büyük yarı döngüyle: stack derinliği O(log n) kalır
        if (p - lo < hi - p)
        {
            HoareSort(a, lo, p, depth + 1);
            lo = p + 1;
        }
        else
        {
            HoareSort(a, p + 1, hi, depth + 1);
            hi = p;
        }
    }
}

// çağrıdan sonra: a[lo..p]'deki her element a[p+1..hi]'deki her element'ten küçük ya da eşit
public static int HoarePartition(int[] a, int lo, int hi)
{
    int mid = lo + (hi - lo) / 2;
    int pivot = MedianOfThree(a[lo], a[mid], a[hi]);
    int i = lo - 1, j = hi + 1;
    while (true)
    {
        do i++; while (a[i] < pivot);
        do j--; while (a[j] > pivot);
        if (i >= j) return j;
        (a[i], a[j]) = (a[j], a[i]);
    }
}

private static int MedianOfThree(int x, int y, int z) =>
    Math.Max(Math.Min(x, y), Math.Min(Math.Max(x, y), z));

HoareSort'taki ikinci önemli fikir "küçük tarafa recursion, büyük tarafa döngü". Her recursive çağrı en fazla yarı boyutta bir parçaya gidiyor; pivot ne kadar kötü olursa olsun stack derinliği log₂ n'i geçemiyor. Pivot kötüyse süre yine O(n²)'ye çıkabilir ama process stack overflow ile ölmez. Testteki sıralı 5.000 elemanda derinlik 13'ün altında kalıyor.

Hoare partition'ın dönüş değeri Lomuto'dan farklı: pivot'un son yeri değil, iki tarafın sınırı. Bu yüzden recursion [lo, p] ve [p + 1, hi] üzerinde, p'yi dışarıda bırakmadan yapılıyor. Lomuto'nun p - 1/p + 1 sınırlarını buraya taşımak, quick sort'un en klasik off-by-one hatası. Üç versiyon da aynı testten geçiyor: boş, tek elemanlı, hepsi eşit, sıralı, ters sıralı, çok tekrarlı ve int.MinValue ile int.MaxValue'yu da içeren rastgele girdiler.

$ dotnet test --project tests/Algorithms.Tests -- --filter-class Algorithms.Tests.QuickSortTests
tests/Algorithms.Tests/bin/Debug/net10.0/Algorithms.Tests.dll (net10.0|arm64) passed (626ms)

Test run summary: Passed!
  total: 6
  failed: 0
  succeeded: 6

.NET'in Array.Sort'u: Introsort

Quick sort pratikte genelde en hızlı karşılaştırmalı sıralama: yerinde çalışıyor, ardışık belleğe erişiyor, iç döngüsü çok sıkı. Ama en kötü durumu O(n²). Introsort (introspective sort) bunu çözmek için üç algoritmayı birleştiriyor ve .NET'in Array.Sort'u tam olarak bunu kullanıyor. Microsoft Learn'deki Remarks bölümüne göre:

• Partition boyutu 16 veya daha azsa insertion sort kullanılıyor.
• Partition sayısı 2 · log n'i aşarsa (n: sıralanan aralığın uzunluğu) heapsort'a geçiliyor.
• Diğer bütün durumlarda quick sort kullanılıyor.

Mantığı şu: quick sort normalde log n civarı derinlikte bitiyor. Derinlik bunun iki katını aşarsa, pivot'lar sürekli kötü seçiliyor demektir; introsort o noktada en kötü durumu da O(n log n) olan heapsort'a geçip kayıpları sınırlıyor. Küçük parçalarda da serinin önceki yazısında gördüğümüz insertion sort devreye giriyor. Sonuç her durumda O(n log n), sabitleri quick sort'unkine yakın. Doküman ayrıca bu sıralamanın unstable olduğunu açıkça yazıyor. Span<T> ve List<T> üzerindeki Sort da aynı algoritmayı kullanıyor. Heapsort'un kendisini serinin heap yazısında yazacağız.

Benchmark üç implementation'ı 10.000 elemanlık rastgele ve sıralı girdide karşılaştırıyor:

BenchmarkDotNet v0.15.8, macOS 27.0.1 (26A434) [Darwin 27.0.0]
Apple M5, 1 CPU, 10 logical and 10 physical cores
.NET SDK 10.0.402
  [Host] : .NET 10.0.13 (10.0.13, 10.0.1326.50504), Arm64 RyuJIT armv8.0-a

| Method             | N     | Input  | Mean         | Ratio  | Allocated |
|------------------- |------ |------- |-------------:|-------:|----------:|
| ArraySort          | 10000 | random |    157.76 us |   1.01 |         - |
| LomutoLastPivot    | 10000 | random |    226.81 us |   1.45 |         - |
| HoareMedianOfThree | 10000 | random |    204.24 us |   1.30 |         - |
|                    |       |        |              |        |           |
| ArraySort          | 10000 | sorted |     33.81 us |   1.00 |         - |
| LomutoLastPivot    | 10000 | sorted | 25,332.58 us | 749.48 |         - |
| HoareMedianOfThree | 10000 | sorted |     60.09 us |   1.78 |         - |

Açılıştaki ilk sorunun cevabı: rastgele girdide yüzde 45 geride kalan ders kitabı quick sort'u, sıralı girdide 749 kat yavaş, 25 ms. Median-of-three ile Hoare versiyonu sıralı girdide daha da hızlanıyor, çünkü her pivot tam ortanca. Array.Sort iki durumda da önde: sıralı girdide 34 µs. Ölçümler makinede başka işler çalışırken alındı; oranlara bak.

Karşılaştırmalı Sıralamanın Alt Sınırı

Introsort'tan daha iyisi var mı? Yalnızca "a, b'den küçük mü?" sorusunu sorarak sıralayan her algoritma için cevap hayır. Sezgisi şu: n elemanın n! farklı dizilişi var ve algoritma bunlardan doğru olanı bulmak zorunda. Her karşılaştırma iki cevaplı bir soru, yani olasılıkları en iyi ihtimalle yarıya indiriyor. n! olasılığı bire indirmek için en az log₂(n!) soru gerekiyor ve log₂(n!) yaklaşık n log₂ n. Bu yüzden comparison sort'lar için Ω(n log n) bir alt sınır; merge sort, heapsort ve introsort bu sınıra zaten ulaşıyor. Decision tree ile ispatı ve Ω notasyonunun anlamı Big-O ve Complexity serisinin "Big-O Notation Nedir" yazısında.

Bu sınırı aşmanın tek yolu karşılaştırma yapmamak: key'lerin yapısını, ör. küçük bir aralıktaki tamsayılar olduklarını, kullanmak.

Karşılaştırmadan Sıralamak: Counting ve Radix Sort

Bookstore'un online sınav modülünde 1 milyon öğrencinin 0–100 arası notları var. 101 farklı key için karşılaştırmaya gerek yok: her notun kaç kez geçtiğini say, sonra sayıları sırayla yaz. Counting sort'un stable versiyonu her key'in çıktıda nereden başlayacağını prefix sum ile hesaplıyor:

// [0, maxKey] aralığında key'ler: O(n + k) zaman, O(n + k) bellek, stable
public static T[] CountingSort<T>(T[] items, Func<T, int> key, int maxKey)
{
    int[] counts = new int[maxKey + 2];
    foreach (T item in items) counts[key(item) + 1]++;
    for (int k = 1; k < counts.Length; k++) counts[k] += counts[k - 1]; // counts[k] = key k'nin ilk slotu
    T[] output = new T[items.Length];
    foreach (T item in items) output[counts[key(item)]++] = item; // soldan sağa: stable
    return output;
}

[Fact]
public void CountingSort_Grades_IsStable()
{
    (string Name, int Grade)[] students = [("ada", 90), ("alan", 75), ("grace", 90), ("linus", 60), ("margaret", 75)];

    (string Name, int Grade)[] sorted = NonComparisonSorts.CountingSort(students, s => s.Grade, maxKey: 100);

    Assert.Equal(["linus", "alan", "margaret", "ada", "grace"], sorted.Select(s => s.Name));
}

Serinin önceki yazısındaki prefix sum burada yine karşımızda: counts önce frekans, sonra her key'in çıktıdaki başlangıç index'i. Element'leri girdideki sırayla yerleştirdiğimiz için aynı notu alan Ada ve Grace girdideki sırada kalıyor. Maliyet O(n + k); k, key aralığının büyüklüğü. k küçükse doğrusal, k büyükse (ör. 32-bit'in tamamı, 4 milyar) kullanılamaz.

Radix sort bu sınırı aşıyor: key'i parçalara (digit'lere) bölüp her parça için stable bir counting sort yapıyor, en anlamsız parçadan (LSD, least significant digit) başlayarak. 32-bit key'leri byte byte sıralayınca dört geçiş yetiyor ve her geçişte k yalnızca 256:

// 32-bit key'ler üzerinde LSD radix sort, geçiş başına bir byte: 4 stable counting geçişi
public static void RadixSort(uint[] items)
{
    uint[] buffer = new uint[items.Length];
    uint[] source = items, target = buffer;
    for (int shift = 0; shift < 32; shift += 8)
    {
        int[] counts = new int[257];
        foreach (uint x in source) counts[((x >> shift) & 0xFF) + 1]++;
        for (int k = 1; k < 257; k++) counts[k] += counts[k - 1];
        foreach (uint x in source) target[counts[(x >> shift) & 0xFF]++] = x;
        (source, target) = (target, source);
    }
    // 4 geçiş: sonuç yeniden "items"ta
}

Neden çalıştığı stability'ye dayanıyor: ikinci byte'a göre sıralarken, ikinci byte'ları eşit olan sayılar birinci byte'a göre kazandıkları sırayı koruyor. Dört geçişten sonra sayılar bütün byte'lara göre, yani değerlerine göre sıralı. Toplam iş 4 · (n + 256), yani O(n).

Benchmark 1 milyon elemanda iki karşılaştırma yapıyor: 0–100 arası notlar için Array.Sort ile counting sort, rastgele 32-bit key'ler için Array.Sort ile radix sort. Tablodaki oranlar notların Array.Sort'una göre; key satırlarını kendi aralarında karşılaştır:

| Method             | N       | Mean      | Ratio | Allocated |
|------------------- |-------- |----------:|------:|----------:|
| GradesArraySort    | 1000000 | 22.400 ms |  1.00 |         - |
| GradesCountingSort | 1000000 |  2.050 ms |  0.09 | 4000109 B |
| KeysArraySort      | 1000000 | 46.200 ms |  2.06 |         - |
| KeysRadixSort      | 1000000 |  3.782 ms |  0.17 | 4004777 B |

Counting sort notları Array.Sort'tan 11 kat hızlı sıralıyor (22,4 ms yerine 2,05 ms), radix sort 32-bit key'leri 12 kat hızlı (46,2 ms yerine 3,78 ms). Bedeli bellek: ikisi de n elemanlık ikinci bir array ayırıyor, yerinde çalışan Array.Sort hiç ayırmıyor. Ayrıca genel değiller: counting sort küçük bir key aralığı, radix sort sabit uzunluklu key'ler (tamsayı, sabit uzunluklu kod) istiyor. Ölçüm makinede başka işler çalışırken alındı.

Üretimde Dikkat

Comparer'ını tek tek kontrol et. Array.Sort geçersiz bir comparer'ı her zaman yakalamıyor. Dokümana göre .NET Framework 4.5'ten bu yana insertion sort ve heapsort geçersiz comparer'ı fark etmiyor ve sıralama başarılı tamamlanamazsa sonuç tanımsız. Taraflardan biri tek sayıysa her zaman "büyük" diyen bozuk bir comparer'la yaptığımız küçük deney bunu doğruluyor:

// bozuk comparer: taraflardan biri tekse "büyük" der (ne transitive ne antisimetrik)
Comparison<int> broken = (a, b) => a == b ? 0 : (a % 2 != 0 || b % 2 != 0) ? 1 : a.CompareTo(b);

n=   10: no exception, sorted=False, first items: 10, 9, 8, 7, 6, 5
n= 1000: no exception, sorted=False, first items: 353, 349, 347, 345, 315, 343

İki boyutta da exception yok, iki sonuç da sıralı değil. Hata sessiz: sıralı olduğu varsayılan bir listeyle sonra binary search yaparsan, serinin bir sonraki yazısında göreceğimiz gibi o da sessizce yanlış cevap veriyor. Comparer'ı property-based bir testle (rastgele üç değer için transitivity ve Compare(a, b) == -Compare(b, a)) doğrula.

Sıralama kriterin küçük bir tamsayı aralığıysa (durum kodu, puan, gün numarası) counting sort'u düşün; özellikle her istekte büyük bir listeyi tekrar tekrar sıralıyorsan. Değilse Array.Sort'a dokunma.

Sık Düşülen Tuzaklar

Comparison'da a - b. Açılıştaki ikinci sorunun cevabı:

a - b       : 2147483647, -2147483648, -10, 5
a.CompareTo : -2147483648, -10, 5, 2147483647

int.MaxValue - (-10) taşıyor ve negatif bir sayı veriyor; comparer'a göre int.MaxValue artık -10'dan küçük. Değerler küçükken hiç görünmeyen bu hata, sınır değerlerde ya da büyük ID'lerde ortaya çıkıyor. Her zaman a.CompareTo(b) ya da Comparer<T>.Default kullan.

Ders kitabı quick sort'unu production'a koymak. Son element'i pivot seçen versiyon sıralı girdide 749 kat yavaşlıyor ve büyük girdide stack overflow ile process'i öldürüyor. Kendi quick sort'unu yazman gerekiyorsa en azından median-of-three ve küçük tarafa recursion kullan.

Hoare partition'ı Lomuto sınırlarıyla kullanmak. Hoare'da p pivot'un son yeri değil; [lo, p - 1] ve [p + 1, hi] ile recursion, p'deki element'i hiçbir parçaya dahil etmez ve sonuç sessizce yanlış sıralı çıkar.

Counting sort'u geniş bir aralıkta kullanmak. Key'ler 0 ile 1 milyar arasındaysa counts 4 GB'lık bir array. k'yi n ile karşılaştırmadan counting sort seçme; geniş aralıkta radix sort ya da Array.Sort doğru seçim.

Küçük Bir Deneme

★☆☆ QuickSortBenchmarks'a RandomPivot'u ekle ve sıralı girdide ölç. Median-of-three ile arasındaki fark ne? Aynı benchmark'ı iki kez çalıştırınca sonuç değişiyor mu?

★★☆ Bütün element'leri eşit olan 10.000 elemanlık bir array'i Lomuto ve Hoare ile sırala ve MaxDepth'e bak. Lomuto neden burada da çöküyor? Üç yollu partition (Dijkstra'nın "Dutch national flag" yaklaşımı: küçük, eşit, büyük) ile düzelt.

★★★ Basit bir introsort yaz: Hoare quick sort'una derinlik sayacı ekle, derinlik 2 · log₂ n'i aşınca o parçayı heapsort'a (şimdilik PriorityQueue ile doldurup boşaltarak) devret, 16'dan küçük parçaları insertion sort'la bitir. Ders kitabı quick sort'unu öldüren sıralı girdide nasıl davranıyor?

Sıralamanın asıl ödülü arama: sıralı bir array'de her şeyi log n adımda bulabilirsin. Bir sonraki yazıda binary search'ü derinlemesine yazıyoruz: half-open aralıklarla invariant, lower ve upper bound, Array.BinarySearch'ün negatif dönüş değeri ve "cevap üzerinde binary search" ile minimum kargo kapasitesini bulmak.