Python Birleştirme Sıralama Algoritması Eğitimi
Python'da Birleştirme Sıralamasını nasıl uygulayacağınızı öğrenin. Böl ve Fethet sıralama stratejisinin etkileşimli, adım adım bir örneği.
Genel Bakış
Merge Sort, böl ve yönet stratejisini kullanan oldukça verimli bir sıralama algoritmasıdır. Sıralanmamış bir listeyi daha küçük alt listelere böler, bu alt listeleri sıralar ve ardından bunları tekrar birleştirir.
Algoritma, diziyi tek öğeli alt dizilere ulaşana kadar yinelemeli olarak ikiye böler. Daha sonra sıralanan alt dizileri, her iki taraftaki öğeleri karşılaştırıp sıralı düzene yerleştirerek birleştirir. Bu, optimum zaman karmaşıklığını garanti eder.
Başlangıç dizisinin sıralanmış, ters çevrilmiş ya da tamamen rastgele olmasına bakılmaksızın Birleştirme Sıralaması O(n log n) zamanında yürütülür. Ancak birleştirme aşamasında alt listeleri tutmak için O(n) ekstra alana ihtiyaç vardır.
Kod ve Yürütme Çıkışı
Python'da Merge Sort algoritmasının standart yinelemeli uygulaması.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = merge_sort(arr[:mid])
right_half = merge_sort(arr[mid:])
return merge(left_half, right_half)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# Test dataset
data = [38, 27, 43, 3, 9, 82, 10]
print("Original List:", data)
sorted_data = merge_sort(data)
print("Sorted List: ", sorted_data)Original List: [38, 27, 43, 3, 9, 82, 10]
Sorted List: [3, 9, 10, 27, 38, 43, 82]Adım Adım Uygulama
- Düğüm yapısının kopyalamaya gerek kalmadan kolay birleştirmeyi kolaylaştırdığı bağlantılı listeleri sıralama
- Tamamen sistem RAM'ına sığmayan dosyalar için harici sıralama rutinleri
- Eşleşen anahtarların orijinal sırasını koruması gereken kararlı sıralama uygulamaları
Sıkça Sorulan Sorular
Birleştirme Sıralaması istikrarlı bir sıralama algoritması mıdır?
Evet, Birleştirme Sıralaması kararlıdır. Aynı elemanları karşılaştırırken, soldaki (orijinal ilk) alt dizideki eleman, orijinal göreceli konumları korunarak ilk olarak yerleştirilir.
Python neden saf Birleştirme Sıralaması yerine Timsort'u kullanıyor?
Python'un yerleşik `sorted()` özelliği, Birleştirme Sıralaması ve Ekleme Sıralamasını birleştiren hibrit bir algoritma olan Timsort'u kullanır. Halihazırda sıralanmış alt segmentleri tanımlayarak gerçek dünyadaki veri modellerini optimize eder ve bunu saf Merge Sort'tan daha hızlı hale getirir.
İlgili Konular
Python'daki hızlı sıralama algoritmasını keşfedin. Bu etkileşimli kodlama örneğinde pivot seçimini, bölümlendirmeyi ve yinelemeyi öğrenin.
Python Sıralama AlgoritmalarıPython sıralama algoritmalarını keşfedin. Kabarcık sıralamasını görselleştirin ve bir tarayıcı IDE bağlamında yerel olarak birleştirme sıralamasını yapın.
Python İkili Arama AlgoritmasıSıralanmış listeleri logaritmik O(log n) süresine göre arayın. Adım adım mantık, uç durumlar ve optimizasyonlar da dahil olmak üzere Python'da ikili aramayı çalıştırın ve anlayın.