Sıralama Algoritmaları Yarışı
Altı algoritma aynı diziyle başlar ve her adımda eşit sayıda temel işlem (bir karşılaştırma ya da bir yazma) yapar. Yani burada "hız" saat süresi değil, işlem sayısıdır; algoritma analizinde saydığımız şey de budur. Kırmızı sütunlar o an karşılaştırılan, yeşil sütunlar az önce yazılan elemanlardır. Bitiren algoritmanın yanında sırası yazar. Seçtiğiniz algoritmanın sözde kodu ve karmaşıklığı altta durur.
Nelere dikkat etmeli?
- Rastgele dizide $n$'yi 30'dan 120'ye çıkarın: $O(n^2)$ algoritmaların işlem sayısı yaklaşık 16 katına, $O(n \log n)$ olanlarınki yaklaşık 5-6 katına çıkar.
- "Neredeyse sıralı" girdide Insertion Sort ve Bubble Sort herkesi geçer: en iyi durumları $O(n)$'dir. Girdi hakkında bildikleriniz algoritma seçimini değiştirir.
- "Ters sıralı" girdide Quick Sort çöker: pivot hep en uçtaki eleman olduğu için en kötü durumuna, $O(n^2)$'ye düşer. Merge Sort ve Heap Sort etkilenmez.
- Selection Sort girdi ne olursa olsun aynı sayıda karşılaştırma yapar, ama en az yazmayı da o yapar: en çok $n - 1$ yer değiştirme.
- AP Computer Science A müfredatında Selection Sort, Insertion Sort ve Merge Sort vardır.