Program Python untuk Merge Sort

Sebagai bahasa pemrograman multi-paradigma dengan pendekatan desain terstruktur, berorientasi objek, serta sintaks dan tata bahasa yang sederhana dan rapi, Python dengan cepat muncul sebagai bahasa pilihan bagi programmer yang mengerjakan proyek dengan berbagai kompleksitas dan skala.

Python menyediakan pustaka modular algoritme pra-bangun yang memungkinkan penggunanya untuk melakukan berbagai operasi yang dapat membantu mereka mencapai tugas mereka sendiri atau berfungsi sebagai langkah untuk mencapai tujuan yang lebih besar dan lebih kompleks. Salah satu algoritma yang lebih populer adalah salah satu yang memungkinkan fungsionalitas Pengurutan Gabung.

Apa itu Pengurutan Gabungan?

Ini adalah teknik penyortiran tujuan umum yang memungkinkan pengguna untuk mengambil kumpulan data acak dari jenis apa pun dan dari sumber apa pun dan membaginya menjadi tahapan berulang hingga akhirnya dipecah menjadi komponen individualnya – teknik rekursif, biasanya disebut sebagai ' metode membagi dan menaklukkan '.

Algoritme kemudian menyatukan komponen-komponen individual – sekali lagi dalam tahap berulang – tetapi mengurutkannya menjadi urutan logis yang telah ditentukan sebelumnya pada setiap tahap di sepanjang jalan, menggunakan perbandingan dasar dan bertukar hingga seluruh seri data disusun kembali dalam urutan logis yang diinginkan. .

Lihat kursus ilmu data kami yang lain di upGrad.

Teknik Divide and Conquer

Ambil, misalnya, kumpulan data acak dari huruf alfabet: N, H, V, B, Q, D, Z, R.

Langkah 1 : Dataset asli pertama-tama dipecah menjadi dua kelompok sebagai berikut:

N, H, V, B Q, D, Z, R

Langkah 2 : Kedua array yang dihasilkan dibagi lagi sebagai berikut:

N, H V, B Q, D Z, R

Langkah 3 : Akhirnya, keempat array selanjutnya dimuntahkan hingga seluruh seri data dipecah menjadi komponen individualnya:

N H V B Q D Z R

Prosesnya kemudian berbalik, dan masing-masing titik data sekarang mulai bergabung secara bertahap. Namun selama proses penggabungan ini, setiap elemen dalam setiap sub-array dinilai dan ditukar sehingga mereka memilah dirinya sendiri dalam urutan logis (urutan abjad), sebagai berikut:

Langkah 4 : Elemen individu bergabung menjadi pasangan sambil bertukar posisi sesuai kebutuhan untuk membentuk urutan yang benar:

H, N B, V D, Q R, Z

Langkah 5 : Proses penggabungan dan pengurutan secara rekursif berlanjut ke iterasi berikutnya:

B, H, N, V ​​D, Q, R, Z

Langkah 6 : Seluruh seri data akhirnya disusun kembali dalam urutan abjad logisnya:

B, D, H, N, Q, R, V, Z

Jelajahi Kursus Ilmu Data Populer kami

Merge Sort Implementasi

Ada dua pendekatan untuk implementasi Merge Sort di Python. Pendekatan top-down dan pendekatan bottom-up.

Pendekatan atas ke bawah:

Pendekatan top-down yang lebih umum digunakan adalah yang dijelaskan di atas. Dibutuhkan lebih lama dan menggunakan lebih banyak memori, dan karenanya tidak efisien saat bekerja dengan kumpulan data yang lebih kecil. Namun, ini jauh lebih andal, terutama bila diterapkan pada kumpulan data besar.

Baca Artikel Ilmu Data populer kami

Kode masukan:

def merge_sort (inp_arr):

ukuran = len(inp_arr)

jika ukuran > 1:

tengah = ukuran // 2

kiri_arr = inp_arr(:tengah)

kanan_arr = inp_arr(tengah:)

gabung_urutkan(kiri_arr)

gabungkan _sort(kanan_arr)

saya = 0

j = 0

k = 0

(Di mana i dan j masing-masing adalah iterator untuk melintasi bagian kiri dan kanan dari seri data, dan k adalah iterator dari keseluruhan seri data).

ukuran_kiri = len(arr_kiri)

kanan _ukuran = len(kanan_arr)

sementara i < ukuran_kiri dan j < ukuran yang benar:

jika left_arr(i) < right_arr (j):

inp_arr(k) – kiri_arr(i)

saya >= 1

kalau tidak:

inp_arr(k) = kanan_arr (j)

j += 1

k += 1

sementara saya <ukuran_kiri:

inp_arr (k) = kiri_arr(i)

saya += 1

k += 1

while j <ukuran_kanan:

inp_arr (k) = kanan_arr(j)

j += 1

k += 1

inp_arr = (N, H, V, B, Q, D, Z, R)

print(:Masukan Larik:\n”)

cetak(inp_arr)

gabung_urutkan (inp_arr)

print(“Array Terurut:\n”)

cetak (inp_arr)

Keluaran:

Array Masukan: N, H, V, B, Q, D, Z, R

Larik Keluaran: B, D, H, N, Q, R, V, Z

Pendekatan dari bawah ke atas:

Pendekatan dari bawah ke atas lebih cepat, menggunakan lebih sedikit memori, dan bekerja secara efisien dengan kumpulan data yang lebih kecil tetapi dapat mengalami masalah saat bekerja dengan kumpulan data yang besar. Oleh karena itu, ini lebih jarang digunakan.

Kode masukan:

def gabungan (kiri, kanan):

hasil = [] x, y = 0, 0

untuk k dalam rentang(0, len(kiri) + len(kanan)):

jika i == len(kiri): # jika pada akhir babak pertama,

result.append(right[j]) # tambahkan semua nilai dari babak ke-2

j += 1

elif j == len(kanan): # jika pada akhir babak ke-2,

result.append(left[x]) # tambahkan semua nilai dari babak pertama

saya += 1

elif kanan[j] < kiri[i]:

hasil.tambahkan(kanan[j])

j += 1

kalau tidak:

result.append(kiri[i])

saya += 1

hasil pengembalian

def mergesort(ar_list):

panjang = len(ar_list)

ukuran = 1

sedangkan ukuran <panjang:

size+=size # menginisialisasi pada 2 seperti yang dijelaskan

untuk pos dalam rentang (0, panjang, ukuran):

mulai = pos

pertengahan = pos + int(ukuran / 2)

akhir = pos + ukuran

kiri = ar_list[ mulai : pertengahan ] kanan = ar_list[ pertengahan : akhir ]

ar_list[mulai:akhir] = gabungkan(kiri, kanan)

kembali ar_list

ar_list = [N, H, V, B, Q, D, Z, R] print(gabungkan(ar_list))

Keluaran:

Array masukan: N, H, V, B, Q, D, Z, R

Larik keluaran: B, D, H, N, Q, R, V, Z

Implementasi Merge Sort diterapkan pada kumpulan data kehidupan nyata yang lebih kompleks

Mari terapkan pendekatan top-down ke empat kendaraan off-road acak di India:

Kode masukan:

Mobil kelas :

def __init__(mandiri, merek, model, harga):

diri.merek = merek

self.model = model

self.harga = harga

def __str__(diri sendiri):

return str.format(“Merek: {}, Model: {}, Harga: {}”, self.brand,

diri.model, diri.harga)

def gabungan(list1, i, j, k, comp_fun):

salinan_kiri = daftar1[i:k + 1]

r_sublist = daftar1[k+1:r+1]

left_copy_index = 0

j_sublist_index = 0

sort_index = i

sementara left_copy_index < len(left_copy) danj_sublist_index <

len(j_sublist):

jika comp_fun(left_copy[left_copy_index], j_sublist[j_sublist_index]):

daftar1[sorted_index] = salinan_kiri[kiri_salinan_indeks]

indeks_salin_kiri = indeks_salin_kiri + 1

lain :

daftar1[sorted_index] = j_sublist[j_sublist_index]

j_sublist_index = j_sublist_index + 1

diurutkan_indeks = diurutkan_indeks + 1

sementara left_copy_index < len(left_copy):

daftar1[sorted_index] = salinan_kiri[kiri_salinan_indeks]

indeks_salin_kiri = indeks_salin_kiri + 1

diurutkan_indeks = diurutkan_indeks + 1

sementara j_sublist_index < len(j_sublist):

daftar1[sorted_index] = j_sublist[j_sublist_index]

j_sublist_index = j_sublist_index + 1

diurutkan_indeks = diurutkan_indeks + 1

def merge_sort(list1, i, j, comp_fun):

jika saya >= j:

kembali

k = (i + j)//2

merge_sort(list1, i, k, comp_fun)

merge_sort(list1, k + 1, j, comp_fun)

gabungkan(daftar1,i,j,k, comp_fun)

mobil1 = Mobil(“Jeep”, “Wrangler”, 0.58)

car2 = Mobil(“Ford”, “Endeavour”, 0.35)

car3 = Mobil(“Jaguar Land Rover”, “Range Rover Sport”, 1.76)

car4 = Mobil(“Mercedes Benz”, “G-class”, 2.42)

daftar1 = [mobil1, mobil2, mobil3, mobil4]

merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.brand < carB.brand)

print (“Mobil disortir berdasarkan merek:”)

untuk mobil dilist1:

cetak (mobil)

cetak ()

merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.price< carB.price)

print (“Mobil diurutkan berdasarkan harga:”)

untuk mobil dilist1:

cetak (mobil)

Keluaran:

Mobil diurutkan berdasarkan merek:

Ford Endeavour

Jaguar Land Rover Range Rover Sport

Jeep Wrangler

Mercedez Benz kelas G

Mobil diurutkan berdasarkan harga:

Ford Endeavour

Jeep Wrangler

Jaguar Land Rover Range Rover

Mercedez Benz kelas G

Anda dapat mempelajari aspek teoretis dan praktis Python dengan Sertifikat Profesional upGrad dalam Ilmu Data dan Analisis Bisnis dari University of Maryland. Kursus ini membantu Anda mempelajari Python dari awal. Bahkan jika Anda baru dalam pemrograman dan pengkodean, upGrad akan menawarkan Anda kursus persiapan dua minggu sehingga Anda dapat mempelajari dasar-dasar pemrograman. Anda akan belajar tentang berbagai alat seperti Python, SQL, sambil mengerjakan beberapa proyek industri.

Rencanakan Karir Pengembangan Perangkat Lunak Anda Sekarang!

Terapkan Untuk Program Sertifikat Profesional dalam Ilmu Data dan Analisis Bisnis