Tutorial Algoritma Pengurutan Penggabungan Python

Pelajari cara mengimplementasikan Pengurutan Gabung dengan Python. Contoh interaktif langkah demi langkah dari strategi pengurutan Divide and Conquer.

Coba di Editor

Ikhtisar

Merge Sort adalah algoritma pengurutan yang sangat efisien yang menggunakan strategi bagi-dan-taklukkan. Ini memecah daftar yang tidak diurutkan menjadi sub-daftar yang lebih kecil, mengurutkan sub-daftar tersebut, dan kemudian menggabungkannya kembali.

Algoritme ini secara rekursif membagi array menjadi dua hingga mencapai subarray elemen tunggal. Kemudian, ia menggabungkan sub-array yang diurutkan dengan membandingkan elemen dari masing-masing sisi dan menempatkannya dalam urutan yang diurutkan. Hal ini memastikan kompleksitas waktu yang optimal.

Terlepas dari apakah array awal diurutkan, dibalik, atau benar-benar acak, Pengurutan Penggabungan dijalankan dalam waktu O(n log n). Namun, diperlukan O(n) ruang ekstra untuk menampung sub-daftar selama fase penggabungan.

Kode & Output Eksekusi

Implementasi rekursif standar dari algoritma Merge Sort dengan Python.

merge_sort.py

Coba di Editor

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)

Keluaran Terminal

Original List: [38, 27, 43, 3, 9, 82, 10]
Sorted List:   [3, 9, 10, 27, 38, 43, 82]

Implementasi Langkah demi Langkah

Menyortir daftar tertaut di mana struktur simpul memfasilitasi penggabungan yang mudah tanpa penyalinan
Rutinitas penyortiran eksternal untuk file yang tidak seluruhnya muat di RAM sistem
Aplikasi penyortiran yang stabil di mana kunci yang cocok harus mempertahankan urutan aslinya

Pertanyaan yang Sering Diajukan

Apakah Merge Sort merupakan algoritma pengurutan yang stabil?

Ya, Merge Sort stabil. Saat membandingkan elemen yang identik, elemen dari subarray kiri (asli pertama) ditempatkan terlebih dahulu, mempertahankan posisi relatif aslinya.

Mengapa Python menggunakan Timsort daripada Merge Sort murni?

`sorted()` bawaan Python menggunakan Timsort, yang merupakan algoritma hybrid yang menggabungkan Merge Sort dan Insertion Sort. Ini mengoptimalkan pola data dunia nyata dengan mengidentifikasi sub-segmen yang sudah diurutkan, menjadikannya lebih cepat daripada Merge Sort murni.

Topik Terkait

Panduan Algoritma Python Quicksort

Jelajahi algoritma quicksort dengan Python. Pelajari pemilihan pivot, partisi, dan rekursi dalam contoh pengkodean interaktif ini.

Algoritma Penyortiran Python

Jelajahi algoritma pengurutan python. Visualisasikan pengurutan gelembung dan pengurutan gabungan secara asli dalam konteks IDE browser.

Algoritma Pencarian Biner Python

Cari daftar yang diurutkan dalam waktu logaritmik O(log n). Jalankan dan pahami pencarian biner dengan Python, termasuk logika langkah demi langkah, kasus edge, dan pengoptimalan.