Doğrusal Zamanlı Sıralama

Verimli sıralama algoritmalarını incelerken sağlam bir duvara çarptık: yalnızca elemanları birbiriyle karşılaştırarak çalışan hiçbir algoritma, en kötü durumda O(n log n)'den daha hızlı olamaz. Bu bir mühendislik kısıtı değil, matematiksel bir sınırdır. Peki bir milyon öğrencinin 0 ile 100 arasındaki sınav notlarını sıralamak için gerçekten n log n kadar iş yapmak zorunda mısın?

Postanede mektup ayıran bir memuru düşün. Önündeki yığını sıralarken iki mektubu alıp "hangisinin posta kodu daha küçük?" diye kıyaslamaz. Her mektubun koduna bir kez bakar ve onu doğrudan ilgili gözeneğe atar. Hiçbir karşılaştırma yapmadan, her mektuba yalnızca bir kez dokunarak işi bitirir. Bu dersteki algoritmaların hepsi aynı fikre dayanır: anahtarın değerini bir adres gibi kullanmak.

Bu dersin sonunda sayma sıralamasını (counting sort), taban sıralamasını (radix sort) ve kova sıralamasını (bucket sort) Go ile sıfırdan yazabileceksin. Her birinin hangi varsayıma dayandığını, bu varsayım bozulduğunda neden kötüleştiğini ve gerçek bir projede slices.Sort yerine ne zaman bunları seçmen gerektiğini de öğreneceksin.

Karşılaştırmasız sıralama fikri

Alt sınır neyi söylüyor, neyi söylemiyor?

Karşılaştırma tabanlı bir algoritma girdi hakkında bilgiyi yalnızca a < b gibi evet/hayır sorularıyla öğrenir. n elemanın n! farklı dizilişi vardır ve algoritma doğru çıktıyı üretebilmek için bunların hepsini birbirinden ayırt edebilmelidir. h tane evet/hayır sorusu en fazla 2ʰ farklı durumu ayırt edebilir. Dolayısıyla 2ʰ ≥ n! olmalıdır; buradan h ≥ log₂(n!) ≈ n log₂ n çıkar. Bu, karar ağacı argümanının özüdür.

Dikkat etmen gereken nokta şu: bu sınır sıralama problemi hakkında değil, hesaplama modeli hakkındadır. "Yalnızca karşılaştırma yaparsan en az bu kadar soru sorman gerekir" der. Bir algoritma count[x]++ gibi bir işlem yapabiliyorsa, tek adımda k yönlü bir dallanma gerçekleştirir: x değeri, k hücreden birini doğrudan seçer. Bu bir evet/hayır sorusu değildir; bu yüzden sayma argümanı bu algoritmalara uygulanmaz.

Bedava öğle yemeği de yoktur. Karşılaştırma yapmadan sıralayabilmek için anahtarlar hakkında ek bilgiye ihtiyaç duyarız:

Sayma sıralaması (counting sort)

Sezgi: çetele tutmak

Bir öğretmen 30 öğrencinin 1 ile 5 arasındaki karne notlarını sıralamak istiyor. Kâğıtları ikişer ikişer kıyaslamak yerine tahtaya beş sütun çizer ve her kâğıt için ilgili sütuna bir çentik atar. Sonra 1'lerin sütunundaki çentik kadar "1", 2'lerinki kadar "2" yazar. İş bitmiştir.

Aynı fikri [4, 2, 2, 8, 3, 3, 1] dizisine uygulayalım. Değerler 0 ile 8 arasında olduğu için dokuz hücrelik bir sayaç dizisi yeter:

girdi:   4  2  2  8  3  3  1

değer:   0  1  2  3  4  5  6  7  8
count:  [0  1  2  2  1  0  0  0  1]

çıktı:   1  2  2  3  3  4  8

İlk sürüm: yalnızca sayılar

package main

import "fmt"

// countingSort, 0 ile maxValue arasındaki tamsayıları sıralanmış yeni bir dilim olarak döndürür.
func countingSort(nums []int, maxValue int) []int {
	count := make([]int, maxValue+1)
	for _, x := range nums {
		count[x]++ // x değerini bir kez daha gördük
	}

	result := make([]int, 0, len(nums))
	for value, c := range count {
		for range c {
			result = append(result, value)
		}
	}
	return result
}

func main() {
	nums := []int{4, 2, 2, 8, 3, 3, 1}
	fmt.Println("girdi:", nums)
	fmt.Println("çıktı:", countingSort(nums, 8))
}

girdi: [4 2 2 8 3 3 1]
çıktı: [1 2 2 3 3 4 8]

Algoritma iki aşamadan oluşur. Sayma aşaması her elemana bir kez dokunur: O(n). Yazma aşamasında dış döngü k + 1 kez döner, iç döngülerin toplamı ise n eder: O(n + k). Hiçbir yerde < operatörü yok.

Bu sürümün bir kusuru var: elemanların kimliğini kaybediyoruz. Sıraladığımız şey çıplak sayılarsa sorun değil; iki tane 2 birbirinden ayırt edilemez. Ama öğrenci kayıtlarını nota göre sıralıyorsak, 85 alan Ayşe ile 85 alan Cem farklı kayıtlardır. Kayıtları taşımamız ve eşit notlu öğrencilerin başlangıçtaki sırasını korumamız, yani kararlı (stable) bir sıralama yapmamız gerekir.

Kararlı sürüm: önek toplamları ve sondan gezinme

Çözüm, sayaç dizisini önek toplamlarına (prefix sums) dönüştürmektir. Her v için count[v] += count[v-1] yaptıktan sonra count[v], anahtarı v veya daha küçük olan eleman sayısını gösterir. Bu da bize bir konum bilgisi verir: anahtarı v olan elemanların sonuncusu, çıktıda count[v] - 1 indeksine gitmelidir.

Bunu, eşit anahtarları harflerle etiketlediğimiz bir örnekle izleyelim. 2a ile 2b aynı anahtara sahip ama farklı kayıtlar:

indeks:   0    1    2    3    4    5    6    7
girdi:   2a    5   3a   0a   2b   3b   0b   3c

değer:     0   1   2   3   4   5
count:    [2   0   2   3   0   1]    her anahtardan kaç tane var
önek:     [2   2   4   7   7   8]    anahtarı ≤ v olan eleman sayısı

önek[3] = 7 şunu söyler: yedi elemanın anahtarı 3 veya daha küçüktür, dolayısıyla üç tane 3'lü eleman çıktıda 4, 5 ve 6. indeksleri kaplayacaktır. Şimdi girdiyi sondan başa gezip her elemanı --önek[anahtar] konumuna yerleştirelim:

Neden sondan başa? Girdiyi geriye doğru gezerken karşılaştığımız ilk 3'lü eleman (3c), girdideki son 3'lüdür ve 3'lülere ayrılan bölgenin son hücresine yerleşir. Ondan önce gelen 3b bir önceki hücreye, 3a ise ilk hücreye gider. Böylece a, b, c sırası korunur. Aynı kodu baştan sona gezecek şekilde yazsaydın 3a 6. hücreye, 3c 4. hücreye düşer ve eşit elemanların sırası ters dönerdi.

Şimdi gerçek kayıtlarla, 0–100 arası notlara sahip öğrencilerle çalışalım:

package main

import "fmt"

type Student struct {
	Name  string
	Score int // 0 ile 100 arasında
}

// sortByScore öğrencileri nota göre kararlı biçimde sıralar.
func sortByScore(students []Student) []Student {
	const maxScore = 100
	count := make([]int, maxScore+1)
	for _, s := range students {
		count[s.Score]++
	}
	// Önek toplamları: count[v] artık notu ≤ v olan öğrenci sayısı.
	for v := 1; v <= maxScore; v++ {
		count[v] += count[v-1]
	}

	result := make([]Student, len(students))
	// Sondan başa gezmek, eşit notlu öğrencilerin sırasını korur.
	for i := len(students) - 1; i >= 0; i-- {
		s := students[i]
		count[s.Score]--
		result[count[s.Score]] = s
	}
	return result
}

func main() {
	students := []Student{
		{"Ayşe", 85}, {"Burak", 70}, {"Cem", 85}, {"Deniz", 100},
		{"Ece", 70}, {"Fatih", 45}, {"Gül", 85},
	}
	for _, s := range sortByScore(students) {
		fmt.Printf("%-6s %3d\n", s.Name, s.Score)
	}
}

Fatih   45
Burak   70
Ece     70
Ayşe    85
Cem     85
Gül     85
Deniz  100

70 alan Burak listede Ece'den önce geliyordu, çıktıda da önce geliyor. 85 alan Ayşe, Cem ve Gül de ilk sıralarını korudu. Maliyeti aşama aşama toplayalım: sayma O(n), önek toplamları O(k), yerleştirme O(n). Bellekte ise k + 1 hücrelik sayaç dizisi ve n elemanlık sonuç dilimi var.

Negatif sayılar: kaydırma (offset)

count[x] ifadesi x negatifse panik oluşturur. Çözüm basit: en küçük değeri bul ve her değerden çıkar. Böylece [min, max] aralığı [0, max - min] aralığına kayar. Bu hile, sıfırdan uzakta toplanmış pozitif sayılar için de işe yarar: [1000, 1003, 1001] için 1004 değil, yalnızca 4 hücre gerekir.

package main

import (
	"fmt"
	"slices"
)

// countingSortRange negatif sayılar dahil herhangi bir tamsayı dilimini sıralar.
func countingSortRange(nums []int) []int {
	if len(nums) == 0 {
		return nil
	}
	lo, hi := slices.Min(nums), slices.Max(nums)
	count := make([]int, hi-lo+1) // aralığın genişliği kadar hücre

	for _, x := range nums {
		count[x-lo]++ // lo değeri 0. hücreye düşer
	}

	result := make([]int, 0, len(nums))
	for i, c := range count {
		for range c {
			result = append(result, i+lo) // kaydırmayı geri al
		}
	}
	return result
}

func main() {
	// Erzurum'da bir haftanın en düşük sıcaklıkları (°C)
	temps := []int{-12, 3, -5, 0, -12, 7, -1}
	fmt.Println(countingSortRange(temps))
	fmt.Println(countingSortRange([]int{1000, 1003, 1001}))
}

[-12 -12 -5 -1 0 3 7]
[1000 1001 1003]

k büyüdüğünde ne olur?

"Doğrusal zamanlı" etiketi yanıltıcı olabilir; gerçek maliyet O(n + k)'dir ve k burada değer aralığının genişliğidir. k, n ile aynı mertebedeyse (k = O(n)) algoritma gerçekten doğrusaldır. k çok büyükse maliyeti n değil k belirler:

Son satır felakettir: 64 bitlik bir sistemde her int 8 bayt tuttuğundan, bin sayı için yaklaşık 8 GB'lık bir sayaç dizisi ayırmaya çalışırsın.

Taban sıralaması (radix sort)

Sayma sıralaması 0..k aralığı küçükken harikadır. Peki 32 bitlik tamsayıları sıralamak istersek? k yaklaşık 4,3 milyar olur. Taban sıralaması bu sorunu, büyük bir anahtarı küçük parçalara (basamaklara) bölüp her parçayı ayrı ayrı sayma sıralamasıyla sıralayarak çözer. Her basamağın aralığı küçüktür: onluk tabanda 10, bayt tabanında 256.

Sezgi: tarihleri sıralamak

Elinde gün.ay.yıl biçiminde tarihler yazan kartlar olsun. Önce kartları güne göre kararlı biçimde sırala, sonra aya göre, en son yıla göre. Sonuç tarihe göre tamamen sıralıdır. Neden? Son sıralama en önemli alana, yıla göre yapıldı. Aynı yıldaki kartlar arasında önceki sıralamanın (ay) düzeni korundu; aynı yıl ve aydaki kartlar arasında ise ondan önceki sıralamanın (gün) düzeni. Bu yönteme en önemsiz basamaktan başlayan (LSD, least significant digit) taban sıralaması denir.

LSD taban sıralaması adım adım

[170, 45, 75, 90, 802, 24, 2, 66] dizisini onluk tabanda sıralayalım. En büyük sayı üç basamaklı olduğu için üç geçiş yapacağız; kısa sayıları baştaki sıfırlarla düşünmek işimizi kolaylaştırır. Her sütun bir geçişten sonraki durumu, kalın rakam da o geçişte bakılan basamağı gösteriyor:

2. geçişin sonucuna dikkatle bak: 170 ile 075'in onlar basamağı aynı (7) ve 170, 1. geçişte 075'ten önce geldiği için yine önde. Bu an için "yanlış" görünüyor, çünkü 170 > 75. Ama sorun değil; 3. geçiş yüzler basamağına bakarak bunu düzeltiyor. Öte yandan 075 ile 090'ın yüzler basamağı aynı (0) ve 3. geçiş aralarındaki sırayı, yani 2. geçişin onlar basamağına göre kurduğu doğru sırayı koruyor.

Doğruluğun arkasındaki değişmez (invariant) şudur: i. geçişten sonra dizi, sayıların son i basamağına göre sıralıdır. Tümevarımla gösterebiliriz. İki sayının i. basamağı farklıysa i. geçiş onları doğru sıraya koyar. Aynıysa kararlı geçiş, önceki geçişten gelen sıralarını korur; tümevarım hipotezine göre bu sıra da son i - 1 basamağa göre doğrudur.

package main

import (
	"fmt"
	"slices"
)

// sortByDigit, nums'u exp ile seçilen basamağa göre (1: birler, 10: onlar...) kararlı sıralar.
func sortByDigit(nums []int, exp int) []int {
	var count [10]int
	for _, x := range nums {
		count[x/exp%10]++
	}
	for d := 1; d < 10; d++ {
		count[d] += count[d-1]
	}
	out := make([]int, len(nums))
	for i := len(nums) - 1; i >= 0; i-- { // sondan başa: kararlı
		d := nums[i] / exp % 10
		count[d]--
		out[count[d]] = nums[i]
	}
	return out
}

// radixSort negatif olmayan tamsayıları LSD taban sıralamasıyla sıralar.
func radixSort(nums []int) []int {
	if len(nums) == 0 {
		return nums
	}
	maxValue := slices.Max(nums)
	for exp := 1; maxValue/exp > 0; exp *= 10 {
		nums = sortByDigit(nums, exp)
		fmt.Printf("basamak %-3d → %v\n", exp, nums)
	}
	return nums
}

func main() {
	nums := []int{170, 45, 75, 90, 802, 24, 2, 66}
	fmt.Println("girdi         ", nums)
	radixSort(nums)
}

girdi          [170 45 75 90 802 24 2 66]
basamak 1   → [170 90 802 2 24 45 75 66]
basamak 10  → [802 2 24 45 66 170 75 90]
basamak 100 → [2 24 45 66 75 90 170 802]

Radix sort için kararlılığın önemi

Yukarıdaki değişmezin ikinci yarısı, yani "basamaklar eşitse önceki sırayı koru" kısmı, tamamen iç sıralamanın kararlılığına dayanır. Kararlılık bozulursa önceki geçişlerin emeği çöpe gider. Bunu görmek için sortByDigit fonksiyonunu tek bir farkla yeniden yazalım: girdiyi baştan sona gezsin. Konum hesabı aynı kalır, ama eşit basamaklı elemanlar artık ters sırayla yerleşir.

package main

import "fmt"

// sortByDigit, stable false ise girdiyi baştan gezer ve eşit basamaklı elemanların sırasını ters çevirir.
func sortByDigit(nums []int, exp int, stable bool) []int {
	var count [10]int
	for _, x := range nums {
		count[x/exp%10]++
	}
	for d := 1; d < 10; d++ {
		count[d] += count[d-1]
	}
	out := make([]int, len(nums))
	place := func(x int) {
		d := x / exp % 10
		count[d]--
		out[count[d]] = x
	}
	if stable {
		for i := len(nums) - 1; i >= 0; i-- {
			place(nums[i])
		}
	} else {
		for _, x := range nums {
			place(x)
		}
	}
	return out
}

func radixSort(nums []int, stable bool) []int {
	for exp := 1; exp <= 100; exp *= 10 {
		nums = sortByDigit(nums, exp, stable)
	}
	return nums
}

func main() {
	nums := []int{170, 45, 75, 90, 802, 24, 2, 66}
	fmt.Println("kararlı iç sıralama:  ", radixSort(nums, true))
	fmt.Println("kararsız iç sıralama: ", radixSort(nums, false))
}

kararlı iç sıralama:   [2 24 45 66 75 90 170 802]
kararsız iç sıralama:  [90 75 66 45 24 2 170 802]

Kararsız sürümün çıktısı sıralı bile değil: yüzler basamağı 0 olan altı sayı tam ters sırada duruyor. Her geçiş yalnızca kendi basamağına bakıyor; o basamakta eşit olan sayıların önceki geçişlerde kazandığı sırayı ise rastgele (burada ters) bozuyor. Sonuçta yalnızca son geçişin basamağına göre sıralı bir dizi kalıyor. Bu yüzden radix sort'un içinde quick sort veya heap sort gibi kararsız bir algoritma kullanamazsın; iç sıralama neredeyse her zaman kararlı sayma sıralamasıdır.

Daha büyük taban: baytlarla sıralama

Onluk taban insanlar için doğaldır ama bilgisayar için değil. Basamağı çıkarmak için bölme ve mod işlemi gerekir, üstelik 32 bitlik bir sayı onluk tabanda 10 basamak tutabilir (en büyük değer 4.294.967.295). Tabanı 256 seçersek her "basamak" bir bayt olur ve (x >> shift) & 0xFF ile tek bir kaydırma ve maskeyle elde edilir. 32 bitlik bir sayı tam 4 bayttır, yani 4 geçiş yeter.

package main

import (
	"fmt"
	"math/rand/v2"
	"slices"
)

// radixSortUint32 dilimi yerinde sıralar: 4 geçiş, her geçişte bir bayt.
func radixSortUint32(nums []uint32) {
	buf := make([]uint32, len(nums))
	src, dst := nums, buf
	for shift := 0; shift < 32; shift += 8 {
		var count [256]int
		for _, x := range src {
			count[(x>>shift)&0xFF]++
		}
		// count[b] artık b baytının çıktıdaki başlangıç konumu.
		start := 0
		for b := range 256 {
			start, count[b] = start+count[b], start
		}
		for _, x := range src { // baştan gezip ilerleyerek yerleştir: kararlı
			b := (x >> shift) & 0xFF
			dst[count[b]] = x
			count[b]++
		}
		src, dst = dst, src
	}
	// Çift sayıda (4) takastan sonra sonuç yeniden nums içinde.
}

func main() {
	r := rand.New(rand.NewPCG(1, 2))
	nums := make([]uint32, 100_000)
	for i := range nums {
		nums[i] = r.Uint32()
	}
	want := slices.Clone(nums)
	slices.Sort(want)

	radixSortUint32(nums)
	fmt.Println("ilk üç:", nums[:3])
	fmt.Println("slices.Sort ile aynı mı?", slices.Equal(nums, want))
}

ilk üç: [72069 148852 164349]
slices.Sort ile aynı mı? true

Burada her geçişte yeni dilim ayırmak yerine iki tamponu (src ve dst) değiş tokuş ediyoruz; toplam ek bellek n eleman ve 256 hücrelik bir sayaç. Taban seçimi bir takastır:

Taban büyüdükçe geçiş sayısı azalır, ama her geçişte O(b) maliyetli önek toplamı hesabı yapılır ve sayaç dizisi işlemci önbelleğine sığmamaya başlar. 256 tabanı, küçük sayaç dizisi ve az geçiş arasında dengeli bir seçim olduğu için sık kullanılır.

Karmaşıklık

d geçişin her biri, b hücrelik sayaçla bir sayma sıralamasıdır:

Anahtar genişliği sabitse (32 bit için d = 4, b = 256) bu O(n) olur. Yine de şunu unutma: d, anahtarın bit sayısına bağlıdır. 64 bitlik anahtarlarda bayt tabanıyla 8 geçiş gerekir. "Doğrusal" sözü, anahtarların sabit genişlikte olduğu varsayımına dayanır.

MSD taban sıralaması

Taban sıralamasını tersinden, en önemli basamaktan (MSD, most significant digit) başlayarak da yapabilirsin. Önce ilk basamağa göre kovalara ayırırsın, sonra her kovayı kendi içinde bir sonraki basamağa göre özyinelemeli olarak sıralarsın. MSD, değişken uzunluklu string'leri sözlük sırasına dizmek için doğaldır ve farklı öneklere sahip anahtarlarda erken durabilir. Bedeli özyineleme ve çok sayıda küçük kovadır; pratikte küçük kovalar için insertion sort'a geçilir.

Kova sıralaması (bucket sort)

Sezgi: kütüphane rafları

Bir kütüphaneye yüzlerce kitap iade edildi. Görevli önce her kitabı yazarın soyadının baş harfine göre kabaca bir rafa koyar, sonra her rafı kendi içinde elle sıralar. Kitaplar harflere dengeli dağılmışsa her rafta birkaç kitap olur ve elle sıralamak çok hızlıdır. Kova sıralaması tam olarak budur.

Klasik kurulum şöyle: [0, 1) aralığına düzgün dağılmış n tane ondalıklı sayı var. n kova oluştur; x değeri int(x·n) numaralı kovaya gitsin. Her kovayı insertion sort ile sırala ve kovaları sırayla birleştir.

girdi: 0.78 0.17 0.39 0.26 0.72 0.94 0.21 0.12 0.23 0.68      (n = 10)

kova 0  [0.0, 0.1)
kova 1  [0.1, 0.2)   0.17 0.12        →  0.12 0.17
kova 2  [0.2, 0.3)   0.26 0.21 0.23   →  0.21 0.23 0.26
kova 3  [0.3, 0.4)   0.39
kova 4  [0.4, 0.5)
kova 5  [0.5, 0.6)
kova 6  [0.6, 0.7)   0.68
kova 7  [0.7, 0.8)   0.78 0.72        →  0.72 0.78
kova 8  [0.8, 0.9)
kova 9  [0.9, 1.0)   0.94

çıktı: 0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94

Neden doğru? x ≤ y ise int(x·n) ≤ int(y·n) olur; yani küçük sayı asla büyük sayıdan daha sonraki bir kovaya düşmez. Farklı kovalardaki sayılar kova sırasıyla, aynı kovadakiler insertion sort ile doğru dizilir.

package main

import "fmt"

// insertionSort küçük dilimler için hızlı ve kararlıdır.
func insertionSort(a []float64) {
	for i := 1; i < len(a); i++ {
		key := a[i]
		j := i - 1
		for j >= 0 && a[j] > key {
			a[j+1] = a[j]
			j--
		}
		a[j+1] = key
	}
}

// bucketSort [0, 1) aralığındaki sayıları sıralar.
func bucketSort(nums []float64) []float64 {
	n := len(nums)
	buckets := make([][]float64, n)
	for _, x := range nums {
		i := min(int(x*float64(n)), n-1) // x = 0.78, n = 10 → 7. kova
		buckets[i] = append(buckets[i], x)
	}

	result := make([]float64, 0, n)
	for _, b := range buckets {
		insertionSort(b)
		result = append(result, b...)
	}
	return result
}

func main() {
	nums := []float64{0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68}
	fmt.Println(bucketSort(nums))
}

[0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94]

min(..., n-1) koruması, kayan nokta yuvarlaması ya da hatalı veri yüzünden x tam 1.0 çıkarsa indeksin taşmasını engeller.

Ortalama ve en kötü durum

Değerler gerçekten düzgün dağılmışsa her kovaya ortalama bir eleman düşer. Insertion sort bir kovada O(nᵢ²) iş yapar ve nᵢ kovadaki eleman sayısıdır. Olasılık hesabı, kova boyutunun karesinin beklenen değerinin 2 - 1/n olduğunu, yani sabit kaldığını gösterir. n kova üzerinden toplayınca beklenen toplam iş O(n) olur.

Varsayım bozulursa tablo tamamen değişir. Aşağıdaki program aynı sayıda değeri önce düzgün dağılımla, sonra hepsi dar bir aralığa sıkışmış hâlde üretiyor ve insertion sort'un kaç kaydırma yaptığını sayıyor:

package main

import (
	"fmt"
	"math/rand/v2"
)

// bucketStats kova sıralaması yapar; en büyük kova boyutunu ve toplam kaydırma sayısını döndürür.
func bucketStats(nums []float64) (largest, shifts int) {
	n := len(nums)
	buckets := make([][]float64, n)
	for _, x := range nums {
		i := min(int(x*float64(n)), n-1)
		buckets[i] = append(buckets[i], x)
	}
	for _, b := range buckets {
		largest = max(largest, len(b))
		for i := 1; i < len(b); i++ {
			key := b[i]
			j := i - 1
			for j >= 0 && b[j] > key {
				b[j+1] = b[j]
				j--
				shifts++
			}
			b[j+1] = key
		}
	}
	return largest, shifts
}

func main() {
	r := rand.New(rand.NewPCG(1, 2))
	const n = 10_000
	uniform := make([]float64, n)
	skewed := make([]float64, n)
	for i := range n {
		uniform[i] = r.Float64()                 // [0, 1) aralığına düzgün dağılmış
		skewed[i] = 0.5 + r.Float64()/float64(n) // hepsi aynı kovaya düşer
	}

	l, s := bucketStats(uniform)
	fmt.Printf("düzgün dağılım:  en büyük kova %5d, kaydırma %10d\n", l, s)
	l, s = bucketStats(skewed)
	fmt.Printf("sıkışık dağılım: en büyük kova %5d, kaydırma %10d\n", l, s)
}

düzgün dağılım:  en büyük kova     6, kaydırma       2472
sıkışık dağılım: en büyük kova 10000, kaydırma   25044942

Düzgün dağılımda iş n mertebesinde kalıyor; sıkışık dağılımda ise bütün elemanlar tek kovaya düştüğü için algoritma düpedüz n elemanlık bir insertion sort'a dönüşüyor ve kaydırma sayısı yaklaşık n²/4'e çıkıyor.

String'leri sıralamak

Uzunluğa göre sıralama

Kelime uzunlukları küçük tamsayılardır; en uzun kelimenin uzunluğu k olarak düşünülebilir. Bu yüzden kelimeleri uzunluğa göre sıralamak için kararlı sayma sıralaması biçilmiş kaftandır ve eşit uzunluktaki kelimeler girdideki sıralarını korur. Türkçe için bir tuzak var: len("çilek") 5 değil 6 döndürür, çünkü ç UTF-8'de iki bayt kaplar. "Uzunluk" derken harf sayısını kastediyorsan utf8.RuneCountInString kullanmalısın.

package main

import (
	"fmt"
	"unicode/utf8"
)

// sortByLength kelimeleri, length fonksiyonunun verdiği uzunluğa göre kararlı biçimde sıralar.
func sortByLength(words []string, length func(string) int) []string {
	maxLen := 0
	for _, w := range words {
		maxLen = max(maxLen, length(w))
	}
	count := make([]int, maxLen+1)
	for _, w := range words {
		count[length(w)]++
	}
	for l := 1; l <= maxLen; l++ {
		count[l] += count[l-1]
	}
	out := make([]string, len(words))
	for i := len(words) - 1; i >= 0; i-- {
		l := length(words[i])
		count[l]--
		out[count[l]] = words[i]
	}
	return out
}

func byteLen(s string) int { return len(s) }

func main() {
	words := []string{"elma", "şeftali", "kivi", "üzüm", "armut", "çilek", "incir", "muz"}
	fmt.Println("harf sayısına göre:", sortByLength(words, utf8.RuneCountInString))
	fmt.Println("bayt sayısına göre:", sortByLength(words, byteLen))
}

harf sayısına göre: [muz elma kivi üzüm armut çilek incir şeftali]
bayt sayısına göre: [muz elma kivi armut incir üzüm çilek şeftali]

Harf sayısına göre üzüm dört harfli kelimelerle, çilek beş harflilerle birlikte; bayt sayısına göre ise ikisi de daha sona kaymış.

Sabit uzunluklu anahtarlar

Tüm anahtarlar aynı uzunluktaysa string'i bir "basamak dizisi" gibi görebilirsin: her karakter bir basamaktır ve en önemsiz basamak en sağdaki karakterdir. Havalimanı kodları (IATA) üç büyük harften oluştuğu için güzel bir örnek:

package main

import (
	"fmt"
	"slices"
)

// sortFixedWidth, hepsi width bayt uzunluğunda olan ASCII anahtarları LSD taban sıralamasıyla sıralar.
func sortFixedWidth(keys []string, width int) []string {
	src := slices.Clone(keys)
	dst := make([]string, len(keys))
	for pos := width - 1; pos >= 0; pos-- { // en sağdaki karakterden başla
		var count [256]int
		for _, k := range src {
			count[k[pos]]++
		}
		for c := 1; c < 256; c++ {
			count[c] += count[c-1]
		}
		for i := len(src) - 1; i >= 0; i-- {
			c := src[i][pos]
			count[c]--
			dst[count[c]] = src[i]
		}
		src, dst = dst, src
		fmt.Printf("%d. karaktere göre: %v\n", pos+1, src)
	}
	return src
}

func main() {
	codes := []string{"SAW", "IST", "ESB", "ADB", "AYT", "TZX", "ADA", "DLM", "BJV", "ASR"}
	sortFixedWidth(codes, 3)
}

3. karaktere göre: [ADA ESB ADB DLM ASR IST AYT BJV SAW TZX]
2. karaktere göre: [SAW ADA ADB BJV DLM ESB ASR IST AYT TZX]
1. karaktere göre: [ADA ADB ASR AYT BJV DLM ESB IST SAW TZX]

Son satır tam bir sözlük sırası. ADA ile ADB'nin ilk iki karakteri aynı; aralarındaki sırayı 3. karakterin geçişi belirledi ve sonraki kararlı geçişler bu sırayı korudu. Değişken uzunluklu string'lerde kısa anahtarları, tüm karakterlerden küçük sayılan hayali bir karakterle sağdan doldurmuş gibi davranabilir ya da MSD yaklaşımını seçebilirsin.

Karşılaştırma tabanlı sıralamalarla karşılaştırma

Karşılaştırma tabanlı algoritmaların en büyük gücü genelliktir: cmp.Compare ile sıralanabilen her şeyi, istediğin karşılaştırma fonksiyonuyla sıralarlar. Doğrusal sıralamalar ise anahtarın içine bakabildikleri için hızlıdır ama her veri tipine uygulanamazlar.

Ne zaman kullanılmalı?

Gerçek dünyadan örnekler

• Yaşlar: İnsan yaşı 0 ile 150 arasındadır. Milyonlarca kişilik bir nüfus kaydını yaşa göre sıralamak, 151 hücrelik bir sayaçla yapılabilir.
• Sınav puanları: 0–100 arası notlar ya da yarım puanlık adımlarla verilen notlar (değeri 2 ile çarpıp 0–200 aralığına taşıyarak) kararlı sayma sıralaması için idealdir. Kararlılık sayesinde eşit puanlılar, önceden sıralandıkları başka bir ölçüte (ör. başvuru sırasına) göre düzenli kalır.
• Posta kodları, sabit uzunluklu kimlikler: Türkiye'deki posta kodları beş basamaklıdır; onluk tabanda 5 geçişle ya da 100.000 hücrelik tek bir sayma sıralamasıyla dizilebilir.
• IP adresleri: Bir IPv4 adresi tam dört bayttır, yani 256 tabanında dört basamaklı bir sayıdır. Günlük (log) dosyalarındaki milyonlarca adresi sıralamak için doğal bir aday.
• Rastgele üretilmiş değerler: Simülasyonlarda [0, 1) aralığında düzgün dağılan sayılar kova sıralamasına uygundur.

IP adresi örneği, string sıralamasının neden yanlış olduğunu da gösteriyor:

package main

import (
	"fmt"
	"net/netip"
	"slices"
)

// sortIPv4 adresleri dört geçişli, 256 tabanlı LSD taban sıralamasıyla sıralar.
func sortIPv4(addrs []netip.Addr) []netip.Addr {
	src := slices.Clone(addrs)
	dst := make([]netip.Addr, len(addrs))
	for octet := 3; octet >= 0; octet-- { // en önemsiz oktet: sonuncusu
		var count [256]int
		for _, a := range src {
			count[a.As4()[octet]]++
		}
		for b := 1; b < 256; b++ {
			count[b] += count[b-1]
		}
		for i := len(src) - 1; i >= 0; i-- {
			b := src[i].As4()[octet]
			count[b]--
			dst[count[b]] = src[i]
		}
		src, dst = dst, src
	}
	return src
}

func main() {
	raw := []string{"192.168.1.10", "10.0.0.1", "192.168.1.2", "172.16.5.4",
		"10.0.0.255", "8.8.8.8", "192.168.0.254", "1.1.1.1"}

	asText := slices.Clone(raw)
	slices.Sort(asText)
	fmt.Println("string olarak:", asText)

	addrs := make([]netip.Addr, len(raw))
	for i, s := range raw {
		addrs[i] = netip.MustParseAddr(s)
	}
	sorted := sortIPv4(addrs)
	fmt.Println("sayı olarak:  ", sorted)

	slices.SortFunc(addrs, netip.Addr.Compare)
	fmt.Println("Compare ile aynı mı?", slices.Equal(sorted, addrs))
}

string olarak: [1.1.1.1 10.0.0.1 10.0.0.255 172.16.5.4 192.168.0.254 192.168.1.10 192.168.1.2 8.8.8.8]
sayı olarak:   [1.1.1.1 8.8.8.8 10.0.0.1 10.0.0.255 172.16.5.4 192.168.0.254 192.168.1.2 192.168.1.10]
Compare ile aynı mı? true

String sıralamasında 192.168.1.10, 192.168.1.2'den önce geliyor, 8.8.8.8 ise en sona düşüyor; çünkü karşılaştırma karakter karakter yapılıyor. Taban sıralaması adresi dört sayı olarak gördüğü için doğru sonucu veriyor.

Pratik notlar

• Bellek: Buradaki algoritmaların hiçbiri yerinde değildir; O(n) ek tampon ve sayaç dizisi ister. Bellek kısıtlı ortamlarda bu belirleyici olabilir.
• Küçük girdiler: n küçükse sayaç dizisini hazırlamanın ve ek tampon ayırmanın sabit maliyeti kazancı yer. Birkaç yüz eleman için slices.Sort genellikle yeterli ve daha basittir; emin olmak istiyorsan kendi verinle benchmark yaz.
• Standart kütüphane: Go'nun standart kütüphanesinde hazır bir radix sort yok; slices.Sort karşılaştırma tabanlı pdqsort kullanır. Doğrusal sıralamaya ihtiyacın varsa kendin yazarsın, ki bu dersten sonra zor değil.
• Karar listesi:
  1. Anahtarlar küçük bir aralıkta tamsayı mı (aralık n mertebesinde)? Sayma sıralaması.
  2. Anahtarlar sabit genişlikte mi (32/64 bit sayılar, IP adresleri, sabit uzunluklu kodlar) ve n çok mu büyük? Taban sıralaması.
  3. Değerler dağılımı bilinen ondalıklı sayılar mı? Kova sıralaması.
  4. Hiçbiri değilse ya da özel bir karşılaştırma gerekiyorsa: slices.Sort, slices.SortFunc veya kararlılık için slices.SortStableFunc.

Sık yapılan hatalar

• Aralığı kontrol etmemek: make([]int, maxValue+1) satırını körü körüne yazmak, büyük bir değer geldiğinde gigabaytlarca bellek ayırmaya ya da bellek hatasına yol açar. Önce max - min değerini ölç.
• Negatif sayıları unutmak: count[x] ifadesi x < 0 için index out of range paniği üretir. En küçük değeri kaydırma olarak kullan.
• Kararlılığı yanlışlıkla bozmak: Önek toplamlı sürümde girdiyi baştan gezip count[v]-- yapmak eşit elemanların sırasını ters çevirir. Ya sondan gez ya da başlangıç konumlarıyla ileriye doğru yerleştir.
• Radix sort'un içinde kararsız sıralama kullanmak: Her geçiş önceki geçişlerin kurduğu sırayı korumalıdır; aksi hâlde sonuç sıralı bile olmaz.
• exp *= 10 taşması: maxValue/exp > 0 döngüsünde değerler math.MaxInt'e yakınsa exp taşar ve döngü yanlış davranır. Sabit genişlikli tamsayılarda bayt tabanlı, kaydırmalı sürümü tercih et.
• Kova indeksini sınırlamamak: int(x*float64(n)) ifadesi x = 1.0 veya aralık dışı bir değer için n ya da daha büyük bir indeks üretir. Girdiyi doğrula ya da min(i, n-1) ile sınırla.
• Bayt uzunluğunu harf sayısı sanmak: Türkçe metinde len bayt sayar. Harf sayısı için utf8.RuneCountInString kullan.
• Her yerde doğrusal sıralama kullanmak: Küçük girdilerde ve genel karşılaştırma gerektiren durumlarda slices.Sort hem daha basit hem de çoğu zaman daha hızlıdır.

Alıştırmalar

package main

import "fmt"

func sortColors(nums []int) {
	var count [3]int
	for _, x := range nums {
		count[x]++
	}
	i := 0
	for color, c := range count {
		for range c {
			nums[i] = color
			i++
		}
	}
}

func main() {
	nums := []int{2, 0, 2, 1, 1, 0}
	sortColors(nums)
	fmt.Println(nums)

	single := []int{1}
	sortColors(single)
	fmt.Println(single)
}

[0 0 1 1 2 2]
[1]

package main

import "fmt"

func topKFrequent(nums []int, k int) []int {
	freq := make(map[int]int)
	for _, x := range nums {
		freq[x]++
	}

	// buckets[f]: tam f kez geçen elemanlar, girdideki ilk görünme sırasıyla.
	buckets := make([][]int, len(nums)+1)
	placed := make(map[int]bool)
	for _, x := range nums {
		if !placed[x] {
			placed[x] = true
			buckets[freq[x]] = append(buckets[freq[x]], x)
		}
	}

	result := make([]int, 0, k)
	for f := len(nums); f >= 1 && len(result) < k; f-- {
		for _, x := range buckets[f] {
			if len(result) == k {
				break
			}
			result = append(result, x)
		}
	}
	return result
}

func main() {
	nums := []int{4, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5}
	fmt.Println(topKFrequent(nums, 2))
	fmt.Println(topKFrequent(nums, 4))
}

[4 3]
[4 3 2 1]

package main

import "fmt"

func hIndex(citations []int) int {
	n := len(citations)
	count := make([]int, n+1) // count[c]: tam c atıf alan makale sayısı (c ≥ n olanlar n'de)
	for _, c := range citations {
		count[min(c, n)]++
	}
	atLeast := 0 // en az h atıf almış makale sayısı
	for h := n; h >= 0; h-- {
		atLeast += count[h]
		if atLeast >= h {
			return h
		}
	}
	return 0
}

func main() {
	fmt.Println(hIndex([]int{3, 0, 6, 1, 5}))
	fmt.Println(hIndex([]int{1, 3, 1}))
	fmt.Println(hIndex([]int{100}))
	fmt.Println(hIndex([]int{0, 0}))
}

3
1
1
0

package main

import (
	"fmt"
	"slices"
)

func maximumGap(nums []int) int {
	n := len(nums)
	if n < 2 {
		return 0
	}
	lo, hi := slices.Min(nums), slices.Max(nums)
	if lo == hi {
		return 0
	}

	size := max(1, (hi-lo)/(n-1)) // kova genişliği
	bucketCount := (hi-lo)/size + 1
	bucketMin := make([]int, bucketCount)
	bucketMax := make([]int, bucketCount)
	used := make([]bool, bucketCount)

	for _, x := range nums {
		i := (x - lo) / size
		if !used[i] {
			bucketMin[i], bucketMax[i], used[i] = x, x, true
			continue
		}
		bucketMin[i] = min(bucketMin[i], x)
		bucketMax[i] = max(bucketMax[i], x)
	}

	best, prevMax := 0, bucketMax[0] // lo her zaman 0. kovada
	for i := 1; i < bucketCount; i++ {
		if !used[i] {
			continue
		}
		best = max(best, bucketMin[i]-prevMax)
		prevMax = bucketMax[i]
	}
	return best
}

func main() {
	fmt.Println(maximumGap([]int{3, 6, 9, 1}))
	fmt.Println(maximumGap([]int{10}))
	fmt.Println(maximumGap([]int{1, 1000000000, 500}))
	fmt.Println(maximumGap([]int{5, 2, 8, 12, 3}))
}

3
0
999999500
4

Kısa sınav

Özet

• Karşılaştırma tabanlı sıralamaların Ω(n log n) alt sınırı yalnızca evet/hayır sorularıyla çalışan modele aittir; anahtarı indeks olarak kullanan algoritmalar bu modelin dışındadır.
• Sayma sıralaması O(n + k) zamanda çalışır. Önek toplamları ve sondan gezinme sayesinde kararlıdır; negatif değerler için en küçük değer kadar kaydırma yapılır.
• k değer aralığıdır. k, n'den çok büyükse sayma sıralaması hem zaman hem bellek açısından felakete dönüşür.
• LSD taban sıralaması anahtarları basamak basamak, en önemsizden başlayarak sıralar ve O(d·(n + b)) sürer. Doğruluğu tamamen iç sıralamanın kararlı olmasına bağlıdır.
• 256 tabanı, basamak çıkarmayı bir kaydırma ve maskeye indirir; 32 bitlik anahtarlar 4 geçişte sıralanır.
• Kova sıralaması düzgün dağılımda ortalama O(n), bütün değerler tek kovaya düştüğünde O(n²) sürer.
• Türkçe string'lerde uzunluk derken harf sayısını kastediyorsan len değil utf8.RuneCountInString kullan; sabit uzunluklu kodlar karakter karakter LSD ile sıralanabilir.
• Varsayımlar sağlanmıyorsa ya da n küçükse slices.Sort genellikle doğru tercihtir; doğrusal sıralamalar büyük ve dar aralıklı ya da sabit genişlikli verilerde parlar.