1 dk, tahmini okuma süresi
Python İle Birleştirme Sıralamasi
En Son Güncelleme: 26 Eylül, 2022Muhtemelen en sevdiğim ve aynı zamanda anlamamın en uzun süren sıralama algoritması. Umarım bu algoritmanın nasıl çalıştığını kavramanızı kolaylaştırabilirim. Temel olarak dizimizi (veya listemizi), parçalar sıralayacak kadar küçük olana kadar özyinelemeli (recursion) olarak böleriz. Sonunda parçaları sıralamaya ve "birleştirmeye" başlayabiliriz. Kulağa gerçekten basit geliyor değil mi? Hadi başlayalım!
§An Example to Help Us Understand
First of all I assume you understand the basic recursion. As we won't really do something complicated don't worry if you are not an expert at recursion.
§Anlamamıza Yardımcı Olacak Bir Örnek
arr = [42, 25, 37, 2, 11, 76, 12]
Bölmeye ve yinelemeli olarak sol taraftan ayırmaya/birleştirmeye başlayacağız. İlk adımda:
[42, 25, 37, 2] --- [11, 76, 12]
İkinci adımda:
[42, 25] --- [37, 2] --- [11, 76, 12]
Üçüncü adımda:
[42] --- [25] --- [37, 2] --- [11, 76, 12]
Şimdi sol taraftan sıralamaya başlayabiliriz. Diyelim ki dizimizde minimumdan maksimuma gitmek istiyoruz. Öncelikle 42 ve 25 değerlerin sıralayacağız. Yani dördüncü adımda:
[25, 42] --- [37, 2] --- [11, 76, 12]
Beşinci adımda:
[25, 42] --- [37] --- [2] --- [11, 76, 12]
Altıncı adımda:
[25, 42] --- [2, 37] --- [11, 76, 12]
Yedinci adımda:
[2, 25, 37, 42] --- [11, 76, 12]
Sekizinci adımda:
[2, 25, 37, 42] --- [11, 76] --- [12]
Dokuzuncu adımda:
[2, 25, 37, 42] --- [11] --- [76] --- [12]
Onuncu adımda:
[2, 25, 37, 42] --- [11, 76] --- [12]
Onbirinci adımda:
[2, 25, 37, 42] --- [11, 12, 76]
Ve son olarak on ikinci adımda:
[2, 11, 12, 25, 37, 42, 76]
Bu algoritma, böl ve yönet algoritmalarının önemini anlamamıza yardımcı oluyor. Problemi çözmesi daha kolay olan daha küçük parçalara bölüyoruz.
Bu algoritmanın kodu da aslında şöyle:
def mergeSort(nums):
if len(nums) <= 1:
return nums
if len(nums) > 1:
mid = len(nums) // 2
left = nums[:mid]
right = nums[mid:]
mergeSort(left)
mergeSort(right)
i = 0
j = 0
k = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
nums[k] = left[i]
i += 1
else:
nums[k] = right[j]
j += 1
k += 1
while i < len(left):
nums[k] = left[i]
i += 1
k += 1
while j < len(right):
nums[k] = right[j]
j += 1
k += 1
numbers = [42, 25, 37, 2, 11, 76, 12]
mergeSort(numbers)
print(numbers)
§Birleştirme Sıralamasının Karmaşıklığı
Birleştirme sıralaması için zaman karmaşıklığı O(nlogn)'dir, çünkü dizimizi yaklaşık olarak iki n defaya bölüyoruz. Gördüğünüz gibi, bu metod nispeten daha büyük dizileri/listeleri sıralamak için ideal olmayabilir. Nispeten daha küçük bağlantılı listelerde birleştirme sıralamasını kullanmamız önerebilirim.
Birleştirme sıralamasının yer (alan) karmaşıklığı O(n)'dir. Tüm bu alt dizileri daha sonra sıralamak için oluşturmak elbette bize pahalıya mal olacaktı. Bu nedenle, alanınız kısıtlıysa, birleştirme sıralamasını seçmeyin.
Kararlılık (Stabilite) açısından, birleştirme sıralamasının kararlı olduğundan emin olabiliriz. Elemanları karşılaştırmak için sol < sağ ölçümünü kullanıyoruz. Eşitlik durumunda önce soldaki değeri sonra da sağdaki değeri dizimize kopyalarız. Böylece düzenimiz korunmuş olur. Bu, birleştirme sıralamasının kararlı olduğunu kanıtlar.
Öğrenmeye devam edin!
Ilker Akbiyikİçindekiler
Benzer Paylaşımlar
