Verimli Sıralama Algoritmaları

package main

import (
	"fmt"
	"slices"
)

var merges, comparisons int

// merge: iki sıralı dilimi birleştirir — O(n)
func merge(left, right []int) []int {
	out := make([]int, 0, len(left)+len(right))
	i, j := 0, 0

	for i < len(left) && j < len(right) {
		comparisons++
		if left[i] <= right[j] { // <= kullanıldığı için KARARLI
			out = append(out, left[i])
			i++
		} else {
			out = append(out, right[j])
			j++
		}
	}
	out = append(out, left[i:]...)
	out = append(out, right[j:]...)
	merges++
	return out
}

// mergeSort: böl, fethet, birleştir
func mergeSort(data []int) []int {
	if len(data) <= 1 {
		return data
	}
	mid := len(data) / 2
	left := mergeSort(slices.Clone(data[:mid]))
	right := mergeSort(slices.Clone(data[mid:]))
	return merge(left, right)
}

// mergeSortInPlace: tek yardımcı tampon kullanır — daha az bellek ayırma
func mergeSortInPlace(data, buffer []int, lo, hi int) {
	if hi-lo <= 1 {
		return
	}
	mid := lo + (hi-lo)/2
	mergeSortInPlace(data, buffer, lo, mid)
	mergeSortInPlace(data, buffer, mid, hi)

	i, j, k := lo, mid, lo
	for i < mid && j < hi {
		if data[i] <= data[j] {
			buffer[k] = data[i]
			i++
		} else {
			buffer[k] = data[j]
			j++
		}
		k++
	}
	for i < mid {
		buffer[k] = data[i]
		i, k = i+1, k+1
	}
	for j < hi {
		buffer[k] = data[j]
		j, k = j+1, k+1
	}
	copy(data[lo:hi], buffer[lo:hi])
}

func main() {
	data := []int{5, 2, 9, 1, 7, 3, 8, 4, 6}
	fmt.Println("girdi:", data)

	sorted := mergeSort(slices.Clone(data))
	fmt.Println("sonuç:", sorted)
	fmt.Printf("birleştirme sayısı: %d, karşılaştırma: %d\n", merges, comparisons)

	// Yerinde sürüm
	inPlace := slices.Clone(data)
	buffer := make([]int, len(inPlace))
	mergeSortInPlace(inPlace, buffer, 0, len(inPlace))
	fmt.Println("tampon kullanan sürüm:", inPlace)
	fmt.Println("iki sürüm aynı mı:", slices.Equal(sorted, inPlace))

	// Karmaşıklık gözlemi
	fmt.Println()
	fmt.Printf("%10s %14s %14s %12s\n", "n", "karşılaştırma", "n log₂ n", "oran")
	for _, n := range []int{16, 64, 256, 1024, 4096} {
		big := make([]int, n)
		for i := range big {
			big[i] = (i * 7919) % n // deterministik karışık dizi
		}
		comparisons, merges = 0, 0
		mergeSort(big)
		expected := n * log2(n)
		fmt.Printf("%10d %14d %14d %12.2f\n", n, comparisons, expected,
			float64(comparisons)/float64(expected))
	}
}

func log2(n int) int {
	count := 0
	for n > 1 {
		n /= 2
		count++
	}
	return count
}

package main

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

// lomutoPartition: son elemanı pivot alır, anlaşılması kolay
func lomutoPartition(data []int, lo, hi int) int {
	pivot := data[hi]
	i := lo // küçük elemanların sınırı

	for j := lo; j < hi; j++ {
		if data[j] < pivot {
			data[i], data[j] = data[j], data[i]
			i++
		}
	}
	data[i], data[hi] = data[hi], data[i] // pivotu yerine koy
	return i
}

// hoarePartition: iki uçtan ortaya doğru çalışır, daha az takas yapar
func hoarePartition(data []int, lo, hi int) int {
	pivot := data[lo+(hi-lo)/2]
	i, j := lo-1, hi+1

	for {
		for {
			i++
			if data[i] >= pivot {
				break
			}
		}
		for {
			j--
			if data[j] <= pivot {
				break
			}
		}
		if i >= j {
			return j
		}
		data[i], data[j] = data[j], data[i]
	}
}

func quickSortLomuto(data []int, lo, hi int) {
	if lo >= hi {
		return
	}
	p := lomutoPartition(data, lo, hi)
	quickSortLomuto(data, lo, p-1)
	quickSortLomuto(data, p+1, hi)
}

func quickSortHoare(data []int, lo, hi int) {
	if lo >= hi {
		return
	}
	p := hoarePartition(data, lo, hi)
	quickSortHoare(data, lo, p)
	quickSortHoare(data, p+1, hi)
}

// quickSortRandom: rastgele pivot — en kötü durumu pratikte imkânsız kılar
func quickSortRandom(data []int, lo, hi int, r *rand.Rand) {
	if lo >= hi {
		return
	}
	pick := lo + r.IntN(hi-lo+1)
	data[pick], data[hi] = data[hi], data[pick]

	p := lomutoPartition(data, lo, hi)
	quickSortRandom(data, lo, p-1, r)
	quickSortRandom(data, p+1, hi, r)
}

func main() {
	base := []int{5, 2, 9, 1, 7, 3, 8, 4, 6}

	a := slices.Clone(base)
	quickSortLomuto(a, 0, len(a)-1)
	fmt.Println("Lomuto:", a)

	b := slices.Clone(base)
	quickSortHoare(b, 0, len(b)-1)
	fmt.Println("Hoare: ", b)

	r := rand.New(rand.NewPCG(1, 2))
	c := slices.Clone(base)
	quickSortRandom(c, 0, len(c)-1, r)
	fmt.Println("rastgele pivot:", c)

	fmt.Println("üçü aynı mı:", slices.Equal(a, b) && slices.Equal(b, c))

	// Bölümleme adımını yakından görelim
	fmt.Println()
	demo := []int{5, 2, 9, 1, 7, 3}
	fmt.Println("bölümleme öncesi:", demo, "pivot:", demo[len(demo)-1])
	p := lomutoPartition(demo, 0, len(demo)-1)
	fmt.Println("bölümleme sonrası:", demo)
	fmt.Printf("pivot indeksi: %d, sol taraf: %v, sağ taraf: %v\n", p, demo[:p], demo[p+1:])
}

package main

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

var depth, maxDepth, partitions int

func partition(data []int, lo, hi int) int {
	partitions++
	pivot := data[hi]
	i := lo
	for j := lo; j < hi; j++ {
		if data[j] < pivot {
			data[i], data[j] = data[j], data[i]
			i++
		}
	}
	data[i], data[hi] = data[hi], data[i]
	return i
}

// lastElementPivot: en kötü duruma açık
func quickSortLast(data []int, lo, hi int) {
	if lo >= hi {
		return
	}
	depth++
	maxDepth = max(maxDepth, depth)
	p := partition(data, lo, hi)
	quickSortLast(data, lo, p-1)
	quickSortLast(data, p+1, hi)
	depth--
}

// medianOfThree: ilk, orta ve son elemanın medyanını pivot yapar
func medianOfThree(data []int, lo, hi int) {
	mid := lo + (hi-lo)/2
	if data[mid] < data[lo] {
		data[mid], data[lo] = data[lo], data[mid]
	}
	if data[hi] < data[lo] {
		data[hi], data[lo] = data[lo], data[hi]
	}
	if data[hi] < data[mid] {
		data[hi], data[mid] = data[mid], data[hi]
	}
	data[mid], data[hi] = data[hi], data[mid] // medyanı sona koy
}

func quickSortMedian(data []int, lo, hi int) {
	if lo >= hi {
		return
	}
	depth++
	maxDepth = max(maxDepth, depth)
	medianOfThree(data, lo, hi)
	p := partition(data, lo, hi)
	quickSortMedian(data, lo, p-1)
	quickSortMedian(data, p+1, hi)
	depth--
}

func quickSortRandom(data []int, lo, hi int, r *rand.Rand) {
	if lo >= hi {
		return
	}
	depth++
	maxDepth = max(maxDepth, depth)
	pick := lo + r.IntN(hi-lo+1)
	data[pick], data[hi] = data[hi], data[pick]
	p := partition(data, lo, hi)
	quickSortRandom(data, lo, p-1, r)
	quickSortRandom(data, p+1, hi, r)
	depth--
}

func main() {
	const n = 500
	sorted := make([]int, n)
	for i := range sorted {
		sorted[i] = i
	}
	r := rand.New(rand.NewPCG(9, 13))
	shuffled := slices.Clone(sorted)
	r.Shuffle(n, func(i, j int) { shuffled[i], shuffled[j] = shuffled[j], shuffled[i] })

	run := func(name string, data []int, sortFn func([]int)) {
		depth, maxDepth, partitions = 0, 0, 0
		copied := slices.Clone(data)
		sortFn(copied)
		fmt.Printf("  %-22s derinlik=%-5d bölümleme=%-6d sıralı=%t\n",
			name, maxDepth, partitions, slices.IsSorted(copied))
	}

	fmt.Printf("SIRALI girdi (n=%d) — teorik en iyi derinlik ≈ %d:\n", n, 9)
	run("son eleman pivot", sorted, func(d []int) { quickSortLast(d, 0, len(d)-1) })
	run("üçün medyanı", sorted, func(d []int) { quickSortMedian(d, 0, len(d)-1) })
	run("rastgele pivot", sorted, func(d []int) {
		quickSortRandom(d, 0, len(d)-1, rand.New(rand.NewPCG(1, 2)))
	})

	fmt.Println()
	fmt.Printf("KARIŞIK girdi (n=%d):\n", n)
	run("son eleman pivot", shuffled, func(d []int) { quickSortLast(d, 0, len(d)-1) })
	run("üçün medyanı", shuffled, func(d []int) { quickSortMedian(d, 0, len(d)-1) })
	run("rastgele pivot", shuffled, func(d []int) {
		quickSortRandom(d, 0, len(d)-1, rand.New(rand.NewPCG(1, 2)))
	})

	fmt.Println()
	fmt.Println("Gözlem: sıralı girdide son-eleman pivotu derinliği n'e çıkarır → O(n²)")
	fmt.Println("Gözlem: medyan veya rastgele pivot her iki girdide de logaritmik kalır")
}

package main

import (
	"fmt"
	"slices"
)

// siftDown: kökü doğru yerine indirir — O(log n)
func siftDown(data []int, root, size int) {
	for {
		child := 2*root + 1
		if child >= size {
			return
		}
		// İki çocuğun büyüğünü seç
		if child+1 < size && data[child+1] > data[child] {
			child++
		}
		if data[root] >= data[child] {
			return // heap özelliği sağlandı
		}
		data[root], data[child] = data[child], data[root]
		root = child
	}
}

// heapSort: yerinde, O(n log n) garanti
func heapSort(data []int) {
	n := len(data)

	// 1) Max-heap kur: son yapraktan geriye doğru — O(n)
	for i := n/2 - 1; i >= 0; i-- {
		siftDown(data, i, n)
	}

	// 2) En büyüğü sona al, heap'i küçült — n × O(log n)
	for end := n - 1; end > 0; end-- {
		data[0], data[end] = data[end], data[0]
		siftDown(data, 0, end)
	}
}

func isMaxHeap(data []int) bool {
	for i := range data {
		for _, c := range []int{2*i + 1, 2*i + 2} {
			if c < len(data) && data[i] < data[c] {
				return false
			}
		}
	}
	return true
}

func main() {
	data := []int{5, 2, 9, 1, 7, 3, 8}
	fmt.Println("girdi:", data)

	// Heapify adımını ayrı gösterelim
	heap := slices.Clone(data)
	for i := len(heap)/2 - 1; i >= 0; i-- {
		siftDown(heap, i, len(heap))
	}
	fmt.Println("heapify sonrası:", heap, "| geçerli max-heap mi:", isMaxHeap(heap))

	sorted := slices.Clone(data)
	heapSort(sorted)
	fmt.Println("sıralı:", sorted)

	// Farklı girdilerde tutarlı davranış
	fmt.Println()
	cases := map[string][]int{
		"sıralı":      {1, 2, 3, 4, 5, 6, 7},
		"ters sıralı": {7, 6, 5, 4, 3, 2, 1},
		"tekrarlı":    {3, 1, 3, 1, 3, 1},
		"tek eleman":  {42},
		"boş":         {},
	}
	for _, name := range []string{"sıralı", "ters sıralı", "tekrarlı", "tek eleman", "boş"} {
		d := slices.Clone(cases[name])
		heapSort(d)
		fmt.Printf("  %-12s → %-20v sıralı: %t\n", name, d, slices.IsSorted(d))
	}

	// Kararsızlık
	fmt.Println()
	fmt.Println("heap sıralaması KARARSIZDIR: uzak elemanlar takas edilir")
}

package main

import (
	"cmp"
	"fmt"
	"slices"
	"sort"
	"strings"
)

type Employee struct {
	Name   string
	Salary int
	Dept   string
}

func main() {
	nums := []int{5, 2, 9, 1, 7, 3}

	// En basit kullanım: sıralanabilir tipler
	asc := slices.Clone(nums)
	slices.Sort(asc)
	fmt.Println("artan:", asc)

	// Azalan: karşılaştırmayı ters çevir
	desc := slices.Clone(nums)
	slices.SortFunc(desc, func(a, b int) int { return cmp.Compare(b, a) })
	fmt.Println("azalan:", desc)

	// Yapılar: çok ölçütlü sıralama
	employees := []Employee{
		{"Zeynep", 15000, "Mühendislik"},
		{"Ali", 12000, "Satış"},
		{"Mehmet", 15000, "Mühendislik"},
		{"Ayşe", 18000, "Yönetim"},
		{"Can", 12000, "Mühendislik"},
	}

	byDeptThenSalary := slices.Clone(employees)
	slices.SortFunc(byDeptThenSalary, func(a, b Employee) int {
		if c := strings.Compare(a.Dept, b.Dept); c != 0 {
			return c
		}
		return cmp.Compare(b.Salary, a.Salary) // maaş azalan
	})
	fmt.Println()
	fmt.Println("departman + maaş sırası:")
	for _, e := range byDeptThenSalary {
		fmt.Printf("  %-14s %-14s %d\n", e.Dept, e.Name, e.Salary)
	}

	// Kararlı sıralama: eşitlikte özgün sıra korunur
	stable := slices.Clone(employees)
	slices.SortStableFunc(stable, func(a, b Employee) int {
		return cmp.Compare(a.Salary, b.Salary)
	})
	fmt.Println()
	fmt.Println("maaşa göre KARARLI sıralama (eşit maaşlarda özgün sıra):")
	for _, e := range stable {
		fmt.Printf("  %-8s %d\n", e.Name, e.Salary)
	}

	// Eski API: sort.Slice (hâlâ çalışır)
	old := slices.Clone(nums)
	sort.Slice(old, func(i, j int) bool { return old[i] < old[j] })
	fmt.Println()
	fmt.Println("sort.Slice ile:", old)

	// Yararlı yardımcılar
	fmt.Println()
	fmt.Println("slices.IsSorted:", slices.IsSorted(asc))
	fmt.Println("slices.Min / Max:", slices.Min(nums), slices.Max(nums))
	fmt.Println("slices.MaxFunc (en yüksek maaş):",
		slices.MaxFunc(employees, func(a, b Employee) int { return cmp.Compare(a.Salary, b.Salary) }).Name)
}