Python Merge Sort (Birleştirme Sıralaması)

0
71

Verinin hafızada sıralı tutulması için geliştirilen sıralama algoritmalarından (sorting algorithms) bir tanesidir. Basitçe sıralanacak olan diziyi ikişer elemanı kalan parçalara inene kadar sürekli olarak ikiye böler. Sonra bu parçaları kendi içlerinde sıralayarak birleştirir. Sonuçta elde edilen dizi sıralı dizinin kendisidir. Bu açıdan bir parçala fethet (divide and conquere) yaklaşımıdır.

Python Merge Sort algoritması ile sıralayalım

Sıralanmak istenen verimiz:

5,7,2,9,6,1,3,7

olsun. Bu verilerin bir oluşumun(composition) belirleyici alanları olduğunu düşünebiliriz. Yani örneğin vatandaşlık numarası veya öğrenci numarası gibi. Dolayısıyla örneğin öğrencilerin numaralarına göre sıralanması durumunda kullanılabilir.

Python Merge Sort Birleştirme sıralamasının çalışması yukarıdaki bu örnek dizi üzerinde adım adım gösterilmiştir. Öncelikle parçalama adımları gelir. Bu adımlar aşağıdadır.

1. adım diziyi ikiye böl:

5,7,2,9 ve 6,1,3,7

2. adım çıkan bu dizileri de ikiye böl:

5,7 ; 2,9 ; 6,1 ; 3,7

3. adım elde edilen parçalar 2 veya daha küçük eleman sayısına ulaştığı için dur (aksi durumda bölme işlemi devam edecekti)

4. adım her parçayı kendi içinde sırala

5,7 ; 2,9 ; 1,6 ; 3,7

5. Her bölünmüş parçayı birleştir ve birleştirirken sıraya dikkat ederek birleştir (1. ve 2. parçalar ile 3. ve 4. parçalar aynı gruptan bölünmüştü)

2,5,7,9 ve 1,3,6,7
6. adım, tek bir bütün parça olmadığı için birleştirmeye devam et

1,2,3,5,6,7,7,9

7. adım sonuçta bir bütün birleşmiş parça olduğu için dur. İşte bu sonuç dizisi ilk dizinin sıralanmış halidir.

Python Merge Sort (Birleştirme Sıralamasının) Python dilinde yazılmış bir örnek kodu aşağıda verilmiştir:

/usr/bin/env python
– coding: utf-8 –
def yonet(ilk_parca, ikinci_parca):
c = []
while len(ilk_parca) != 0 and len(ikinci_parca) != 0:
if ilk_parca[0] < ikinci_parca[0]:
c.append(ilk_parca[0])
ilk_parca.remove(ilk_parca[0])
else:
c.append(ikinci_parca[0])
ikinci_parca.remove(ikinci_parca[0])
if len(ilk_parca) == 0:
c = c + ikinci_parca
else:
c = c + ilk_parca
return c
def bol(x):
if len(x) == 0 or len(x) == 1:
return x
else:
kes = len(x)/2
ilk_parca = bol(x[:kes])
ikinci_parca = bol(x[kes:])
return yonet(ilk_parca, ikinci_parca)
print bol([90,80,70,60,50,40,30,20,10,5,4,3,2,1])

Python Tutorial

Bir Cevap Yazın

This site uses Akismet to reduce spam. Learn how your comment data is processed.