Blog ini didasarkan pada pendekatan divide and conquer. Merge Sort adalah algoritme “bagi dan taklukkan” di mana masalah dibagi menjadi beberapa subproblem dan kemudian digabungkan untuk mendapatkan solusi. Blog ini di Merge Sort in akan memandu Anda melalui topik di bawah ini secara mendetail -
- Apa itu Merge Sort in Python?
- Pendekatan Divide and Conquer
- Menerapkan Merge Sort dengan Python
- Flowchart untuk implementasi Merge Sort
- Keuntungan dan Penggunaan
Apa itu Merge Sort in Python?
Merge Sort didasarkan pada algoritma divide and conquer dimana input array dibagi menjadi dua bagian, kemudian diurutkan secara terpisah dan digabungkan kembali untuk mencapai solusi. Fungsi merge () digunakan untuk menggabungkan yang diurutkan .
Pendekatan Divide and Conquer
- Array dibagi menjadi dua dan proses diulangi dengan setiap setengahnya sampai setiap setengah berukuran 1 atau 0.
- Larik ukuran 1 diurutkan dengan mudah.
- Sekarang dua array yang diurutkan digabungkan menjadi satu array besar. Dan ini dilanjutkan sampai semua elemen digabungkan dan array diurutkan.
Berikut adalah visualisasi dari merge sort untuk membersihkan gambar untuk Anda
Masukan Array = [3,1,4,1,5,9,2,6,5,4]
Sekarang, mari kita lanjutkan ke implementasinya.
diploma pasca sarjana vs master
Menerapkan Merge Sort dengan Python
def mergeSort (nlist): print ('Splitting', nlist) if len (nlist)> 1: mid = len (nlist) // 2 lefthalf = nlist [: mid] righthalf = nlist [mid:] mergeSort (lefthalf) mergeSort (kanan) i = j = k = 0 sedangkan i Keluaran:
$ python main.py
('Memisahkan', [3, 1, 4, 1, 5, 9, 2, 6, 5, 4])
('Memisahkan', [3, 1, 4, 1, 5])
('Memisahkan', [3, 1])
('Memisahkan', [3])
('Penggabungan', [3])
('Memisahkan', [1])
('Penggabungan', [1])
('Penggabungan', [1, 3])
('Memisahkan', [4, 1, 5])
('Memisahkan', [4])
('Penggabungan', [4])
('Memisahkan', [1, 5])
('Memisahkan', [1])
('Penggabungan', [1])
('Memisahkan', [5])
('Penggabungan', [5])
('Penggabungan', [1, 5])
('Penggabungan', [1, 4, 5])
('Penggabungan', [1, 1, 3, 4, 5])
('Memisahkan', [9, 2, 6, 5, 4])
('Memisahkan', [9, 2])
('Memisahkan', [9])
('Penggabungan', [9])
('Memisahkan', [2])
('Penggabungan', [2])
('Penggabungan', [2, 9])
('Memisahkan', [6, 5, 4])
('Memisahkan', [6])
('Penggabungan', [6])
('Memisahkan', [5, 4])
('Memisahkan', [5])
('Penggabungan', [5])
('Memisahkan', [4])
('Penggabungan', [4])
('Penggabungan', [4, 5])
('Penggabungan', [4, 5, 6])
('Penggabungan', [2, 4, 5, 6, 9])
('Penggabungan', [1, 1, 2, 3, 4, 4, 5, 5, 6, 9])
[1, 1, 2, 3, 4, 4, 5, 5, 6, 9]
java convert double to int
Diagram Alir untuk implementasi Merge Sort
Keuntungan dan Penggunaan Merge Sort
Sebagian besar algoritme lain berkinerja buruk dengan struktur data berurutan seperti file dan daftar tertaut. Dalam struktur ini mengakses elemen acak membutuhkan waktu linier, bukan waktu konstan reguler. Dan sifat dari jenis gabungan membuatnya mudah dan cepat untuk struktur data seperti itu.Salah satu fitur terbaik dari jenis gabungan adalah jumlah perbandingannya yang rendah. Itu membuat O (n * log (n)) jumlah pembanding, tetapi faktor konstantanya bagus jika dibandingkan dengan quicksort, yang membuatnya berguna jika fungsi pembanding adalah operasi yang lambat.Selain itu, pendekatan divide-and-conquer dari jenis gabungan membuatnya nyaman untuk pemrosesan paralel.
Dengan ini, kita sampai pada akhir blog ini tentang “Bagaimana menerapkan Merge Sort in Python”. Saya harap konten tersebut menambah nilai pengetahuan Anda dengan Python. Untuk mendapatkan pengetahuan mendalam tentang Python beserta berbagai aplikasinya, Anda dapat mendaftar secara langsung dengan dukungan 24/7 dan akses seumur hidup.