Hızlı sıralama
Pivot denen bir değer seçer, küçük değerleri onun soluna, büyükleri sağına taşır. Sonra aynısını her iki taraf için yapar.
- en iyi Ω(n log n)
- ortalama Θ(n log n)
- en kötü O(n²)
- bellek O(log n)
- kararsız
- ek bellek istemez
Bunlar ne demek?
- En iyi durum: girdi bu algoritma için en kolay olduğunda sürenin liste boyutu n ile nasıl arttığı.
- Ortalama: sürenin n ile olağan artışı. n²'de değer sayısı iki katına çıkınca süre yaklaşık dört katına çıkar; n log n çok daha yavaş artar.
- En kötü durum: en zor girdideki artış. Hızın asla düşmemesi gerektiğinde işe yarar.
- Bellek: listenin dışında ne kadar ek bellek gerektiği. 1 birkaç değişken, n listenin bir kopyası demektir.
- Kararlı: eşit iki değer başlangıçtaki sıralarını korur. Kayıtlar tek bir alana göre sıralanırken önemlidir.
- Ek bellek istemez: ikinci bir liste olmadan, listenin kendi içinde sıralar.
- karşılaştırılıyor
- taşınıyor
- pivot
- son yerinde
Oynat'a basın: çizgiler maliyetin nasıl arttığını gösterir
Oynat tuşuna basın veya algoritmada adım adım ilerleyin.
Boşluk: oynat veya duraklat. Sol ve sağ oklar: adım adım. Home ve End: atla.
Şunu deneyin: Ters sıralı bir liste seçin. Pivot hep kalan en küçük ya da en büyük değer olur, bir taraf boş kalır ve maliyet n²'ye tırmanır.
Nasıl çalışır
Burada pivot, aralığın son değeridir. Soldan sağa gidilirken pivottan büyük olmayan her değer, yer değiştirilerek sol tarafa alınır. Sonra pivot iki tarafın arasına konur ve bir daha oradan hiç ayrılmaz. Ardından her taraf aynı yolla sıralanır.
Ne zaman iyi bir seçimdir
Pratikte en hızlı sıralama yollarından biridir ve neredeyse hiç ek bellek istemez. Ama hep kötü bir pivot seçerse, örneğin zaten sıralı bir listede, yavaşlar. Gerçek sürümler pivotu daha dikkatli seçer.