Python Binary Insertion Sort Algoritması

Herkese merhaba, Python yazılarımıza kaldığımız yerden devam ediyoruz. Bu yazımızda sıralama algoritmalarından biri olan Binary Insertion Sort Algoritması’nı anlatacağım. Hadi başlayalım !

Binary Insertion Sort Algoritması

Binary Insertion Sort, Insertion Sort algoritmasının bir varyasyonudur. Bu algoritma, sıralanacak olan verilerin sayısının artmasıyla birlikte, Insertion Sort algoritmasının verimliliğini arttırmak için kullanılır.

Bu algoritma, Insertion Sort algoritmasına benzer bir şekilde çalışır. Fakat burada elemanları doğrudan yerlerine yerleştirmek yerine, elemanların sıralı dizideki yerlerini binary search yaparak bulur ve sonra ilgili konuma yerleştirir. Böylece, elemanların yerleştirilmesi için gereken işlem sayısı azalır ve dolayısıyla algoritmanın çalışma süresi azalır.

Python Kodu

Şimdi, Binary Insertion Sort algoritmasını Python dilinde yazalım:

def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        left, right = 0, i - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] > key:
                right = mid - 1
            else:
                left = mid + 1
        for j in range(i - 1, left - 1, -1):
            arr[j + 1] = arr[j]
        arr[left] = key

Kod Açıklamaları

Yukarıdaki kodda, binary_insertion_sort fonksiyonu, sıralanacak olan diziyi parametre olarak alır ve algoritmanın geri kalan kısmını uygular. Dizinin ilk elemanı zaten sıralı olduğu için, sıralama işlemi 2. elemandan başlar. Bu nedenle, for döngüsü range(1, len(arr)) aralığında çalışır.

İlk olarak, sıralanacak olan eleman key değişkenine atanır ve binary search yapmak için left ve right pointerları tanımlanır. Daha sonra, left ve right pointerları arasındaki orta nokta mid hesaplanır.

Eğer arr[mid] değeri key değerinden büyükse, key değerinin sol tarafındaki elemanlar arasında arama yapılması gerektiği anlaşılır ve right pointerı mid – 1 değeriyle güncellenir. Eğer arr[mid] değeri key değerinden küçük veya eşitse, key değerinin sağ tarafındaki elemanlar arasında arama yapılması gerektiği anlaşılır ve left pointerı mid + 1 değeriyle güncellenir.

Bu işlemler bittikten sonra, key değeri doğru pozisyona yerleştirilir. Bunun için, for döngüsü range(i – 1, left – 1, -1) aralığında çalışır ve elemanların sağa kaydırılması işlemi yapılır. Son olarak, key değeri, doğru pozisyona yerleştirilir.

Örnek Kullanım

Yukarıdaki kodu, aşağıdaki gibi kullanabiliriz:

# Örnek kullanım
arr = [5, 2, 4, 6, 1, 3]
binary_insertion_sort(arr)
print(arr) # [1, 2, 3, 4, 5, 6]

Yukarıdaki örnek kullanımda, arr adlı dizi, sıralanacak olan verileri içerir. binary_insertion_sort fonksiyonu bu diziyi parametre olarak alır ve sıralama işlemini gerçekleştirir. Sonuç olarak, dizi sıralanmış bir şekilde ekrana yazdırılır.

Sonuç

Binary Insertion Sort algoritması, Insertion Sort algoritmasına göre daha verimlidir. Ancak, büyük veri setleri için bile en iyi performansı sağlamaz. Daha büyük veri setleri için daha iyi sıralama algoritmaları mevcuttur.

Evet Python’da Binary Insertion Sort Algoritması bu şekilde yazılmakta. Tüm Python yazılarımıza buraya, diğer sıralama algoritmaları ile ilgili yazılarımıza buraya tıklayarak ulaşabilirsiniz. Herkese hayırlı günler.