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

Nedir BubblSırala?

Bubble Sırala Sıralama algoritması, bitişik iki değeri karşılaştırarak liste öğelerini artan sırada sıralamak için kullanılır. Birinci değer ikinci değerden büyükse, birinci değer ikinci değerin yerini alır, ikinci değer ise birinci değerin yerini alır. Birinci değer ikinci değerden küçükse, yer değiştirme olmaz.ping bitti.

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 Çözdüğü problemi, optimize edilmiş halini, adım adım görsel bir açıklamayı ve çalışma prensibini öğreneceksiniz. Python program ve performans özellikleri.

uygulanması Bubble Sıralama Algoritması

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

Sorun

Verilen listedeki öğeler rastgele bir sırayla sıralanmıştır ve biz bu öğeleri düzenli bir şekilde düzenlemek istiyoruz.

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

[21, 6, 9, 33, 3]

çözüm

Listedeki iki bitişik öğeyi karşılaştırarak ve yerlerini değiştirerek listede döngü oluşturun.ping Birinci değer ikinci değerden yüksekse, onları işaretleyin.

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 Verilen listedeki toplam öğe sayısını bulun.

) 2 Adım Yapılacak dış geçiş sayısını (n – 1) belirleyin. Uzunluğu, listedeki değerden bir çıkarılarak bulunur.

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

) 4 Adım 3. adımı, dış geçişe (n – 1) ulaşana kadar tekrarlayın. Listedeki bir sonraki öğeyi alın, ardından tüm değerler doğru artan sırada yerleştirilene 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ıralanmış listenin sonuçlarını döndürün.

) 6 Adım Optimizasyon Algoritması.

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 Takas işleminin gerçekleşip gerçekleşmediğini izleyen bir bayrak değişkeni oluşturun.ping İç döngüde meydana geldi.

) 2 Adım Değerlerin yerleri değişmişse, bir sonraki yinelemeye geçin.

) 3 Adım Değerler yer değiştirmemişse, iç döngüyü sonlandırın ve dış döngüye 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ş elemandan oluşan bir liste verildiğinde, kabarcık sıralama algoritmasının sıralama yaparken değerler arasında nasıl döngü oluşturduğunu aşağıdaki görseller göstermektedir.

Aşağıdaki görselde sıralanmamış liste gösterilmektedir:

İ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ük olduğu için 21, 6'nın yerini alırken 6 da 21'in yerini 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ük olduğu için 21 ve 9'un yerlerini değiştiriyoruz.

Yeni liste 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, bu yüzden takas yok.ping yer alır.

) 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.

Birinci yinelemenin sonunda sıralanmış liste yukarıdaki gibidir.

İ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 Ö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:

[3, 6, 9, 21, 33]

Code açıklama

Bunun için açıklama Python BubblSıralama programının kodu aşağıdaki gibidir:

İŞTE,

1. TheSeq parametresini kabul eden bubbleSort işlevini tanımlar. Kod herhangi bir çıktı vermiyor.
2. Dizinin uzunluğunu alır ve değeri n değişkenine atar. Kod herhangi bir çıktı vermez.
3. 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 herhangi bir çıktı vermez.
4. Takas işleminin gerçekleşip gerçekleşmediğini belirlemek için kullanılacak bir bayrak değişkeni tanımlar. Bu, optimizasyon amacıyla yapılır. Kod herhangi bir çıktı vermez.
5. 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.
6. 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.
7. Koşul doğruysa, theSeq[j] değerini geçici bir değişken olan tmp'ye atar. Kod herhangi bir çıktı vermez.
8. theSeq[j + 1]'in değeri, theSeq[j]'nin konumuna atanır. Kod herhangi bir çıktı vermez.
9. tmp değişkeninin değeri theSeq[j + 1] konumuna atanır. Kod herhangi bir çıktı vermez.
10. Bayrak değişkenine, takas işleminin gerçekleştiğini belirtmek için 1 değeri atanır. Kod herhangi bir çıktı vermez.
11. Kod, `flag` değişkeninin değerinin 0 olup olmadığını kontrol etmek için bir `if` ifadesi kullanır. Kod herhangi bir çıktı vermez.
12. Değer 0 ise iç döngünün dışına çıkan break ifadesini çağırırız.
13. Sıralandıktan sonra theSeq'in değerini döndürür. Kod sıralanmış listenin çıktısını verir.
14. Rastgele sayıların listesini içeren bir el değişkenini tanımlar. Kod herhangi bir çıktı vermiyor.
15. BubbleSort fonksiyonunun değerini değişken bir sonuca atar.
16. Değişken sonucunun değerini yazdırır.

Bubble sıralama avantajları

Kabarcık sıralama algoritmasının bazı avantajları şunlardır:

• Anlaması kolaydır.
• Liste zaten sıralanmış veya neredeyse sıralanmış olduğunda çok iyi performans gösteriyor.
• 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

Kabarcık sıralama algoritmasının bazı dezavantajları şunlardır:

• Büyük listeleri sıralarken iyi performans göstermez. Çok fazla zaman ve kaynak gerektirir.
• Çoğunlukla akademik amaçlarla kullanılır, gerçek dünya uygulamalarında pek kullanılmaz.
• 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ığı, listenin sıralanması için gereken yürütme süresini ve alan miktarını ifade etmek için kullanılır. Kabarcık sıralama, listedeki toplam eleman sayısı n olmak üzere, listeyi sıralamak için (n – 1) iterasyon yapar.

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, verilen listenin zaten sıralı olması durumunda gerçekleşir. Algoritma, [Big-Omega] Ω(n) olarak ifade edilen minimum sayıda çalıştırma gerçekleştirir.
• Ortalama durum – bu, listenin rastgele sırada olduğu durumlarda meydana gelir. Ortalama karmaşıklık [Büyük-teta] ⊝(n) olarak temsil edilir.²).

3) Uzay karmaşıklığı

Alan karmaşıklığı, listenin sıralanması için gereken ek alan miktarını ölçer. Kabarcık sıralama, takas için kullanılan geçici değişken için yalnızca bir (1) ek alan gerektirir.ping değerler. Bu nedenle, alan karmaşıklığı O(1)'dir.

SSS