Kabarcık Sıralama nedir?
Kabarcık Sıralama , iki bitişik değeri karşılaştırarak liste öğelerini artan sırada sıralamak için kullanılan bir sıralama algoritmasıdır. İlk değer ikinci değerden yüksekse, birinci değer ikinci değer konumunu alırken, ikinci değer ilk değer konumunu alır. İlk değer ikinci değerden düşükse, takas yapılmaz.
Bu işlem, bir listedeki tüm değerler karşılaştırılana ve gerekirse değiştirilene kadar tekrarlanır. Her yinelemeye genellikle geçiş adı verilir. Kabarcık sıralamasındaki geçişlerin sayısı, bir listedeki öğelerin sayısı eksi bire eşittir.
Bu Python'da Kabarcık Sıralama eğitiminde şunları öğreneceksiniz:
- Kabarcık Sıralama nedir?
- Kabarcık Sıralama Algoritmasını Uygulama
- Optimize Edilmiş Kabarcık Sıralama Algoritması
- Görsel sunum
- Python Örnekleri
- Kod Açıklama
- Kabarcık sıralama avantajları
- Kabarcık sıralama Dezavantajları
- Kabarcık Sıralamasının Karmaşıklık Analizi
Kabarcık Sıralama Algoritmasını Uygulama
Uygulamayı üç (3) adıma, yani problem, çözüm ve herhangi bir dil için kod yazmak için kullanabileceğimiz algoritmaya ayıracağız.
Sorun
Öğelerin bir listesi rastgele sırayla verilir ve öğeleri düzenli bir şekilde düzenlemek istiyoruz.
Aşağıdaki listeyi düşünün:
[21,6,9,33,3]
Çözüm
İki bitişik öğeyi karşılaştıran listeyi yineleyin ve ilk değer ikinci değerden yüksekse bunları değiştirin.
Sonuç aşağıdaki gibi olmalıdır:
[3,6,9,21,33]
Algoritma
Kabarcık sıralama algoritması aşağıdaki gibi çalışır
Adım 1) Toplam eleman sayısını alın. Verilen listedeki toplam öğe sayısını alın
Adım 2) Yapılacak dış geçişlerin (n - 1) sayısını belirleyin. Uzunluğu liste eksi bir
Adım 3) Dış geçiş 1 için iç geçişler (n - 1) kez gerçekleştirin. İlk eleman değerini alın ve ikinci değerle karşılaştırın. İkinci değer ilk değerden düşükse, pozisyonları değiştirin
Adım 4) Dış geçide (n - 1) ulaşana kadar 3. adım geçişlerini tekrarlayın. Listedeki bir sonraki öğeyi alın, ardından tüm değerler doğru artan sıralarına yerleştirilene kadar 3. adımda gerçekleştirilen işlemi tekrarlayın.
Adım 5) Tüm geçişler tamamlandığında sonucu geri verin. Sıralanmış listenin sonuçlarını döndür
Adım 6) Algoritmayı Optimize Edin
Liste veya bitişik değerler zaten sıralanmışsa, gereksiz iç geçişlerden kaçının. Örneğin, sağlanan liste zaten artan sırada sıralanmış öğeler içeriyorsa, döngüyü erken kırabiliriz.
Optimize Edilmiş Kabarcık Sıralama Algoritması
Varsayılan olarak, Python'daki kabarcık sıralama algoritması, listenin önceden sıralanmış olup olmadığına bakılmaksızın listedeki tüm öğeleri karşılaştırır. Verilen liste zaten sıralanmışsa, tüm değerleri karşılaştırmak zaman ve kaynak israfıdır.
Kabarcık sıralamayı optimize etmek, gereksiz yinelemelerden kaçınmamıza ve zamandan ve kaynaklardan tasarruf etmemize yardımcı olur.
Örneğin, birinci ve ikinci öğeler zaten sıralanmışsa, değerlerin geri kalanını yinelemeye gerek yoktur. Yineleme sonlandırılır ve bir sonraki, aşağıdaki Kabarcık Sıralama örneğinde gösterildiği gibi işlem tamamlanana kadar başlatılır.
Optimizasyon aşağıdaki adımlar kullanılarak yapılır
Adım 1) İç döngüde herhangi bir takas olup olmadığını izleyen bir bayrak değişkeni oluşturun
Adım 2) Değerler konum değiştirdiyse, bir sonraki yinelemeye devam edin
Adım 3) Faydalar konumları değiştirmediyse, iç döngüyü sonlandırın ve dış döngü ile devam edin.
Optimize edilmiş bir balon sıralaması, yalnızca gerekli adımları yürüttüğü ve gerekmeyenleri atladığı için daha verimlidir.
Görsel sunum
Beş öğeden oluşan bir liste verildiğinde, aşağıdaki resimler, balon sıralamanın değerleri sıralarken nasıl yinelediğini gösterir.
Aşağıdaki görüntü sıralanmamış listeyi göstermektedir
İlk Yineleme
Aşama 1)
21 ve 6 değerleri, hangisinin diğerinden daha büyük olduğunu kontrol etmek için karşılaştırılır.
21, 6'dan büyüktür, bu nedenle 21, 6'nın işgal ettiği konumu alırken, 6, 21'in işgal ettiği konumu alır.
Değiştirilmiş listemiz şimdi yukarıdaki gibi görünüyor.
Adım 2)
21 ve 9 değerleri karşılaştırılır.
21, 9'dan büyük olduğundan, 21 ve 9'un konumlarını değiştiriyoruz
Yeni liste şimdi yukarıdaki gibidir
Aşama 3)
Daha büyük olanı bulmak için 21 ve 33 değerleri karşılaştırılır.
33 değeri 21'den büyüktür, bu nedenle takas yapılmaz.
Adım 4)
Daha büyük olanı bulmak için 33 ve 3 değerleri karşılaştırılır.
33 değeri 3'ten büyük, bu yüzden konumlarını değiştiriyoruz.
İlk yinelemenin sonundaki sıralanmış liste, yukarıdaki gibi
İkinci Yineleme
İkinci yinelemeden sonraki yeni liste aşağıdaki gibidir
Üçüncü Yineleme
Üçüncü yinelemeden sonraki yeni liste aşağıdaki gibidir
Dördüncü Yineleme
Dördüncü yinelemeden sonraki yeni liste aşağıdaki gibidir
Python Örnekleri
Aşağıdaki kod, Kabarcık Sıralama algoritmasının Python'da nasıl uygulanacağını gösterir.
def bubbleSort( theSeq ):n = len( theSeq )for i in range( n - 1 ) :flag = 0for j in range(n - 1) :if theSeq[j] > theSeq[j + 1] :tmp = theSeq[j]theSeq[j] = theSeq[j + 1]theSeq[j + 1] = tmpflag = 1if flag == 0:breakreturn theSeqel = [21,6,9,33,3]result = bubbleSort(el)print (result)
Yukarıdaki kabarcık sıralama programını Python'da çalıştırmak aşağıdaki sonuçları verir
[6, 9, 21, 3, 33]
Kod Açıklama
Python Bubble Sort program kodunun açıklaması aşağıdaki gibidir
İŞTE,
- TheSeq parametresini kabul eden bubbleSort işlevini tanımlar. Kod herhangi bir çıktı vermez.
- Dizinin uzunluğunu alır ve değeri bir değişken n'ye atar. Kod hiçbir şey vermiyor
- Kabarcık sıralama algoritmasını (n - 1) kez çalıştıran bir for döngüsü başlatır. Bu dış döngüdür. Kod hiçbir şey vermiyor
- Bir takasın olup olmadığını belirlemek için kullanılacak bir bayrak değişkenini tanımlar. Bu, optimizasyon amaçlıdır. Kod hiçbir şey vermiyor
- Listedeki tüm değerleri ilkinden sonuncusuna kadar karşılaştıran iç döngüyü başlatır. Kod herhangi bir çıktı vermez.
- Sol taraftaki değerin hemen sağ taraftakinden büyük olup olmadığını kontrol etmek için if ifadesini kullanır. Kod herhangi bir çıktı vermez.
- Koşul true olarak değerlendirilirse, Eşit [j] değerini bir geçici değişken tmp'ye atar. Kod hiçbir şey vermiyor
- Eşit [j + 1] 'in değeri, Eşit [j] konumuna atanır. Kod hiçbir şey vermiyor
- Tmp değişkeninin değeri, Eşit [j + 1] 'i konumlandırmak için atanır. Kod hiçbir şey vermiyor
- Bayrak değişkenine, bir takasın gerçekleştiğini belirtmek için 1 değeri atanır. Kod hiçbir şey vermiyor
- Değişken bayrağının değerinin 0 olup olmadığını kontrol etmek için bir if ifadesi kullanır. Kod herhangi bir çıktı vermez.
- Değer 0 ise, iç döngüden çıkan break ifadesini çağırırız.
- Sıralandıktan sonra Eşiğin değerini döndürür. Kod, sıralı listeyi çıkarır.
- Rastgele sayıların bir listesini içeren bir el değişkenini tanımlar. Kod herhangi bir çıktı vermez.
- BubbleSort işlevinin değerini değişken bir sonuca atar.
- Değişken sonucunun değerini yazdırır.
Kabarcık sıralama avantajları
Aşağıdakiler, kabarcık sıralama algoritmasının avantajlarından bazılarıdır
- Anlaması kolay
- Liste halihazırda veya neredeyse sıralandığında çok iyi performans gösterir
- Kapsamlı hafıza gerektirmez.
- Algoritma için kod yazmak kolaydır
- Alan gereksinimleri, diğer sıralama algoritmalarına kıyasla minimumdur.
Kabarcık sıralama Dezavantajları
Aşağıdakiler, kabarcık sıralama algoritmasının bazı dezavantajlarıdır
- Büyük listeleri sıralarken iyi performans göstermez. Çok fazla zaman ve kaynak gerektirir.
- Çoğunlukla akademik amaçlar için kullanılır, gerçek dünya uygulaması için değil.
- Listeyi sıralamak için gereken adım sayısı n 2 düzenindedir
Kabarcık Sıralamasının Karmaşıklık Analizi
Üç tür Karmaşıklık vardır:
1) Karmaşıklığı sıralayın
Sıralama karmaşıklığı, listeyi sıralamak için gereken yürütme süreleri ve alanı miktarını ifade etmek için kullanılır. Kabarcık sıralaması, listedeki n'nin listedeki toplam öğe sayısı olduğu (n - 1) yineleme yapar.
2) Zaman karmaşıklığı
Kabarcık sıralamanın zaman karmaşıklığı O (n 2 )
Zaman karmaşıklıkları şu şekilde kategorize edilebilir:
- En kötü durum - bu, sağlanan listenin azalan sırada olduğu yerdir. Algoritma, [Big-O] O (n 2 ) olarak ifade edilen maksimum yürütme sayısını gerçekleştirir.
- En iyi durum - bu, sağlanan liste zaten sıralandığında ortaya çıkar. Algoritma, [Big-Omega] Ω (n) olarak ifade edilen minimum yürütme sayısını gerçekleştirir.
- Ortalama durum - bu, liste rastgele sırada olduğunda ortaya çıkar. Ortalama Karmaşıklık [Büyük-teta] ⊝ (n 2 ) olarak temsil edilir.
3) Uzay karmaşıklığı
Alan karmaşıklığı, listeyi sıralamak için gereken fazladan alan miktarını ölçer. Kabarcıklı sıralama, değerleri takas etmek için kullanılan geçici değişken için yalnızca bir (1) fazladan boşluk gerektirir. Bu nedenle, O (1) uzay karmaşıklığına sahiptir.
Özet
- Kabarcıklı sıralama algoritması, iki bitişik değeri karşılaştırarak ve soldaki değer sağdaki değerden küçükse bunları değiştirerek çalışır.
- Kabarcık sıralama algoritması uygulamak Python ile nispeten basittir. Kullanmanız gereken tek şey döngüler ve if ifadeleridir.
- Kabarcık sıralama algoritmasının çözdüğü sorun, rastgele bir öğe listesi alıp sıralı bir listeye dönüştürmektir.
- Veri yapısındaki balonlu sıralama algoritması, minimum sayıda yineleme gerçekleştirdiği için liste önceden sıralandığında en iyi performansı gösterir.
- Kabarcık sıralama algoritması, liste ters sırada olduğunda iyi performans göstermez.
- Fıskiye sıralaması, O (n 2 ) zaman karmaşıklığına ve O (1) uzay karmaşıklığına sahiptir.
- Bubbler sıralama algoritması, gerçek dünya uygulamaları için değil akademik amaçlar için en uygun olanıdır.
- Optimize edilmiş balon sıralaması, önceden sıralanmış değerleri kontrol ederken gereksiz yinelemeleri atlayarak algoritmayı daha verimli hale getirir.