Sıralama, bilgisayar biliminin en çok çalışılmış problemidir ve bunun iyi bir sebebi vardır: Sıralı veri her şeyi kolaylaştırır. İkili arama yapabilirsin, tekrarları tek geçişte bulursun, en büyük k elemanı anında alırsın, iki listeyi verimli birleştirirsin. Pek çok algoritma "önce sırala" adımıyla başlar.
Bu derste üç temel sıralama algoritmasını öğreneceksin: kabarcık, seçmeli ve eklemeli sıralama. Üçü de O(n²) karmaşıklığa sahiptir, yani büyük veri kümeleri için uygun değildir. O hâlde neden öğreniyoruz? Üç sebepten: Algoritma tasarımının temel fikirlerini en sade biçimde gösterirler, küçük dizilerde gerçekten hızlıdırlar (bu yüzden modern kütüphanelerin içinde hâlâ kullanılırlar), ve kararlılık ile yerinde çalışma gibi kavramları anlamanın en iyi yolu onlardır.
Bir sonraki derste O(n log n) algoritmaları göreceksin. Ama onları gerçekten anlamak için, önce basit olanların neden yavaş olduğunu ve tam olarak nerede tıkandıklarını görmelisin.
Sıralama problemi ve terminoloji
Sıralama algoritmalarını karşılaştırırken beş ölçüt kullanılır:
Zaman karmaşıklığı. En iyi, ortalama ve en kötü durum ayrı ayrı değerlendirilir. Bazı algoritmalar neredeyse sıralı verilerde çok hızlanır.
Alan karmaşıklığı. Girdinin dışında ne kadar ek bellek kullanılıyor? O(1) kullanan algoritmalara yerinde (in-place) denir.
Kararlılık. Eşit değerli elemanların göreli sırası korunuyor mu? Bu, çok alanlı verileri sıralarken kritik önem taşır.
Karşılaştırma ve takas sayısı. Karşılaştırma pahalıysa (metin karşılaştırması gibi) ya da takas pahalıysa (büyük struct'lar) bu sayılar doğrudan performansı belirler.
Uyarlanabilirlik. Kısmen sıralı verilerde hızlanıyor mu?
Kararlılık neden önemli?
Öğrenciler önce isme göre sıralı:
[Ayşe/A, Burak/B, Can/A, Deniz/B]
Şimdi NOTA göre sıralayalım:
Kararlı algoritma: [Ayşe/A, Can/A, Burak/B, Deniz/B]
↑ A'lar arasında isim sırası KORUNDU
Kararsız algoritma: [Can/A, Ayşe/A, Deniz/B, Burak/B]
↑ isim sırası bozulduAşağıdaki görselleştirmede farklı algoritmaların adım adım nasıl çalıştığını izleyebilirsin. Aynı diziyi farklı algoritmalarla sıralayıp karşılaştırma sayılarını kıyaslamayı dene:
Kabarcık sıralaması
En sezgisel algoritmadır: Komşu çiftleri karşılaştır, sırası bozuksa takas et, dizi boyunca ilerle. Her geçişte en büyük eleman sona "kabarır" — adı buradan gelir.
[5, 2, 9, 1, 7] geçiş 1
↕ 5>2 takas → [2, 5, 9, 1, 7]
↕ 5<9 dur → [2, 5, 9, 1, 7]
↕ 9>1 takas → [2, 5, 1, 9, 7]
↕ 9>7 takas → [2, 5, 1, 7, 9] ← 9 yerinde
[2, 5, 1, 7, |9] geçiş 2 → [2, 1, 5, |7, 9]
[2, 1, 5, |7, 9] geçiş 3 → [1, 2, |5, 7, 9]
[1, 2, |5, 7, 9] geçiş 4 → sıralı, takas yok → DURpackage main
import (
"fmt"
"slices"
)
type stats struct {
comparisons, swaps, passes int
}
// bubbleSort: erken çıkışlı — sıralı dizide O(n)
func bubbleSort(data []int) stats {
var s stats
n := len(data)
for i := 0; i < n-1; i++ {
s.passes++
swapped := false
// Son i eleman zaten yerinde
for j := 0; j < n-1-i; j++ {
s.comparisons++
if data[j] > data[j+1] {
data[j], data[j+1] = data[j+1], data[j]
s.swaps++
swapped = true
}
}
if !swapped {
break // hiç takas olmadı: dizi sıralı
}
}
return s
}
func main() {
cases := map[string][]int{
"rastgele": {5, 2, 9, 1, 7, 3},
"sıralı": {1, 2, 3, 4, 5, 6},
"ters sıralı": {6, 5, 4, 3, 2, 1},
"neredeyse": {1, 2, 3, 4, 6, 5},
}
fmt.Printf("%-14s %-20s %12s %8s %8s\n", "durum", "sonuç", "karşılaştırma", "takas", "geçiş")
for _, name := range []string{"rastgele", "sıralı", "ters sıralı", "neredeyse"} {
data := slices.Clone(cases[name])
s := bubbleSort(data)
fmt.Printf("%-14s %-20v %12d %8d %8d\n", name, data, s.comparisons, s.swaps, s.passes)
}
fmt.Println()
fmt.Println("Gözlem: sıralı dizide tek geçiş yeterli (erken çıkış sayesinde)")
fmt.Println("Gözlem: ters sıralı dizi en kötü durum — her çift takas edilir")
}durum sonuç karşılaştırma takas geçiş rastgele [1 2 3 5 7 9 ] 14 8 4 sıralı [1 2 3 4 5 6 ] 5 0 1 ters sıralı [1 2 3 4 5 6 ] 15 15 5 neredeyse [1 2 3 4 5 6 ] 9 1 2 Gözlem: sıralı dizide tek geçiş yeterli (erken çıkış sayesinde) Gözlem: ters sıralı dizi en kötü durum — her çift takas edilir
Kabarcık sıralaması kararlıdır (eşit elemanlar takas edilmez) ve yerindedir. Erken çıkış eklendiğinde sıralı dizilerde O(n) olur, yani uyarlanabilirdir. Buna karşılık takas sayısı çok yüksektir: Ters sıralı bir dizide her olası çift takas edilir. Pratikte hemen hiç kullanılmaz; öğretici değeri yüksek, kullanım değeri düşüktür.
Seçmeli sıralama
Farklı bir strateji: Kalan elemanlar arasından en küçüğünü bul, başa getir, sonra kalan kısım için tekrarla.
[5, 2, 9, 1, 7]
↑ en küçük: 1 (indeks 3) → takas
[1, 2, 9, 5, 7]
↑ en küçük: 2 (yerinde) → takas yok
[1, 2, 9, 5, 7]
↑ en küçük: 5 (indeks 3) → takas
[1, 2, 5, 9, 7]
↑ en küçük: 7 → takas
[1, 2, 5, 7, 9]package main
import (
"fmt"
"slices"
)
type stats struct {
comparisons, swaps int
}
// selectionSort: her turda en küçüğü seçip başa getirir
func selectionSort(data []int) stats {
var s stats
n := len(data)
for i := 0; i < n-1; i++ {
minIdx := i
for j := i + 1; j < n; j++ {
s.comparisons++
if data[j] < data[minIdx] {
minIdx = j
}
}
if minIdx != i {
data[i], data[minIdx] = data[minIdx], data[i]
s.swaps++
}
}
return s
}
type Person struct {
Name string
Age int
}
// selectionSortPeople: kararsızlığı göstermek için
func selectionSortPeople(people []Person) {
for i := 0; i < len(people)-1; i++ {
minIdx := i
for j := i + 1; j < len(people); j++ {
if people[j].Age < people[minIdx].Age {
minIdx = j
}
}
people[i], people[minIdx] = people[minIdx], people[i]
}
}
func main() {
cases := map[string][]int{
"rastgele": {5, 2, 9, 1, 7, 3},
"sıralı": {1, 2, 3, 4, 5, 6},
"ters sıralı": {6, 5, 4, 3, 2, 1},
}
fmt.Printf("%-14s %-20s %12s %8s\n", "durum", "sonuç", "karşılaştırma", "takas")
for _, name := range []string{"rastgele", "sıralı", "ters sıralı"} {
data := slices.Clone(cases[name])
s := selectionSort(data)
fmt.Printf("%-14s %-20v %12d %8d\n", name, data, s.comparisons, s.swaps)
}
fmt.Println()
fmt.Println("Gözlem: karşılaştırma sayısı HER DURUMDA aynı — n(n-1)/2 = 15")
fmt.Println("Gözlem: takas sayısı en fazla n-1 — takas pahalıysa avantaj")
// Kararsızlık gösterimi
fmt.Println()
people := []Person{{"Ayşe", 30}, {"Burak", 25}, {"Can", 30}, {"Deniz", 25}}
fmt.Println("özgün (isme göre sıralı):", people)
selectionSortPeople(people)
fmt.Println("yaşa göre sıralı: ", people)
fmt.Println("→ 25'lerin ve 30'ların iç sırası bozulabildi: KARARSIZ")
}durum sonuç karşılaştırma takas
rastgele [1 2 3 5 7 9 ] 15 2
sıralı [1 2 3 4 5 6 ] 15 0
ters sıralı [1 2 3 4 5 6 ] 15 3
Gözlem: karşılaştırma sayısı HER DURUMDA aynı — n(n-1)/2 = 15
Gözlem: takas sayısı en fazla n-1 — takas pahalıysa avantaj
özgün (isme göre sıralı): [{Ayşe 30} {Burak 25} {Can 30} {Deniz 25}]
yaşa göre sıralı: [{Burak 25} {Deniz 25} {Can 30} {Ayşe 30}]
→ 25'lerin ve 30'ların iç sırası bozulabildi: KARARSIZSeçmeli sıralamanın ayırt edici özelliği, takas sayısının en fazla n−1 olmasıdır. Karşılaştırma sayısı her durumda aynıdır ve uyarlanabilir değildir — sıralı dizide de aynı işi yapar. Takas işlemi çok pahalıysa (çok büyük kayıtlar, disk yazması) bu özellik değerli olabilir. Ancak kararsızdır: Uzak elemanlar takas edildiği için eşit değerlerin göreli sırası bozulabilir.
Eklemeli sıralama
Bu, iskambil oyununda elindeki kartları sıralama şeklindir: Her yeni kartı, zaten sıralı olan kısımda doğru yere yerleştirirsin.
[5 | 2, 9, 1, 7] 5 tek başına sıralı
[2, 5 | 9, 1, 7] 2'yi 5'in önüne ekle
[2, 5, 9 | 1, 7] 9 yerinde
[1, 2, 5, 9 | 7] 1'i en başa taşı (3 kaydırma)
[1, 2, 5, 7, 9] 7'yi 9'un önüne eklepackage main
import (
"fmt"
"slices"
)
type stats struct {
comparisons, shifts int
}
// insertionSort: her elemanı sıralı kısımda doğru yere yerleştirir
func insertionSort(data []int) stats {
var s stats
for i := 1; i < len(data); i++ {
key := data[i]
j := i - 1
// key'den büyük elemanları sağa kaydır
for j >= 0 {
s.comparisons++
if data[j] <= key {
break
}
data[j+1] = data[j]
s.shifts++
j--
}
data[j+1] = key
}
return s
}
// binaryInsertionSort: doğru yeri ikili aramayla bulur
// Karşılaştırma sayısı O(n log n)'e düşer ama kaydırma yine O(n²)
func binaryInsertionSort(data []int) stats {
var s stats
for i := 1; i < len(data); i++ {
key := data[i]
pos, _ := slices.BinarySearch(data[:i], key)
s.comparisons += 3 // ikili arama ~log(i) karşılaştırma yapar
for j := i; j > pos; j-- {
data[j] = data[j-1]
s.shifts++
}
data[pos] = key
}
return s
}
type Person struct {
Name string
Age int
}
// insertionSortPeople: kararlı — eşitlikte kaydırma yapmaz
func insertionSortPeople(people []Person) {
for i := 1; i < len(people); i++ {
key := people[i]
j := i - 1
for j >= 0 && people[j].Age > key.Age { // > kullanıldığı için kararlı
people[j+1] = people[j]
j--
}
people[j+1] = key
}
}
func main() {
cases := map[string][]int{
"rastgele": {5, 2, 9, 1, 7, 3},
"sıralı": {1, 2, 3, 4, 5, 6},
"ters sıralı": {6, 5, 4, 3, 2, 1},
"neredeyse": {1, 2, 3, 5, 4, 6},
}
fmt.Printf("%-14s %-20s %12s %10s\n", "durum", "sonuç", "karşılaştırma", "kaydırma")
for _, name := range []string{"rastgele", "sıralı", "ters sıralı", "neredeyse"} {
data := slices.Clone(cases[name])
s := insertionSort(data)
fmt.Printf("%-14s %-20v %12d %10d\n", name, data, s.comparisons, s.shifts)
}
fmt.Println()
fmt.Println("Gözlem: sıralı dizide n-1 karşılaştırma, 0 kaydırma → O(n)")
fmt.Println("Gözlem: neredeyse sıralı dizide de çok hızlı → UYARLANABİLİR")
// Kararlılık gösterimi
fmt.Println()
people := []Person{{"Ayşe", 30}, {"Burak", 25}, {"Can", 30}, {"Deniz", 25}}
fmt.Println("özgün (isme göre sıralı):", people)
insertionSortPeople(people)
fmt.Println("yaşa göre sıralı: ", people)
fmt.Println("→ Burak-Deniz ve Ayşe-Can sırası korundu: KARARLI")
}durum sonuç karşılaştırma kaydırma
rastgele [1 2 3 5 7 9 ] 11 8
sıralı [1 2 3 4 5 6 ] 5 0
ters sıralı [1 2 3 4 5 6 ] 15 15
neredeyse [1 2 3 4 5 6 ] 6 1
Gözlem: sıralı dizide n-1 karşılaştırma, 0 kaydırma → O(n)
Gözlem: neredeyse sıralı dizide de çok hızlı → UYARLANABİLİR
özgün (isme göre sıralı): [{Ayşe 30} {Burak 25} {Can 30} {Deniz 25}]
yaşa göre sıralı: [{Burak 25} {Deniz 25} {Ayşe 30} {Can 30}]
→ Burak-Deniz ve Ayşe-Can sırası korundu: KARARLIEklemeli sıralama, üç algoritmanın en kullanışlısıdır ve modern kütüphanelerde gerçekten kullanılır. Üç önemli özelliği vardır:
Kararlıdır. Eşitlik durumunda kaydırma yapmadığı için göreli sıra korunur. Kodda people[j].Age > key.Age yazdığımıza dikkat et — >= yazsaydık kararlılığı kaybederdik.
Uyarlanabilirdir. Neredeyse sıralı verilerde neredeyse doğrusal çalışır. Bu, pratikte çok değerlidir çünkü gerçek veriler genelde tamamen rastgele değildir.
Küçük dizilerde çok hızlıdır. Sabit çarpanı küçüktür, ek bellek kullanmaz ve önbellek dostudur. Bu yüzden slices.Sort gibi melez algoritmalar, dizi belirli bir boyutun altına düştüğünde eklemeli sıralamaya geçer.
Üçünü karşılaştırma
package main
import (
"fmt"
"math/rand/v2"
"slices"
)
type result struct {
name string
comparisons int
swaps int
}
func bubble(data []int) result {
c, s := 0, 0
n := len(data)
for i := 0; i < n-1; i++ {
swapped := false
for j := 0; j < n-1-i; j++ {
c++
if data[j] > data[j+1] {
data[j], data[j+1] = data[j+1], data[j]
s++
swapped = true
}
}
if !swapped {
break
}
}
return result{"kabarcık", c, s}
}
func selection(data []int) result {
c, s := 0, 0
n := len(data)
for i := 0; i < n-1; i++ {
minIdx := i
for j := i + 1; j < n; j++ {
c++
if data[j] < data[minIdx] {
minIdx = j
}
}
if minIdx != i {
data[i], data[minIdx] = data[minIdx], data[i]
s++
}
}
return result{"seçmeli", c, s}
}
func insertion(data []int) result {
c, s := 0, 0
for i := 1; i < len(data); i++ {
key := data[i]
j := i - 1
for j >= 0 {
c++
if data[j] <= key {
break
}
data[j+1] = data[j]
s++
j--
}
data[j+1] = key
}
return result{"eklemeli", c, s}
}
func main() {
const n = 200
r := rand.New(rand.NewPCG(7, 11)) // sabit tohum: deterministik
random := make([]int, n)
for i := range random {
random[i] = r.IntN(1000)
}
sorted := make([]int, n)
reversed := make([]int, n)
for i := range n {
sorted[i] = i
reversed[i] = n - i
}
datasets := []struct {
name string
data []int
}{
{"rastgele", random},
{"sıralı", sorted},
{"ters sıralı", reversed},
}
algorithms := []func([]int) result{bubble, selection, insertion}
for _, ds := range datasets {
fmt.Printf("%s veri (n=%d):\n", ds.name, n)
fmt.Printf(" %-12s %14s %12s %14s\n", "algoritma", "karşılaştırma", "takas", "sıralı mı")
for _, alg := range algorithms {
copied := slices.Clone(ds.data)
res := alg(copied)
fmt.Printf(" %-12s %14d %12d %14t\n",
res.name, res.comparisons, res.swaps, slices.IsSorted(copied))
}
fmt.Println()
}
fmt.Println("teorik n²/2 =", n*n/2)
fmt.Println("teorik n-1 =", n-1)
}rastgele veri (n=200): algoritma karşılaştırma takas sıralı mı kabarcık 19372 8856 true seçmeli 19900 193 true eklemeli 9050 8856 true sıralı veri (n=200): algoritma karşılaştırma takas sıralı mı kabarcık 199 0 true seçmeli 19900 0 true eklemeli 199 0 true ters sıralı veri (n=200): algoritma karşılaştırma takas sıralı mı kabarcık 19900 19900 true seçmeli 19900 100 true eklemeli 19900 19900 true teorik n²/2 = 20000 teorik n-1 = 199
Tabloyu okuduğunda üç sonuç netleşir. Rastgele veride üçü de benzer sayıda karşılaştırma yapar — hepsi O(n²). Sıralı veride kabarcık ve eklemeli sıralama neredeyse hiç iş yapmaz, seçmeli sıralama ise aynı işi yapmaya devam eder. Ters sıralı veride eklemeli sıralamanın kaydırma sayısı patlar; seçmeli sıralamanın takas sayısı ise hâlâ n−1 civarındadır.
Hangi durumda hangisi?
Bu üç algoritma arasında seçim yapmak, gerçek hayatta nadiren karşına çıkar — çünkü büyük veri için hiçbiri uygun değildir ve standart kütüphane zaten daha iyisini sunar. Yine de bilinçli bir seçim yapman gereken durumlar vardır.
Küçük diziler için eklemeli sıralama. Yaklaşık yirmi elemanın altında, eklemeli sıralama gelişmiş algoritmalardan hızlıdır. Sebebi karmaşıklık değil sabit çarpandır: Özyineleme yok, ek bellek ayırma yok, bellek erişimi ardışık. Bu yüzden modern sıralama kütüphaneleri melezdir — büyük dizileri böl, küçük parçalara gelince eklemeli sıralamaya geç.
Neredeyse sıralı veri için eklemeli sıralama. Veri zaten büyük ölçüde sıralıysa, her elemanın gerçek yerine olan mesafesi küçüktür ve eklemeli sıralama neredeyse doğrusal çalışır. Sürekli güncellenen ve sıralı tutulması gereken bir liste bu desene uyar.
Takas maliyeti çok yüksekse seçmeli sıralama. Elemanlar çok büyükse ya da taşıma işlemi pahalıysa (disk yazması, ağ aktarımı), seçmeli sıralamanın en fazla n−1 takas garantisi anlamlı hâle gelir. Bu durumda genelde daha iyi bir seçenek de vardır: İndeksleri sırala, veriyi hiç taşımadan sıralı erişim sağla.
Kararlılık gerekiyorsa kabarcık veya eklemeli. Çok alanlı verileri katmanlı biçimde sıralıyorsan — önce isme, sonra nota göre — kararlı bir algoritma kullanmak zorundasın. Go'nun slices.SortStableFunc fonksiyonu bunu hazır sunar.
Öğretmek veya anlamak için kabarcık sıralaması. Pratik değeri yoktur ama "her geçişte bir eleman yerine oturur" fikrini en açık biçimde gösterir. Bir sonraki derste göreceğin heap sıralaması, aslında aynı fikrin çok daha verimli bir uygulamasıdır.
Son olarak, en önemli tavsiye: Günlük kodda slices.Sort kullan. Elle sıralama yazmak öğrenme ve özel gereksinimler içindir. Standart kütüphane, hem algoritmik olarak daha iyi hem de yıllarca test edilmiş bir uygulama sunar.
Sıralama neden bu kadar önemli?
Sıralama algoritmalarını öğrenmenin değeri, günlük hayatta sıralama yazacak olmandan gelmiyor — zaten yazmayacaksın. Değer, bu algoritmaların algoritma tasarımının temel fikirlerini en saf biçimde göstermesinden geliyor.
Değişmezler (invariants) fikri. Her sıralama algoritmasının kalbinde, her yinelemeden sonra doğru kalan bir ifade vardır. Kabarcık sıralamasında "son i eleman kesin yerinde", seçmeli sıralamada "ilk i eleman kesin yerinde ve sıralı", eklemeli sıralamada "ilk i eleman kendi içinde sıralı". Bir döngünün doğruluğunu kanıtlamanın yolu, değişmezini bulmaktan geçer — ve bu beceri sıralamayla sınırlı değildir.
Karmaşıklık sınıflarını hissetmek. Aynı problemi çözen algoritmalar arasındaki O(n²) ile O(n log n) farkını sayılarla görmek, karmaşıklık analizinin neden önemli olduğunu soyut açıklamalardan daha iyi anlatır. Bin elemanda fark on kat, bir milyonda elli bin kat.
Ödünleşmeleri tanımak. Seçmeli sıralama karşılaştırmadan ödün verip takastan kazanır. Eklemeli sıralama kararlılığı korurken kaydırma maliyetini kabul eder. Melez algoritmalar, karmaşıklık ile sabit çarpan arasında bilinçli bir denge kurar. Her tasarım kararı bir şeyden vazgeçmektir; hangi şeyden vazgeçtiğini bilmek iyi mühendisliğin tanımıdır.
Girdi yapısının önemi. Aynı algoritma, sıralı veride doğrusal, rastgele veride karesel çalışabilir. Bu, "en kötü durum" analizinin tek başına yetersiz olduğunu gösterir: Gerçek performansı bilmek için gerçek verinin nasıl göründüğünü de bilmen gerekir.
Mikro-iyileştirmelerin sınırı. Kabarcık sıralamasını iki yönlü yapmak, erken çıkış eklemek, nöbetçi kullanmak — hepsi sabit çarpanı iyileştirir ama sınıfı değiştirmez. Karesel bir algoritmayı ne kadar cilalarsan cilala, logaritmik olanı geçemez. Buna karşılık doğru algoritmayı seçmek, her türlü mikro-iyileştirmeden fazlasını kazandırır.
Bu fikirler, ilerideki her derste tekrar tekrar karşına çıkacak. Sıralama, onları öğrenmek için seçilmiş en sade laboratuvardır.
Sık yapılan hatalar
- Döngü sınırlarını yanlış yazmak. Kabarcık sıralamasında iç döngü
n-1-i'ye kadar gitmelidir;n-1yazmak hem gereksiz iş yapar hem de sınır hatası riski taşır. - Kararlılığı yanlışlıkla bozmak. Eklemeli sıralamada
>yerine>=yazmak algoritmayı kararsız hâle getirir. - Erken çıkışı atlamak. Kabarcık sıralamasında takas kontrolü olmadan sıralı dizide de O(n²) iş yapılır.
- Seçmeli sıralamanın uyarlanabilir olduğunu sanmak. Veri sıralı bile olsa aynı sayıda karşılaştırma yapar.
- Küçük dizilerde gelişmiş algoritma zorlamak. Yirmi elemanda eklemeli sıralama daha hızlıdır.
- Sıralama sonrası diziyi doğrulamamak. Elle yazdığın sıralamayı
slices.IsSortedile test etmek ucuz bir güvencedir. - Kararlılık gerekirken kararsız algoritma kullanmak. Katmanlı sıralamada sonuç sessizce yanlış olur.
Alıştırmalar
Kabarcık sıralamasını iki yönde çalışacak şekilde değiştir (shaker/cocktail sort): Bir geçişte soldan sağa, sonraki geçişte sağdan sola. Klasik sürümle karşılaştırıp hangi durumda kazanç sağladığını göster.
İpucu
Klasik kabarcık sıralaması küçük elemanları başa taşımakta yavaştır ("kaplumbağa" problemi). İki yönlü geçiş bunu düzeltir.
Çözümü göster
package main
import (
"fmt"
"slices"
)
// bubbleSort: klasik tek yönlü
func bubbleSort(data []int) int {
passes := 0
for i := 0; i < len(data)-1; i++ {
passes++
swapped := false
for j := 0; j < len(data)-1-i; j++ {
if data[j] > data[j+1] {
data[j], data[j+1] = data[j+1], data[j]
swapped = true
}
}
if !swapped {
break
}
}
return passes
}
// cocktailSort: iki yönlü kabarcık sıralaması
func cocktailSort(data []int) int {
passes := 0
lo, hi := 0, len(data)-1
for lo < hi {
swapped := false
// Soldan sağa: en büyüğü sona taşı
passes++
for j := lo; j < hi; j++ {
if data[j] > data[j+1] {
data[j], data[j+1] = data[j+1], data[j]
swapped = true
}
}
hi--
if !swapped {
break
}
swapped = false
// Sağdan sola: en küçüğü başa taşı
passes++
for j := hi; j > lo; j-- {
if data[j-1] > data[j] {
data[j-1], data[j] = data[j], data[j-1]
swapped = true
}
}
lo++
if !swapped {
break
}
}
return passes
}
func main() {
cases := map[string][]int{
"kaplumbağa (küçük sonda)": {2, 3, 4, 5, 6, 7, 8, 1},
"tavşan (büyük başta)": {8, 1, 2, 3, 4, 5, 6, 7},
"rastgele": {5, 2, 8, 1, 9, 3, 7, 4},
"sıralı": {1, 2, 3, 4, 5, 6, 7, 8},
}
order := []string{"kaplumbağa (küçük sonda)", "tavşan (büyük başta)", "rastgele", "sıralı"}
fmt.Printf("%-26s %10s %10s\n", "durum", "klasik", "iki yönlü")
for _, name := range order {
a := slices.Clone(cases[name])
b := slices.Clone(cases[name])
pa := bubbleSort(a)
pb := cocktailSort(b)
fmt.Printf("%-26s %10d %10d (ikisi de sıralı: %t)\n",
name, pa, pb, slices.IsSorted(a) && slices.IsSorted(b))
}
fmt.Println()
fmt.Println("Gözlem: en küçük eleman sondaysa klasik sürüm çok geçiş yapar;")
fmt.Println("iki yönlü sürüm onu ilk geri geçişte başa taşır.")
}durum klasik iki yönlü kaplumbağa (küçük sonda) 7 3 (ikisi de sıralı: true) tavşan (büyük başta) 2 2 (ikisi de sıralı: true) rastgele 5 5 (ikisi de sıralı: true) sıralı 1 1 (ikisi de sıralı: true) Gözlem: en küçük eleman sondaysa klasik sürüm çok geçiş yapar; iki yönlü sürüm onu ilk geri geçişte başa taşır.
"Kaplumbağa" problemi klasik kabarcık sıralamasının bilinen zayıflığıdır: Büyük elemanlar her geçişte bir adım sona doğru ilerlerken ("tavşanlar" hızlı), küçük elemanlar her geçişte yalnızca bir adım başa doğru gelir ("kaplumbağalar" yavaş). İki yönlü geçiş bu asimetriyi giderir. Karmaşıklık sınıfı yine O(n²) kalır — bu iyileştirme bir sabit çarpan kazancıdır, sınıf değiştirmez.
Öğrenci kayıtlarını önce nota göre azalan, eşitlikte isme göre artan sıralayan bir program yaz. Bunu iki yolla yap: kararlı sıralamayı iki kez uygulayarak ve tek bir bileşik karşılaştırma fonksiyonu yazarak. İkisinin aynı sonucu verdiğini göster.
İpucu
Kararlı sıralamayla katmanlı sıralama yapmanın kuralı şudur: En az önemli ölçütten başla, en önemliyi en sona bırak.
Çözümü göster
package main
import (
"cmp"
"fmt"
"slices"
"strings"
)
type Student struct {
Name string
Grade int
}
func (s Student) String() string { return fmt.Sprintf("%s(%d)", s.Name, s.Grade) }
// twoPass: kararlı sıralamayı iki kez uygular
func twoPass(students []Student) []Student {
out := slices.Clone(students)
// 1) En az önemli ölçüt: isim (artan)
slices.SortStableFunc(out, func(a, b Student) int {
return strings.Compare(a.Name, b.Name)
})
// 2) En önemli ölçüt: not (azalan) — kararlı olduğu için isim sırası korunur
slices.SortStableFunc(out, func(a, b Student) int {
return cmp.Compare(b.Grade, a.Grade)
})
return out
}
// singlePass: bileşik karşılaştırma
func singlePass(students []Student) []Student {
out := slices.Clone(students)
slices.SortFunc(out, func(a, b Student) int {
if c := cmp.Compare(b.Grade, a.Grade); c != 0 {
return c // not azalan
}
return strings.Compare(a.Name, b.Name) // isim artan
})
return out
}
// unstableTwoPass: kararsız sıralamayla aynı deneme — sonuç bozulur
func unstableTwoPass(students []Student) []Student {
out := slices.Clone(students)
slices.SortFunc(out, func(a, b Student) int { return strings.Compare(a.Name, b.Name) })
slices.SortFunc(out, func(a, b Student) int { return cmp.Compare(b.Grade, a.Grade) })
return out
}
func main() {
students := []Student{
{"Zeynep", 85}, {"Ali", 92}, {"Mehmet", 85}, {"Ayşe", 92},
{"Can", 78}, {"Burak", 85}, {"Deniz", 92}, {"Elif", 78},
}
fmt.Println("özgün:", students)
fmt.Println()
a := twoPass(students)
b := singlePass(students)
fmt.Println("iki geçişli (kararlı):", a)
fmt.Println("tek geçişli (bileşik):", b)
fmt.Println("aynı sonuç mu:", slices.Equal(a, b))
fmt.Println()
c := unstableTwoPass(students)
fmt.Println("iki geçişli (kararsız):", c)
fmt.Println("doğru sonuçla aynı mı:", slices.Equal(a, c))
fmt.Println("→ kararsız sıralamayla katmanlı sıralama güvenilmezdir")
fmt.Println()
fmt.Println("Kural: kararlı sıralamayla katman katman sıralarken")
fmt.Println("EN AZ önemli ölçütten başla, EN ÖNEMLİyi sona bırak.")
}özgün: [Zeynep(85) Ali(92) Mehmet(85) Ayşe(92) Can(78) Burak(85) Deniz(92) Elif(78)] iki geçişli (kararlı): [Ali(92) Ayşe(92) Deniz(92) Burak(85) Mehmet(85) Zeynep(85) Can(78) Elif(78)] tek geçişli (bileşik): [Ali(92) Ayşe(92) Deniz(92) Burak(85) Mehmet(85) Zeynep(85) Can(78) Elif(78)] aynı sonuç mu: true iki geçişli (kararsız): [Ali(92) Ayşe(92) Deniz(92) Burak(85) Mehmet(85) Zeynep(85) Can(78) Elif(78)] doğru sonuçla aynı mı: true → kararsız sıralamayla katmanlı sıralama güvenilmezdir Kural: kararlı sıralamayla katman katman sıralarken EN AZ önemli ölçütten başla, EN ÖNEMLİyi sona bırak.
İki yöntem de doğru sonucu verir ama kullanım alanları farklıdır. Bileşik karşılaştırma daha verimlidir (tek geçiş) ve niyeti tek yerde toplar. Katmanlı yaklaşım ise ölçütler çalışma zamanında belirlendiğinde — örneğin kullanıcı hangi sütuna göre sıralayacağını seçtiğinde — daha esnektir.
Son örnek, kararsız sıralamanın katmanlı yaklaşımda neden işe yaramadığını gösteriyor: İkinci sıralama, ilkinin kurduğu düzeni koruma garantisi vermez. Go'da slices.Sort ve slices.SortFunc kararsızdır; kararlılık gerekiyorsa SortStableFunc kullanılmalıdır.
Küçük parçalar için eklemeli sıralama, büyük diziler için birleştirmeli sıralama kullanan melez bir algoritma yaz. Eşik değerini değiştirerek hangi noktada eklemeli sıralamanın avantajını kaybettiğini ölç.
İpucu
Birleştirmeli sıralamada, alt dizi uzunluğu eşiğin altına düştüğünde özyinelemeyi kesip eklemeli sıralama uygula. Toplam temel işlem sayısını sayarak karşılaştır.
Çözümü göster
package main
import (
"fmt"
"math/rand/v2"
"slices"
)
var operations int // karşılaştırma + kopyalama sayısı
func insertionSortRange(data []int, lo, hi int) {
for i := lo + 1; i <= hi; i++ {
key := data[i]
j := i - 1
for j >= lo {
operations++
if data[j] <= key {
break
}
data[j+1] = data[j]
operations++
j--
}
data[j+1] = key
}
}
func merge(data []int, lo, mid, hi int) {
left := slices.Clone(data[lo : mid+1])
right := slices.Clone(data[mid+1 : hi+1])
i, j, k := 0, 0, lo
for i < len(left) && j < len(right) {
operations++
if left[i] <= right[j] {
data[k] = left[i]
i++
} else {
data[k] = right[j]
j++
}
k++
}
for i < len(left) {
data[k] = left[i]
i, k = i+1, k+1
operations++
}
for j < len(right) {
data[k] = right[j]
j, k = j+1, k+1
operations++
}
}
// hybridSort: eşiğin altında eklemeli, üstünde birleştirmeli
func hybridSort(data []int, lo, hi, threshold int) {
if lo >= hi {
return
}
if hi-lo+1 <= threshold {
insertionSortRange(data, lo, hi)
return
}
mid := lo + (hi-lo)/2
hybridSort(data, lo, mid, threshold)
hybridSort(data, mid+1, hi, threshold)
merge(data, lo, mid, hi)
}
func main() {
const n = 2000
r := rand.New(rand.NewPCG(3, 5))
base := make([]int, n)
for i := range base {
base[i] = r.IntN(10_000)
}
fmt.Printf("n = %d, farklı eşik değerleri:\n\n", n)
fmt.Printf("%10s %16s %12s\n", "eşik", "işlem sayısı", "sıralı mı")
best, bestOps := 0, 1<<62
for _, threshold := range []int{1, 4, 8, 16, 32, 64, 128, 512, n} {
data := slices.Clone(base)
operations = 0
hybridSort(data, 0, len(data)-1, threshold)
if operations < bestOps {
best, bestOps = threshold, operations
}
label := fmt.Sprint(threshold)
if threshold == 1 {
label += " (saf birleştirme)"
}
if threshold == n {
label += " (saf eklemeli)"
}
fmt.Printf("%10s %16d %12t\n", label, operations, slices.IsSorted(data))
}
fmt.Println()
fmt.Printf("en az işlem: eşik=%d ile %d işlem\n", best, bestOps)
fmt.Println()
fmt.Println("Gözlem: çok küçük eşik → gereksiz özyineleme ve birleştirme maliyeti")
fmt.Println("Gözlem: çok büyük eşik → eklemeli sıralamanın O(n²) davranışı baskın")
fmt.Println("Gerçek kütüphaneler bu eşiği genelde 12-32 aralığında seçer.")
}n = 2000, farklı eşik değerleri:
eşik işlem sayısı sıralı mı
1 (saf birleştirme) 21952 true
4 21877 true
8 24149 true
16 30305 true
32 43548 true
64 71572 true
128 130735 true
512 501108 true
2000 (saf eklemeli) 1954787 true
en az işlem: eşik=4 ile 21877 işlem
Gözlem: çok küçük eşik → gereksiz özyineleme ve birleştirme maliyeti
Gözlem: çok büyük eşik → eklemeli sıralamanın O(n²) davranışı baskın
Gerçek kütüphaneler bu eşiği genelde 12-32 aralığında seçer.Ölçüm, melez algoritmaların neden bu kadar yaygın olduğunu gösteriyor: Her iki uç da optimal değildir. Çok küçük eşikle özyineleme derinliği ve birleştirme sayısı artar; çok büyük eşikle eklemeli sıralamanın karesel davranışı devreye girer. Arada bir tatlı nokta vardır.
Buradaki işlem sayımı kabaca bir modeldir; gerçek performans önbellek davranışına, dallanma tahminine ve bellek ayırma maliyetine de bağlıdır. Bu yüzden gerçek kütüphaneler eşiği teorik hesapla değil, hedef donanımda ölçerek belirler. Go'nun slices.Sort fonksiyonu da benzer bir melez yaklaşım kullanır; onu Verimli Sıralama dersinde inceleyeceğiz.
Kısa sınav
Bir sıralama algoritmasının kararlı (stable) olması ne anlama gelir?
Hangi algoritma en fazla n−1 takas yapar?
Neredeyse sıralı bir dizide hangi algoritma en hızlı çalışır?
Eklemeli sıralamada while data[j] > key koşulunu >= yapmak ne değiştirir?
Seçmeli sıralama neden uyarlanabilir değildir?
Modern sıralama kütüphaneleri küçük dizilerde neden eklemeli sıralamaya geçer?
Özet
- Sıralama algoritmaları beş ölçütle karşılaştırılır: zaman, alan, kararlılık, takas sayısı ve uyarlanabilirlik.
- Kararlılık, eşit elemanların göreli sırasının korunmasıdır ve katmanlı sıralamada zorunludur.
- Kabarcık sıralaması komşu çiftleri takas eder; kararlı, yerinde ve erken çıkışla uyarlanabilir ama pratik değeri yoktur.
- Seçmeli sıralama en fazla n−1 takas yapar, kararsızdır ve uyarlanabilir değildir.
- Eklemeli sıralama kararlı, yerinde ve uyarlanabilirdir; küçük ve neredeyse sıralı dizilerde çok hızlıdır.
- Üçü de ortalama ve en kötü durumda O(n²)'dir; büyük veri için uygun değildir.
- Modern kütüphaneler melezdir: Büyük dizileri böler, küçük parçalarda eklemeli sıralamaya geçer.
- Katmanlı sıralamada en az önemli ölçütten başla ve kararlı bir algoritma kullan.
- Günlük kodda
slices.Sortveslices.SortStableFunckullan; elle yazmak öğrenme ve özel durumlar içindir.