Karşılaştırma
Takas
Bölümleme

  • Bölümlenen kısım
  • Pivot
  • Karşılaştırılan
  • Takas edilen
  • Yerinde

Hızlı sıralama hakkında daha fazla

Hızlı sıralama

Hızlı sıralama (quicksort) bir pivot seçer, her küçük değeri onun önüne, diğer her değeri arkasına taşır, sonra iki tarafı da aynı şekilde sıralar. Her bölümlemeden sonra pivot son yerine yerleşir. Pivotun nasıl seçileceğini belirleyin, sıralamayı istediğiniz hızda oynatın ya da her seferinde bir karşılaştırma ilerleyin ve sıralı bir listede kötü bir pivotun hızlı sıralamayı neden yavaşlattığını görün. Sıralamayı izlemek için Oynat'a, her seferinde bir karşılaştırma ilerlemek için Adım ve Geri'ye basın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin. Kutucuklar karşılaştırmaları, takasları ve bölümlemeleri sayar. Çubuk sayısını, başlangıç düzenini ve pivotun nasıl seçileceğini seçin ya da kendi sayılarınızı yazın. Tahta seçiliyken ok tuşları adım atar, boşluk tuşu oynatır ve duraklatır, Home ve End başa ve sona atlar.

Nasıl çalışır

  1. Çubuk sayısını ve başlangıç düzenini seçin: rastgele, neredeyse sıralı, ters veya az sayıda farklı değerle. Ya da kendi sayılarınızı yazın.
  2. Oynat'a basın ya da her seferinde bir karşılaştırma ilerlemek için Adım ve Geri'yi kullanın. Sıralamanın herhangi bir yerine atlamak için adım kaydırıcısını sürükleyin.
  3. Pivot kuralını seçin: son değer, ortadaki değer, rastgele bir değer ya da üçün medyanı. Her birini sıralı bir listede deneyin.

Hızlı sıralama nasıl çalışır

Sıralanacak kısımdan bir değeri pivot olarak seçin ve sona taşıyın. Diğer değerleri soldan sağa gezin; pivottan küçük olan her değer takasla, baştan büyüyen bir sol kısma geçer. Sonra pivotu takasla sol kısmın hemen arkasına yerleştirin. Önündeki her şey artık daha küçük, arkasındakilerin hiçbiri değil; yani pivot son yerinde. Önündeki ve arkasındaki kısımları da her kısım tek bir değer kalana kadar aynı şekilde sıralayın.

Pivot neden önemli

Pivot ortaya yakın düştüğünde her bölümleme problemi yarıya indirir ve karşılaştırma sayısı n log n gibi artar: 40 rastgele değer için yaklaşık 190. Pivot en küçük ya da en büyük değer olduğunda bir taraf boş kalır, diğer tarafta geri kalan her şey olur. Pivot olarak son değer seçilirse sıralı ya da ters bir listede bu her adımda olur ve sıralama n(n − 1)/2 karşılaştırma gerektirir; 40 değer için 780. Rastgele bir pivot ya da ilk, orta ve son değerin medyanı pratikte bunu önler.

Sık sorulan sorular

Hızlı sıralama nasıl çalışır?

Bir pivot seçer, listeyi küçük değerler pivotun önüne, kalanlar arkasına gelecek şekilde bölümler, sonra iki tarafı da hızlı sıralamayla sıralar. Her bölümlemeden sonra pivot son yerindedir.

Hızlı sıralama sıralı bir listede neden yavaştır?

Pivot olarak ilk ya da son değer seçilirse sıralı bir liste pivot olarak hep en küçük ya da en büyük değeri verir. Bu durumda bölümlemenin bir tarafı boş kalır, her bölümleme yalnızca bir değeri ayırır ve sıralama n(n − 1)/2 karşılaştırma gerektirir. Rastgele bir pivot ya da üçün medyanı pratikte bunu çözer.

Hızlı sıralama birleştirme sıralamasından hızlı mı?

Pratikte çoğu zaman evet: yerinde sıralar, ek tampona ihtiyaç duymaz ve iç döngüsü çok basittir. Ortalamada birleştirme sıralamasından biraz daha fazla karşılaştırma yapar; en kötü durumu n², birleştirme sıralamasınınki ise her zaman n log n. Introsort gibi kütüphane sıralamaları hızlı sıralamayla başlar ve bölünmeler fazla dengesizleşirse yığın sıralamasına geçer.

Hızlı sıralama kararlı mı?

Hayır. Bölümleme değerleri uzak mesafelere takas eder, bu yüzden eşit değerlerin sırası değişebilir.

Sayılarım bir yere gönderiliyor mu?

Hayır. Sıralama tarayıcınızda çalışır ve son ayarlarınız bu tarayıcının yerel depolamasında kalır.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Editöre Git