Python Hızlı Sıralama Algoritması Kılavuzu
Python'daki hızlı sıralama algoritmasını keşfedin. Bu etkileşimli kodlama örneğinde pivot seçimini, bölümlendirmeyi ve yinelemeyi öğrenin.
Genel Bakış
Quicksort son derece hızlı ve yaygın olarak kullanılan bir sıralama algoritmasıdır. Birleştirme sıralaması gibi, böl ve yönet yaklaşımını kullanır. Ancak hızlı sıralama, öğeleri 'yerinde' sıralayarak hafızayı verimli hale getirir.
Algoritma listeden bir 'pivot' öğesi seçilerek çalışır. Daha sonra diğer elemanları iki alt diziye ayırır: pivottan küçük olanlar ve pivottan büyük olanlar. Bu işlem alt dizilere yinelemeli olarak uygulanır.
Quicksort'un en kötü durum karmaşıklığı O(n²) olsa da, ortalama durum çalışma süresi O(n log n)'dir ve daha düşük önbellek kayıpları ve geçici diziler oluşturmanın sıfır ek yükü nedeniyle genellikle pratikte birleştirme sıralamasından daha iyi performans gösterir.
Kod ve Yürütme Çıkışı
Yüksek okunabilirlik için liste kavramalarını kullanan kısa ve öz bir Hızlı Sıralama komut dosyası.
def quicksort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
# Test list
data = [12, 4, 5, 6, 7, 3, 1, 15]
print("Original List:", data)
sorted_data = quicksort(data)
print("Sorted List: ", sorted_data)Original List: [12, 4, 5, 6, 7, 3, 1, 15]
Sorted List: [1, 3, 4, 5, 6, 7, 12, 15]Adım Adım Uygulama
- Bellek ayak izinin minimumda tutulması gereken sistem sıralama rutinleri
- Standart dil kitaplığı çerçevelerinde genel amaçlı sıralama
- Bölme mekaniği ve özyinelemeli böl ve yönet konularının akademik öğretimi
Sıkça Sorulan Sorular
Hızlı sıralamada O(n²)'nin en kötü durum karmaşıklığından nasıl kaçınabiliriz?
En kötü durum, seçilen pivotun sürekli olarak en küçük veya en büyük öğe olması durumunda ortaya çıkar. Bunu azaltmak için geliştiriciler rastgele bir pivot veya "üçün medyanı" değerlerini seçmek gibi stratejiler kullanır.
Hızlı sıralama kararlı mı?
Hayır, standart Hızlı Sıralama kararsızdır. Bölümleme sırasında öğeler uzun aralıklarda değiştirilir ve bu da yinelenen öğelerin göreceli sırasını değiştirebilir.
İlgili Konular
Python'da Birleştirme Sıralamasını nasıl uygulayacağınızı öğrenin. Böl ve Fethet sıralama stratejisinin etkileşimli, adım adım bir örneği.
Python Sıralama AlgoritmalarıPython sıralama algoritmalarını keşfedin. Kabarcık sıralamasını görselleştirin ve bir tarayıcı IDE bağlamında yerel olarak birleştirme sıralamasını yapın.
Python İkili Arama AlgoritmasıSıralanmış listeleri logaritmik O(log n) süresine göre arayın. Adım adım mantık, uç durumlar ve optimizasyonlar da dahil olmak üzere Python'da ikili aramayı çalıştırın ve anlayın.