Hızlı Sıralama ve Dönüm Noktası Seçimi
Lomuto ve Hoare bölümleme şemalarıyla hızlı sıralama oluşturun; en kötü durumdaki O(n²)’yi ve rastgele dönüm noktası seçiminin bunu nasıl azalttığını tartışın.
Hızlı Sıralama ve Dönüm Noktası Seçimi, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 3. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.
Hızlı Sıralama: Yerinde Böl ve Yönet
Hızlı sıralama, pratikte en yaygın kullanılan sıralama algoritmasıdır. Birleştirmeli sıralamanın aksine, ek diziler ayırmadan yerinde sıralama yapar. Temel fikir şudur: bir pivot öğesi seçin, diziyi pivot'tan küçük tüm öğeler önce ve büyük tüm öğeler sonra olacak şekilde bölümlendirin, ardından her bölümü özyinelemeli olarak sıralayın. Bölümleme adımı O(n) sürede çalışır ve iyi bir pivot seçildiğinde özyineleme derinliği O(log n) olur.
def quick_sort(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
pivot_idx = partition(arr, lo, hi)
quick_sort(arr, lo, pivot_idx - 1) # sort left
quick_sort(arr, pivot_idx + 1, hi) # sort right
def partition(arr, lo, hi):
pivot = arr[hi] # Lomuto: choose last element as pivot
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]Lomuto Bölümleme Şeması
Lomuto bölümlemesi, son öğeyi pivot olarak kullanır. Yavaş bir i işaretçisi, 'pivot'tan küçük' bölgesinin sınırını izler; hızlı bir j işaretçisi ileri doğru tarama yapar. arr[j] <= pivot olduğunda i değerini artırın ve küçük öğeler bölgesini genişleterek arr[i] ile arr[j] değerlerini yer değiştirin. Tarama sonrasında arr[hi] ile yer değiştirerek pivotu i+1 konumuna yerleştirin. Uygulaması basittir; ancak Hoare şemasına göre 3× daha fazla yer değiştirme yapar.
def lomuto_partition_traced(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
print(f'Pivot: {pivot}, array: {arr[lo:hi+1]}')
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
print(f'After partition: {arr[lo:hi+1]}')
return i + 1
arr = [3, 1, 4, 1, 5, 9, 2, 6]
lomuto_partition_traced(arr, 0, len(arr)-1)Hoare Bölümleme Şeması
Hoare bölümlemesi, iki uçtan başlayan ve kesişene kadar içeri doğru ilerleyen iki işaretçi kullanır. Pivotu (genellikle ilk öğeyi) seçer ve pivot'tan küçük öğeleri sola, büyük öğeleri sağa taşır. Hoare şeması, Lomuto'ya göre 3× daha az yer değiştirme yapar ve eşit öğelerle daha iyi çalışır; ancak bölümleme sonrasında pivot son konumuna yerleşmez — bu da biraz farklı özyinelemeli çağrılar gerektirir.
def hoare_partition(arr, lo, hi):
pivot = arr[lo] # first element as pivot
i, j = lo - 1, hi + 1
while True:
i += 1
while arr[i] < pivot: i += 1
j -= 1
while arr[j] > pivot: j -= 1
if i >= j: return j
arr[i], arr[j] = arr[j], arr[i]
def quick_sort_hoare(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
p = hoare_partition(arr, lo, hi)
quick_sort_hoare(arr, lo, p) # note: p not p-1
quick_sort_hoare(arr, p+1, hi)
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort_hoare(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]En Kötü Durum O(n²): Zaten Sıralanmış Girdi
Hızlı sıralamanın en kötü durumu, pivotun bölüm içindeki sürekli olarak en küçük veya en büyük öğe olmasıyla ortaya çıkar. Lomuto'nun zaten sıralanmış bir dizide son öğeyi pivot olarak kullandığı durumda, bölümleme her zaman sola 0 öğe, sağa ise n-1 öğe yerleştirir: özyineleme ağacı n derinliğinde bir zincire dönüşür ve O(n²) karşılaştırma yapılır. Bu nedenle pivot seçimi kritik önem taşır ve üretim uygulamalarında pivot rastgeleleştirilir.
import sys
sys.setrecursionlimit(5000)
def quick_sort_naive(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
comparisons = [0]
def _qs(lo, hi):
if lo >= hi: return
pivot = arr[hi] # last element pivot
i = lo - 1
for j in range(lo, hi):
comparisons[0] += 1
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
_qs(lo, p-1); _qs(p+1, hi)
_qs(lo, hi)
return comparisons[0]
import math
n = 100
sorted_arr = list(range(n))
ops = quick_sort_naive(sorted_arr)
print(f'n={n}, ops={ops}, n^2={n**2}') # ops close to n*(n-1)/2Rastgeleleştirilmiş Pivot: Beklenen O(n log n)
Pivotu eşit olasılıkla rastgele seçerek (bölümlemeden önce rastgele bir öğeyi arr[hi] ile yer değiştirerek), sürekli olarak kötü pivotlar seçme olasılığı üstel biçimde azalır. Beklenen karşılaştırma sayısı 2n ln(n) ≈ 1.39 n log₂(n) olur; böylece beklenen süre O(n log n) ve çok yüksek olasılıkla bu sonuç elde edilir. Rastgeleleştirilmiş hızlı sıralamanın pratikte kullanılmasının nedeni budur — sabit pivot stratejileri için kötü niyetli bir tarafın oluşturabileceği patolojik en kötü durumlardan kaçınır.
import random
def quick_sort_random(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
# Randomise pivot
rand_i = random.randint(lo, hi)
arr[rand_i], arr[hi] = arr[hi], arr[rand_i]
# Lomuto partition with last element as pivot
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
quick_sort_random(arr, lo, p - 1)
quick_sort_random(arr, p + 1, hi)
arr = list(range(100, 0, -1)) # worst case for naive
quick_sort_random(arr)
print(arr[:10]) # [1,2,3,4,5,6,7,8,9,10]Üçlü Ortanca Pivot Seçimi
Başka bir pivot stratejisi de ilk, orta ve son öğelerin ortancasını seçmektir. Bu yöntem, sıralanmış veya ters sıralanmış girdilerdeki (en yaygın kötü durum oluşturan girdiler) en kötü durum davranışından kaçınırken rastgele sayı üretmenin ek yükünü ortadan kaldırır. Büyük diziler için birçok üretim uygulaması üçlü ortanca veya ninther'ı (üç ortancanın ortancası) kullanır ve yaklaşık 10 öğelik bir eşikten küçük alt diziler için eklemeli sıralamaya geçer.
def median_of_three(arr, lo, hi):
mid = (lo + hi) // 2
# Sort lo, mid, hi values in place
if arr[lo] > arr[mid]: arr[lo], arr[mid] = arr[mid], arr[lo]
if arr[lo] > arr[hi]: arr[lo], arr[hi] = arr[hi], arr[lo]
if arr[mid] > arr[hi]: arr[mid], arr[hi] = arr[hi], arr[mid]
# Median is now at arr[mid]; swap to arr[hi-1] as pivot
arr[mid], arr[hi] = arr[hi], arr[mid]
return arr[hi] # pivot value
arr = [3, 9, 1]
print(median_of_three(arr, 0, 2), arr) # 3, [1,3,9] (sorted)Hollanda Ulusal Bayrağı: Üç Yönlü Bölümleme
Standart bölümleme, pivot'tan küçük öğeleri sola ve büyük öğeleri sağa yerleştirir; ancak pivot'a eşit öğeler dağınık kalır. Üç yönlü bölümleme (Hollanda ulusal bayrağı), üç bölge oluşturur: <pivot, ==pivot, >pivot. Bu, çok sayıda yinelenen öğe içeren diziler için kritik önem taşır — standart hızlı sıralama O(n²) süresine gerilerken üç yönlü hızlı sıralama tüm değerleri aynı olan girdilerde O(n) sürede çalışır.
def three_way_partition(arr, lo, hi):
pivot = arr[lo]
lt = lo # arr[lo..lt-1] < pivot
gt = hi # arr[gt+1..hi] > pivot
i = lo # current
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1; i += 1
elif arr[i] > pivot:
arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1 # don't advance i
else:
i += 1
return lt, gt # pivot occupies arr[lt..gt]
arr = [3, 1, 4, 1, 5, 9, 2, 6, 3, 3]
lt, gt = three_way_partition(arr, 0, len(arr)-1)
print(arr, '| pivot region:', lt, 'to', gt)Quickselect: O(n) Sürede K'ıncı En Küçük Öğe
Quickselect, tamamen sıralama yapmadan k'ıncı en küçük öğeyi ortalama O(n) sürede bulmak için hızlı sıralamanın bölümleme adımını kullanır. Bölümlemeden sonra pivot, son konumu olan p konumundadır. p == k ise arr[p] değerini döndürün. k < p ise sol bölümde; k > p ise sağ bölümde özyinelemeli çağrı yapın. Ortalama olarak her özyineleme problemi yarıya böler: O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n).
import random
def quickselect(nums, k):
'''Find kth smallest (0-indexed) in O(n) average.'''
def _select(lo, hi):
if lo == hi: return nums[lo]
rand_i = random.randint(lo, hi)
nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
pivot = nums[hi]
i = lo - 1
for j in range(lo, hi):
if nums[j] <= pivot:
i += 1; nums[i], nums[j] = nums[j], nums[i]
p = i + 1
nums[p], nums[hi] = nums[hi], nums[p]
if p == k: return nums[p]
elif k < p: return _select(lo, p - 1)
else: return _select(p + 1, hi)
return _select(0, len(nums) - 1)
print(quickselect([3,2,1,5,6,4], 1)) # 2 (2nd smallest)Hızlı Sıralamanın Alan Karmaşıklığı
Hızlı sıralamaya 'yerinde' denir; ancak özyineleme için ortalama O(log n) yığın alanı kullanır (özyineleme ağacının her düzeyi için bir çerçeve). En kötü durumda bu, O(n) yığın derinliğine ulaşır. En kötü durumda O(log n) yığın alanını garanti etmek için her zaman önce daha küçük bölümde özyinelemeli çağrı yapın ve daha büyük bölüm için kuyruk çağrısı optimizasyonunu kullanın. Python'ın özyineleme sınırı, çok derin hızlı sıralama özyinelemelerini riskli hâle getirir — bunu mülakatlarda belirtmekte fayda vardır.
def quick_sort_optimised(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
while lo < hi:
p = lomuto_partition_qs(arr, lo, hi)
# Recurse on smaller partition; iterate on larger
if p - lo < hi - p:
quick_sort_optimised(arr, lo, p - 1)
lo = p + 1 # tail-call elimination
else:
quick_sort_optimised(arr, p + 1, hi)
hi = p - 1
def lomuto_partition_qs(arr, lo, hi):
pivot = arr[hi]; i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot: i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1Sıralama Algoritmalarını Karşılaştırma
Bilginizi bir araya getirin:
- Hızlı sıralama: beklenen O(n log n), en kötü durumda O(n²), O(log n) alan, kararlı değil, rastgele verilerde pratikte en hızlı
- Birleştirmeli sıralama: garanti edilen O(n log n), O(n) alan, kararlı, bağlı listeler ve harici sıralama için en iyi seçenek
- Yığın sıralaması: garanti edilen O(n log n), O(1) alan, kararlı değil, önbellek kaçırmaları nedeniyle pratikte daha yavaş
- Eklemeli sıralama: en iyi durumda O(n), küçük n veya neredeyse sıralı veriler için ideal
# Python's sorted() uses Timsort:
# - Hybrid: merge sort for large runs, insertion sort for small (< 64 elements)
# - Stable, O(n log n) worst case
# - O(n) best case for sorted/reverse-sorted/nearly-sorted
# - O(n) extra space
import random
arr = random.sample(range(10000), 1000)
sorted_arr = sorted(arr) # Timsort
print(sorted_arr[:5], '...') # first 5 elementsIntrosort: Üç Yaklaşımı Birleştirme
Introsort (C++ STL'de std::sort tarafından kullanılır), hızlı sıralama, yığın sıralaması ve eklemeli sıralamayı birleştirir: rastgeleleştirilmiş hızlı sıralamayla başlayın; özyineleme derinliği 2 log n değerini aşarsa (kötü bir pivot dizisine işaret eder), O(n log n) süresini garanti etmek için yığın sıralamasına geçin; 16 öğeden küçük alt diziler için eklemeli sıralamayı kullanın. Böylece hızlı sıralamanın ortalama durum hızını ve eklemeli sıralamanın küçük alt dizilerdeki verimliliğini korurken en kötü durumda O(n log n) elde edilir.
# Introsort hybrid (simplified)
def introsort(arr, depth_limit=None):
if depth_limit is None:
import math
depth_limit = 2 * int(math.log2(len(arr) + 1)) if arr else 0
if len(arr) <= 16:
# insertion sort for small arrays
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1
arr[j+1] = key
return arr
if depth_limit == 0:
arr.sort() # fall back to heapsort equivalent
return arr
# Otherwise quick sort
pivot = arr[-1]
small = [x for x in arr[:-1] if x <= pivot]
large = [x for x in arr[:-1] if x > pivot]
return introsort(small, depth_limit-1) + [pivot] + introsort(large, depth_limit-1)
print(introsort([5,3,8,1,9,2,7]))Hızlı Kontrol
Bu dersteki Veri Yapıları & Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını ne kadar anladığınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: hızlı sıralama, bir pivot etrafında yerinde bölümleme yapar ve her iki taraf için özyinelemeli çağrı yapar; böylece O(log n) yığın alanıyla beklenen O(n log n) süreye ulaşır ve rastgele verilerde pratikte birleştirmeli sıralamadan daha hızlıdır, sabit pivot kullanılan sıralanmış girdilerde en kötü durum olan O(n²) ortaya çıkar ve rastgeleleştirilmiş pivot seçimi veya üçlü ortanca ile bundan kaçınılır ve üç yönlü bölümleme yinelenen öğeleri verimli şekilde işler; quickselect ise bölümleme fikrini genişleterek tam sıralama yapmadan k'ıncı en küçük öğeyi ortalama O(n) sürede bulur. Sırada karşılaştırmaya dayanmayan sıralamaları ve Python'ın yerleşik sıralamasını inceleyeceğiz.
Sıkça Sorulan Sorular
“Hızlı Sıralama ve Dönüm Noktası Seçimi” dersi ücretsiz mi?
Evet — “Hızlı Sıralama ve Dönüm Noktası Seçimi” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.
“Hızlı Sıralama ve Dönüm Noktası Seçimi” dersinde ne öğreneceğim?
Lomuto ve Hoare bölümleme şemalarıyla hızlı sıralama oluşturun; en kötü durumdaki O(n²)’yi ve rastgele dönüm noktası seçiminin bunu nasıl azalttığını tartışın. DSA Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 3. dersidir.
“Hızlı Sıralama ve Dönüm Noktası Seçimi” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her DSA Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Kabarcık Sıralaması ve Eklemeli Sıralama
- Birleştirmeli Sıralama: Böl, Sırala, Birleştir
- Hızlı Sıralama ve Dönüm Noktası Seçimi
- Karşılaştırmasız Sıralamalar ve Python’un sort() İşlevi