Bubble Sort Algoritması

Aşağıdaki adreste Python3 ile örneklediğimiz bubble sort algoritmasını detaylı olarak açıklıyoruz. 

https://github.com/ismetyaksi/Python3/blob/main/python3_bubble_sort_240730.py

Sort sıralama demek. Bubble da kabarcık. Elimizdeki karışık bir listeyi azalan veya artan sıraya dizeceğiz. Bubble sort, bu işlerde kullanabileceğimiz karışık olmayan bir algoritmadır.

Önce bir dizi oluşturalım. Python programlama dilinde diziye liste diyoruz. Sıralayacağımız listenin elemanları metin (text) veya sayısal (numeric) olabilir. Örneğimizde sayısal yaptık. Büyükten küçüğe, küçükten büyüğe veya rasgele (random) sayı dizileri üretmek, karakter katarları (character string) üretmekten daha kolay. Ama uygulamayı bir kez geliştirdikten sonra elinizdeki sorunu çözmek için her türlü veri ile kullanabilirsiniz.

listeyi oluşturmak için bir fonksiyon yazdık. Girdi (input) olarak iki parametre alıyor. Birincisi listedeki eleman sayısı. Uygulamayı geliştirmeye 10 ile başladık, 100 ile devam ettik. 1000 ile tamamladık.

def init_list(len1, order1):

    random.seed(17)

    list1 = []

    for ix1 in range(len1):

        if (order1 == "ascending"):

            list1.append(ix1)

        elif (order1 == "descending"):

            list1.append(len1-ix1)

        else:

            list1.append(random.randint(len1, 2*len1))

    return(list1)

İkinci parametre hazırlanacak test verisinin tipi. Normal olarak listeyi rasgele (random) sayılarla oluşturmak yeterlidir ama en kötü durum (worst case) senaryoları karşılaştırmaları yapabilmek için ikinci parametreyi ekledik. Artan sıraya dizmek için azalan sırada liste ve azalan sıraya dizmek için artan sırada liste de kullandık.

Uygulamada azalan ve artan sıraya dizme bölümleri yanısıra kaynak kullanımını azaltmak için iyileştirmeler yaptık. Bu iyileştirmelerin sonuçlarını karşılaştırabilmek için bütün sıralama işlemlerini aynı verilerle yapmamız önemliydi. Rasgele sayılar oluştururken seed (tohumlama) işlemi yaptık. Böylece her sıralama için aynı sayı sıralarının kullanılmasını sağladık.

Aşağıdan başlıyoruz. Artan sıraya dizeceğimizi düşünelim. Önce sondan bir önceki elemanı son eleman ile karşılaştırıyoruz. Son eleman daha küçükse ikisini yer değiştiriyoruz (swap). Daha sonra sondan ikinci eleman ile sondan üçüncü elemanı karşılaştırıyoruz. Sıradaysa sorun yok. Değilse yer değiştiriyoruz. Bu şekilde her döngüde (loop) en küçük veya en büyük eleman sudaki bir kabarcık gibi en yukarıya geliyor. Algoritmanın adı da buradan geliyor.

Yer değiştirmek için bir elemanı geçici bir değişkene atıyoruz (assign). İkinci elemanı onun yerine atıyoruz. Son işlem olarak geçici değişkendeki değeri ikinci elemana atıyoruz. Atıyoruz derken atama yapıyoruz demek istiyoruz.

n_iterations = 0

n_swaps = 0

for ix1 in range(len(list1)-1, 0, -1):      # iterate bottom up

    for ix2 in range(ix1):  

        #print("1 >>>", ix1, ix2)

        n_iterations += 1

        if (list1[ix2] > list1[ix2+1]):     # swap if greater than next item

            n_swaps += 1

            tmp1 = list1[ix2]

            list1[ix2] = list1[ix2+1]

            list1[ix2+1] = tmp1

İlk örneğimizde liste elemanlarını artan sıraya (ascending) diziyoruz. Bu arada karşılaştırma yapabilmek için yineleme (iteration) ve değiştirmeleri saydırıyoruz.

Sıralama sonunda listemizin sıralı olup olmadığını doğruluyoruz. Python programlama dilinin sorted fonksiyonunu kullanıyoruz. Python fonksiyonu ile sıraladığımız liste, bizim sıraladığımız liste aynı ise sorun yok. Yineleme ve değiştirmeleri ekranda görüntülüyoruz.

if (list1 == sorted(list1)):                # test whether sort order correct or not

    print("1 >>> #iterations", f"{n_iterations:,d}")

    print("1 >>> #swaps.....", f"{n_swaps:,d}")

    print()

else:

    print("1 >>> sort order not ok!", list1)

    exit()

print("1 >>> sort ascending optimized")

print()

Yok eğer bir yazım hatası veya mantık hatası nedeniyle sonuç doğru değilse ekrana uyarı yazılarak programın devam etmeden bitmesini sağlıyoruz.

Yaptığımız iyileştirme (optimization) ikinci iç döngünün başında değişim olduğunu gösteren doğru-yanlış (true-false) tipi bir mantıksal değişken tanımlamak oldu. Başlangıçta yanlış değeri ile atama yapıyoruz. Eğer iç döngü içinde yer değiştirme gerçekleşirse, değişkeni bunu belirtecek şekilde değiştiriyoruz. İç döngü sonunda değiştirme olup olmadığını kontrol ediyoruz. Eğer değiştirme olmamışsa listenin sıraya girmiş olduğunu değerlendirerek ilk döngüden de çıkarak sıralamayı tamamlamış oluyoruz. 

for ix1 in range(len(list1)-1, 0, -1):      # iterate bottom up

    any_swap = False                        # reset inner swap flag

    for ix2 in range(ix1):  

        #print("1 >>>", ix1, ix2)

        n_iterations += 1

        if (list1[ix2] > list1[ix2+1]):     # swap if greater than next item

            any_swap = True                 # set swap flag

            n_swaps += 1

            tmp1 = list1[ix2]

            list1[ix2] = list1[ix2+1]

            list1[ix2+1] = tmp1

    if (not any_swap):                      # If no inner swaps, already ordered, terminate

      break

Artan, azalan sıralamalar ve iyileştirmeli çalıştırmalarla programımız aşağıdaki şekilde bir çıktı üretiyor.

 0 >>> list size.. 1,000

1 >>> sort ascending

1 >>> #iterations 499,500

1 >>> #swaps..... 256,297

1 >>> sort ascending optimized

1 >>> #iterations 499,269

1 >>> #swaps..... 256,297

2 >>> sort descending

2 >>> #iterations 499,500

2 >>> #swaps..... 242,729

2 >>> sort descending optimized

2 >>> #iterations 497,609

2 >>> #swaps..... 242,729

Gördüğünüz gibi elimizdeki girdi veri yapısıyla yinelemelerde sağladığımız iyileştirmeler artan sıralamada 499,500 - 499,269 = 231,  azalan sıralamada 499,500 - 497,609 = 1,891.