Yükleniyor // RUNTIME_INITIALIZINGAlgoritma ve bileşen ağacı hazırlanıyor...
Hızlı sıralama algoritmasının performansını ve kararlılığını artırmak için pivot seçimi ve bölümleme stratejilerini optimize eden varyantlardır.
Quicksort, ortalama durumda son derece hızlı çalışan bir böl ve fethet sıralama algoritmasıdır. Ancak en kötü durumda (örneğin sıralı bir dizide ilk veya son elemanın pivot seçilmesi) O(n^2) süresinde çalışabilir. Bu problemi çözmek için çeşitli varyantlar geliştirilmiştir.
Rastgeleleştirilmiş Quicksort (Randomized Quicksort), diziden rastgele bir elemanı pivot seçerek en kötü durum senaryolarını önler. Üçlü Medyan Bölümleme (Median-of-Three Partitioning) ise dizinin başındaki, ortasındaki ve sonundaki elemanların medyanını pivot seçerek dengeli bir bölümleme sağlar.
Pivot Bölümleme (Partition) ise diziyi pivotun etrafında küçükler, eşitler ve büyükler olarak organize eder. Hoare ve Lomuto bölümleme şemaları en yaygın kullanılan temel bölümleme yöntemleridir.
Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.
1function randomizedQuicksort(arr: number[], low = 0, high = arr.length - 1): number[] {2 if (low < high) {3 const pivotIndex = randomizedPartition(arr, low, high);4 randomizedQuicksort(arr, low, pivotIndex - 1);5 randomizedQuicksort(arr, pivotIndex + 1, high);6 }7 return arr;8}910function randomizedPartition(arr: number[], low: number, high: number): number {11 const randIdx = Math.floor(Math.random() * (high - low + 1)) + low;12 [arr[randIdx], arr[high]] = [arr[high], arr[randIdx]];13 const pivot = arr[high];14 let i = low - 1;15 for (let j = low; j < high; j++) {16 if (arr[j] <= pivot) {17 i++;18 [arr[i], arr[j]] = [arr[j], arr[i]];19 }20 }21 [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];22 return i + 1;23}Sıralamak istediğiniz sayıları virgülle ayırarak girin ve çalıştırın. Örnek: 35, 12, 43, 8, 22, 9, 60
Sıralamak istediğiniz sayıları virgülle ayırarak girin ve çalıştırın. Örnek: 35, 12, 43, 8, 22, 9, 60
En İyi Durum: O(n log n)
Ortalama Durum: O(n log n)
En Kötü Durum: O(n^2)
O(log n) - Giriş boyutu arttıkça, çalışma süresi logaritmik olarak artar.
Quicksort Varyantları (Quicksort Variants) Algoritması ile benzer veya alternatif olarak değerlendirilebilecek diğer başlıklar: