Bubble Sıralama Algoritması Python Liste Örneği kullanarak

Nedir BubblSırala?

Bubble Sırala iki bitişik değeri karşılaştırarak liste öğelerini artan düzende sıralamak için kullanılan bir sıralama algoritmasıdır. Birinci değer ikinci değerden büyükse birinci değer ikinci değer konumunu, ikinci değer ise birinci değer konumunu alır. Birinci değer ikinci değerden küçükse takas yapılmaz.

Bu işlem, 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ş sayısı, listedeki öğe sayısının bir eksiğine eşittir.

Bu Bubble Sıralama Python öğretici öğreneceksiniz:

uygulanması Bubble Sıralama Algoritması

Uygulamayı üç (3) adıma ayıracağız: sorun, çözüm ve herhangi bir dil için kod yazmak için kullanabileceğimiz algoritma.

Sorun

Öğelerin bir listesi rastgele sırayla verilmiştir ve öğeleri düzenli bir şekilde düzenlemek istiyoruz.

Aşağıdaki listeyi göz önünde bulundurun:

[21,6,9,33,3]

çözüm

İki bitişik öğeyi karşılaştırarak 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ı şu şekilde çalışır:

) 1 Adım Toplam öğe sayısını alın. Verilen listedeki toplam öğe sayısını alın

) 2 Adım Yapılacak dış geçiş sayısını (n – 1) belirleyin. Uzunluğu liste eksi birdir

) 3 Adım Dış geçiş 1 için iç geçişleri (n – 1) kez gerçekleştirin. İlk eleman değerini alın ve ikinci değerle karşılaştırın. İkinci değer birinci değerden küçükse konumları değiştirin

) 4 Adım Dış geçişe (n – 3) ulaşana kadar 1. adımı tekrarlayın. Listedeki bir sonraki öğeyi alın ve tüm değerler doğru artan sıraya yerleştirilinceye kadar 3. adımda gerçekleştirilen işlemi tekrarlayın.

) 5 Adım Tüm geçişler tamamlandığında sonucu döndürün. Sıralanan listenin sonuçlarını döndür

) 6 Adım Algoritmayı Optimize Et

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 düzende sıralanmış öğeler içeriyorsa, döngüyü erkenden kırabiliriz.

Optimize Edilmiş Bubble Sıralama Algoritması

Varsayılan olarak, kabarcık sıralaması algoritması Python listedeki tüm öğeleri, listenin zaten sıralanmış olup olmadığına bakmaksızın 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ıralamasını 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, geri kalan değerleri yinelemeye gerek yoktur. Aşağıda gösterildiği gibi yineleme sonlandırılır ve işlem tamamlanana kadar bir sonraki başlatılır. Bubble Örneği sıralayın.

Optimizasyon aşağıdaki adımlar kullanılarak yapılır

) 1 Adım İç döngüde herhangi bir değişiklik olup olmadığını izleyen bir bayrak değişkeni oluşturun

) 2 Adım Değerlerin konumları değiştiyse sonraki yinelemeye devam edin

) 3 Adım Faydalar yer değiştirmemişse, iç döngüyü sonlandırın ve dış döngüyle devam edin.

Optimize edilmiş kabarcık sıralaması, yalnızca gerekli adımları yürüttüğü ve gerekli olmayan adımları atladığı için daha verimlidir.

Görsel sunum

Beş öğeden oluşan bir liste verildiğinde, aşağıdaki görseller, kabarcık sıralamasının değerleri sıralarken nasıl yineleme yaptığını göstermektedir

Aşağıdaki görüntü sıralanmamış listeyi göstermektedir

İlk Yineleme

) 1 Adım

Hangisinin diğerinden büyük olduğunu kontrol etmek için 21 ve 6 değerleri karşılaştırılır.

21, 6'dan büyüktür, dolayısıyla 21, 6'nın işgal ettiği konumu alırken, 6, 21'in işgal ettiği konumu alır

Değiştirilen listemiz artık yukarıdaki gibi görünüyor.

) 2 Adım

21 ve 9 değerleri karşılaştırılır.

21, 9'dan büyüktür, dolayısıyla 21 ile 9'un yerlerini değiştiririz

Yeni liste artık yukarıdaki gibidir

) 3 Adım

21 ve 33 değerleri karşılaştırılarak büyük olanı bulunur.

33 değeri 21'den büyük olduğundan herhangi bir değişiklik yapılmaz.

) 4 Adım

33 ve 3 değerleri karşılaştırılarak büyük olanı bulunur.

33 değeri 3'ten büyük olduğu için konumlarını değiştiriyoruz.

İlk yinelemenin sonunda sıralanan liste yukarıdaki gibi

İkinci Yineleme

İkinci yinelemeden sonra yeni liste aşağıdaki gibidir

Üçüncü Yineleme

Üçüncü yinelemeden sonra yeni liste aşağıdaki gibidir

Dördüncü Yineleme

Dördüncü yinelemeden sonra yeni liste aşağıdaki gibidir

Python Örnekler

Aşağıdaki kod, bunun nasıl uygulanacağını gösterir Bubble Sıralama algoritması Python.

def bubbleSort( theSeq ):
    n = len( theSeq )

    for i in range( n - 1 ) :
        flag = 0

        for j in range(n - 1) :
            
            if theSeq[j] > theSeq[j + 1] : 
                tmp = theSeq[j]
                theSeq[j] = theSeq[j + 1]
                theSeq[j + 1] = tmp
                flag = 1

        if flag == 0:
            break

    return theSeq

el = [21,6,9,33,3] 

result = bubbleSort(el)

print (result)

Yukarıdaki kabarcık sıralama programını çalıştırmak Python aşağıdaki sonuçları üretir

[6, 9, 21, 3, 33]

Kod Açıklama

Bunun için açıklama Python Bubble Sıralama programı kodu aşağıdaki gibidir

İŞTE,

TheSeq parametresini kabul eden bubbleSort işlevini tanımlar. Kod herhangi bir çıktı vermiyor.
Dizinin uzunluğunu alır ve değeri bir n değişkenine atar. Kod hiçbir şey çıkarmıyor
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 çıkarmıyor
Bir takasın gerçekleşip gerçekleşmediğini belirlemek için kullanılacak bir bayrak değişkenini tanımlar. Bu optimizasyon amaçlıdır. Kod hiçbir şey çıkarmıyor
Listedeki tüm değerleri ilk değerden son değere kadar karşılaştıran iç döngüyü başlatır. Kod hiçbir şey çıktı vermez.
Sol taraftaki değerin hemen sağ taraftaki değerden büyük olup olmadığını kontrol etmek için if ifadesini kullanır. Kod herhangi bir çıktı vermiyor.
Koşul doğru olarak değerlendirilirse Seq[j] değerini geçici bir tmp değişkenine atar. Kod hiçbir şey çıkarmıyor
Sıra[j + 1]'in değeri Sıra[j]'nin konumuna atanır. Kod hiçbir şey çıkarmıyor
Tmp değişkeninin değeri Sıra[j + 1] konumuna atanır. Kod hiçbir şey çıkarmıyor
Bayrak değişkenine takasın gerçekleştiğini belirtmek için 1 değeri atanır. Kod hiçbir şey çıkarmıyor
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ünün dışına çıkan break ifadesini çağırırız.
Sıralandıktan sonra theSeq'in değerini döndürür. Kod sıralanmış listenin çıktısını verir.
Rastgele sayıların listesini içeren bir el değişkenini tanımlar. Kod herhangi bir çıktı vermiyor.
BubbleSort fonksiyonunun değerini değişken bir sonuca atar.
Değişken sonucunun değerini yazdırır.

Bubble sıralama avantajları

Aşağıda kabarcık sıralama algoritmasının bazı avantajları listelenmiştir

anlamak kolaydır
Liste zaten sıralandığında veya neredeyse sıralandığında çok iyi performans gösterir
Geniş hafıza gerektirmez.
Algoritmanın kodunu yazmak kolaydır
Diğer sıralama algoritmalarına kıyasla alan gereksinimleri minimum düzeydedir.

BubblDezavantajları sıralayın

Aşağıda kabarcık sıralama algoritmasının bazı dezavantajları listelenmiştir

Büyük listeleri sıralarken iyi performans göstermez. Çok fazla zaman ve kaynak gerektirir.
Gerçek dünyadaki uygulamalar için değil, çoğunlukla akademik amaçlar için kullanılır.
Listeyi sıralamak için gereken adım sayısı n mertebesindedir²

Karmaşıklık Analizi Bubble Sırala

Karmaşıklığın üç türü vardır:

1) Karmaşıklığı sıralayın

Sıralama karmaşıklığı, listeyi sıralamak için gereken yürütme zamanlarını ve alanı ifade etmek için kullanılır. Kabarcık sıralaması, listeyi sıralamak için (n – 1) yineleme yapar; burada n, listedeki toplam öğe sayısıdır.

2) Zaman karmaşıklığı

Kabarcık sıralamasının zaman karmaşıklığı O(n)'dir²)

Zaman karmaşıklıkları şu şekilde kategorize edilebilir:

En kötü durumda – sağlanan listenin azalan sırada olduğu yer burasıdır. Algoritma, [Big-O] O(n) olarak ifade edilen maksimum yürütme sayısını gerçekleştirir.²)
En iyi senaryo – bu, sağlanan liste zaten sıralandığında gerçekleşir. 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 meydana gelir. Ortalama Karmaşıklık [Büyük-teta] ⊝(n) olarak gösterilir²)

3) Uzay karmaşıklığı

Uzay karmaşıklığı, listeyi sıralamak için gereken ekstra alan miktarını ölçer. Kabarcık sıralaması, değerleri takas etmek için kullanılan zamansal değişken için yalnızca bir (1) ekstra alan gerektirir. Bu nedenle, O (1) uzay karmaşıklığına sahiptir.

ÖZET

Kabarcık 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.
Bir kabarcık sıralama algoritmasını uygulamak nispeten basittir Python. Kullanmanız gereken tek şey for döngüleri ve if ifadeleridir.
Kabarcık sıralama algoritmasının çözdüğü problem, rastgele bir öğe listesini alıp onu sıralı bir listeye dönüştürmektir.
Veri yapısındaki kabarcık sıralama algoritması, minimum sayıda yineleme gerçekleştirdiğinden liste zaten sıralandığında en iyi performansı gösterir.
Liste ters sırada olduğunda kabarcık sıralama algoritması iyi performans göstermez.
Bubbler sıralaması O (n) zaman karmaşıklığına sahiptir²) ve O (1) uzay karmaşıklığı
Kabarcık sıralama algoritması, gerçek dünyadaki uygulamalar için değil, akademik amaçlar için en uygunudur.
Optimize edilmiş kabarcık sıralaması, önceden sıralanmış değerleri kontrol ederken gereksiz yinelemeleri atlayarak algoritmayı daha verimli hale getirir.

Beğenebilirsin: