Kabarcık sıralaması
Listeyi tekrar tekrar dolaşır ve sırası yanlış olan komşuların yerini değiştirir. Her turdan sonra kalan en büyük değer sona ulaşır.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- evet
- evet
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
- son yerinde
Şunu deneyin: Neredeyse sıralı bir liste seçin. Hiç yer değiştirme olmayan bir turdan sonra algoritma erken durur.
Nasıl çalışır
Her seferinde iki komşuyu karşılaştırır, soldaki büyükse yerlerini değiştirir. Böylece her turda en büyük değer, yükselen bir kabarcık gibi en sağa kadar gider. Bir turda hiç yer değiştirme olmazsa liste zaten sıralıdır.
Ne zaman iyi bir seçimdir
Gerçek programlarda neredeyse hiç kullanılmaz, çünkü uzun listelerde yavaştır. Öğrenmek içinse harikadır: karşılaştırıp yer değiştirerek sıralamanın temel fikrini gösterir. Yalnızca liste zaten sıralıysa hızlıdır.