Bubble Sort
Kabarcık Sıralaması
- Okunuşu
- babıl sort
Kısaca
Bubble sort (kabarcık sıralaması), sırası bozuk komşu öğeleri yer değiştiren basit bir sıralama algoritmasıdır; her geçiş kalan en büyük değeri sona taşır.
Bubble sort nedir?
Her geçiş her komşu çifti karşılaştırır ve soldaki daha büyükse onları yer değiştirir. İlk geçişten sonra en büyük öğe sonuna kadar ilerlemiş olur; ikinciden sonra ikinci en büyük onun hemen önüne yerleşir ve böyle devam eder. Sıralı kısım sağdan büyür, ta ki bir geçiş hiç yer değiştirme yapmayana kadar; bu da listenin sıralı olduğu anlamına gelir.
Bubble sort ortalama ve en kötü durumda O(n²) zaman alır, çünkü en fazla n geçişin her biri en fazla n çifti karşılaştırabilir. Bir geçiş hiç yer değiştirme yapmadığında durmak şeklindeki yaygın optimizasyonla zaten sıralı bir liste yalnızca tek bir geçiş, yani O(n) sürer. O(1) ek bellekle yerinde sıralar ve kararlıdır (stable); eşit öğeleri ilk sıralarında tutar.
Değeri eğiticidir. Anlaması, görselleştirmesi ve yazması kolaydır; bu da onu yaygın bir ilk sıralama algoritması ve döngüleri, yer değiştirmeleri, karmaşıklığı ve kararlılığı öğrenmenin iyi bir yolu yapar. Onun çalışmasını izlemek, bazı algoritmaların neden diğerlerinden çok daha iyi ölçeklendiğini açıkça gösterir.
Sık yapılan bir yanlış, bubble sort'un gerçek veriler için kabul edilebilir olduğunu düşünmektir. Çok küçük ya da neredeyse sıralı girdiler dışında alternatiflerden çok daha yavaştır; o da O(n²) olan insertion sort bile genellikle onu geçer. Production kodu, Timsort ya da introsort gibi verimli algoritmalar kullanan dilin yerleşik sıralamasını kullanmalıdır.
Önemli noktalar
- Bubble sort, sırası bozuk komşu öğeleri tekrar tekrar yer değiştirir.
- Her geçiş kalan en büyük öğeyi sona taşır.
- Ortalamada O(n²), erken çıkışla sıralı girdide O(n)'dir.
- Yerinde ve kararlıdır; çoğunlukla öğretim için kullanılır.
- Gerçek kod onun yerine yerleşik sıralamayı kullanmalıdır.
Örnek
def bubble_sort(items):
items = list(items)
for end in range(len(items) - 1, 0, -1):
swapped = False
for i in range(end):
if items[i] > items[i + 1]:
items[i], items[i + 1] = items[i + 1], items[i] # swap neighbors
swapped = True
if not swapped: # no swaps: already sorted, stop early
break
return items
print(bubble_sort([5, 1, 4, 2, 8])) # [1, 2, 4, 5, 8]Sık sorulan sorular
Bubble sort neden yavaştır?
Çünkü öğeleri bir seferde yalnızca bir konum taşır ve n öğe üzerinde yaklaşık n geçişe ihtiyaç duyabilir; bu da O(n²) karşılaştırma demektir. Girdiyi iki katına çıkarmak işi kabaca dört katına çıkarır.
Bubble sort kararlı mı?
Evet. Komşuları yalnızca soldaki kesinlikle daha büyük olduğunda yer değiştirir; bu yüzden eşit öğeler asla birbirinin önüne geçmez ve ilk sıralarını korur.
Bubble sort ile insertion sort arasındaki fark nedir?
İkisi de en kötü durumda O(n²)'dir. Bubble sort her geçişte bütün liste boyunca komşuları yer değiştirir; insertion sort ise sıralı bir ön kısım kurar ve her yeni öğeyi yerine yerleştirir; bu da genellikle çok daha az işlem yapar.
İlgili sayfalar
- Sıralama AlgoritmasıVeri Yapıları, s. 30Sıralama algoritması, öğeleri sayıları küçükten büyüğe ya da adları alfabetik olarak sıralamak gibi tanımlı bir düzene sokan adım adım bir yöntemdir.
- Insertion SortVeri Yapıları, s. 20Insertion sort (eklemeli sıralama), sıralı listeyi öğe öğe kurar; her yeni öğeyi sıralanmışlar arasında yerine koyar, tıpkı eldeki kartları dizmek gibi.
- Merge SortVeri Yapıları, s. 26Merge sort, bir listeyi ikiye bölen, her yarıyı özyinelemeyle sıralayan ve sıralı yarıları O(n log n) sürede birleştiren böl ve yönet sıralama algoritmasıdır.
- QuicksortVeri Yapıları, s. 28Quicksort, öğeleri seçilen bir pivot etrafında bölümleyen, sonra küçük ve büyük grupları aynı şekilde sıralayan bir böl ve yönet sıralama algoritmasıdır.
- Big O gösterimiProgramlamanın Temelleri, s. 4Big O gösterimi, girdi büyüdükçe bir algoritmanın çalışma süresinin ya da bellek kullanımının nasıl arttığını, kesin hız yerine büyüme oranıyla anlatır.
- DiziProgramlamanın Temelleri, s. 15Dizi, tek bir ad altında saklanan ve her öğesine genellikle 0'dan başlayan indeks adlı sayısal konumuyla erişilen, sıralı bir değerler koleksiyonudur.
Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin