Kabarcık Sıralaması, listede sürekli olarak adım adım ilerleyen, bitişik öğeleri karşılaştıran ve yanlış sırada olmaları durumunda bunları değiştiren basit bir sıralama algoritmasıdır. 'Kabarcık Sıralaması' olarak adlandırılmıştır çünkü daha küçük öğeler listenin en üstüne 'baloncuk yapar'. En verimli sıralama algoritması olmasa da anlaşılması ve uygulanması kolaydır, bu da onu sıralama algoritmaları hakkında bilgi edinmek için iyi bir başlangıç noktası yapar. Bu makalede Bubble Sort kavramını derinlemesine inceleyeceğiz, çıktılı bir Python uygulaması sunacağız ve algoritmanın zaman karmaşıklığını tartışacağız.
Kabarcık Sıralamasını Anlamak
Kabarcık Sıralamanın ardındaki temel fikir, listeyi birden çok kez yineleyerek bitişik öğeleri karşılaştırmak ve sıra dışıysa bunları değiştirmektir. İşlem, artık takas gerekmeyene kadar devam eder; bu, listenin artık sıralandığını gösterir. Algoritma adını, yüzeye çıkan kabarcıklar gibi, daha küçük öğelerin yavaş yavaş listenin en üstüne çıkmasından alıyor.
Kabarcık Sıralaması algoritmasının adımlarını inceleyelim:
- Listeyi yineleyin: Listenin başından başlayın ve her bir bitişik öğe çiftini karşılaştırın.
- Karşılaştırın ve değiştirin: Öğeler yanlış sıradaysa değiştirin. Bu, daha büyük olanın 'kabarcıklar oluşturmasını' ve daha küçük olanın aşağı doğru hareket etmesini sağlar.
- Yinelemeye devam et: Listenin sonuna ulaşılıncaya kadar her bir bitişik öğe çifti için işlemi tekrarlayın.
- Sıralanana kadar tekrarla: Daha fazla takas gerekmeyene kadar listeyi yinelemeye devam edin. Bu noktada liste sıralanıyor.
Kabarcık Sıralamanın anlaşılması kolay olsa da, özellikle büyük veri kümeleri için en verimli sıralama algoritması değildir. En kötü durumda zaman karmaşıklığı O(n^2)'dir; burada 'n', listedeki öğelerin sayısıdır. Bu ikinci dereceden zaman karmaşıklığı, daha gelişmiş sıralama algoritmalarıyla karşılaştırıldığında onu büyük veri kümeleri için daha az uygun hale getirir.
Kabarcık Sıralamanın Python Uygulaması
Şimdi Python'da Bubble Sort'u uygulayalım ve davranışını örnek bir listeyle gözlemleyelim:
def bubble_sort(arr): n = len(arr) # Traverse through all array elements for i in range(n): # Last i elements are already sorted, so we don't need to check them for j in range(0, n-i-1): # Swap if the element found is greater than the next element if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] # Example usage if __name__ == '__main__': # Sample list to be sorted sample_list = [64, 34, 25, 12, 22, 11, 90] # Display the original list print('Original List:', sample_list) # Apply Bubble Sort bubble_sort(sample_list) # Display the sorted list print('Sorted List:', sample_list)
Bu uygulamada, bubble_sort işlevi parametre olarak bir listeyi (arr) alır ve onu yerinde sıralar. İç içe döngü, bitişik elemanları karşılaştırır ve yanlış sırada olmaları durumunda bunları değiştirir. Dış döngü, listenin tamamı sıralanana kadar işlemin tekrarlanmasını sağlar.
str'den int'ye
Çıktı ve Açıklama
Sağlanan Python kodunu örnek listeyle çalıştıralım ve çıktıyı gözlemleyelim:
Original List: [64, 34, 25, 12, 22, 11, 90] Sorted List: [11, 12, 22, 25, 34, 64, 90]
Burada orijinal liste [64, 34, 25, 12, 22, 11, 90] Kabarcık Sıralaması algoritması kullanılarak başarılı bir şekilde sıralanır ve sıralanmış liste [11, 12, 22, 25, 34, 64, 90] elde edilir.
Algoritma, listenin tamamı sıralanana kadar öğeleri karşılaştırarak ve değiştirerek listeyi birden çok kez yineler. Her geçişte, sıralanmamış en büyük öğe doğru konumuna 'kabarcıklar' atar. Bu işlem, listenin tamamen sıralandığını gösteren, daha fazla takas gerekmeyene kadar devam eder.
Kabarcık Sıralaması listeyi başarılı bir şekilde sıralasa da, zaman karmaşıklığının onu büyük veri kümeleri için Birleştirerek Sıralama veya Hızlı Sıralama gibi diğer sıralama algoritmalarına kıyasla daha az verimli hale getirdiğini unutmamak önemlidir.
Kabarcık Sıralamanın Zaman Karmaşıklığı
Bir algoritmanın zaman karmaşıklığını anlamak, özellikle büyük veri kümeleriyle uğraşırken verimliliğini değerlendirmek için çok önemlidir. Kabarcık Sıralamanın zaman karmaşıklığı en kötü durumda O(n^2)'dir; burada 'n', listedeki öğelerin sayısıdır.
Zaman karmaşıklığı analizini parçalara ayıralım:
- Dış döngü 'n' yineleme için çalışır; burada 'n', listedeki öğelerin sayısıdır.
- En kötü durumda iç döngü 'n' yineleme için de çalışır. Ancak algoritma ilerledikçe, en büyük sıralanmamış öğe her geçişte doğru konuma yerleştirildiğinden iç döngüdeki yineleme sayısı azalır.
- En kötü durumda, karşılaştırma ve takas sayısı listedeki öğe sayısının karesiyle orantılıdır ve bu da O(n^2) zaman karmaşıklığına neden olur. Bu, Kabarcık Sıralamasını büyük veri kümeleri için verimsiz hale getirir ve daha iyi zaman karmaşıklığına sahip daha gelişmiş sıralama algoritmaları, gerçek dünya uygulamalarında sıklıkla tercih edilir.
Çözüm
Bu makalede, tüm liste sıralanana kadar bitişik öğeleri tekrar tekrar karşılaştıran ve değiştiren basit bir sıralama algoritması olan Kabarcık Sıralaması kavramını araştırdık. Bubble Sort'un Python uygulamasını sağladık, örnek bir listeyle çalıştırdık ve çıktıyı analiz ettik. Ek olarak, Kabarcık Sıralamanın zaman karmaşıklığını tartıştık, O(n^2) en kötü durum zaman karmaşıklığını ve verimlilik üzerindeki etkilerini vurguladık.