Struktur Data - Merge Sort Algorithm

Merge sort adalah teknik pengurutan berdasarkan teknik divide and conquer. Dengan kompleksitas waktu kasus terburuk menjadi Ο (n log n), ini adalah salah satu algoritma yang paling dihormati.

Merge sort terlebih dahulu membagi array menjadi dua bagian yang sama, lalu menggabungkannya dalam cara yang diurutkan.

Bagaimana Cara Kerja Merge Sort?

Untuk memahami merge sort, kita mengambil array yang tidak disortir sebagai berikut -

Kita tahu bahwa merge sort pertama-tama membagi seluruh array secara iteratif menjadi dua bagian yang sama kecuali jika nilai atomnya tercapai. Kita melihat di sini bahwa array 8 item dibagi menjadi dua array dengan ukuran 4.

Ini tidak mengubah urutan kemunculan item di aslinya. Sekarang kami membagi dua larik ini menjadi dua.

Kami selanjutnya membagi array ini dan kami mencapai nilai atom yang tidak dapat lagi dibagi.

Sekarang, kami menggabungkannya dengan cara yang persis sama seperti saat dipecah. Harap perhatikan kode warna yang diberikan untuk daftar ini.

Kami pertama-tama membandingkan elemen untuk setiap daftar dan kemudian menggabungkannya ke dalam daftar lain dengan cara yang diurutkan. Kami melihat bahwa 14 dan 33 berada di posisi yang diurutkan. Kami membandingkan 27 dan 10 dan dalam daftar target dari 2 nilai kami menempatkan 10 terlebih dahulu, diikuti oleh 27. Kami mengubah urutan 19 dan 35 sedangkan 42 dan 44 ditempatkan secara berurutan.

Pada iterasi berikutnya dari fase penggabungan, kami membandingkan daftar dua nilai data, dan menggabungkannya ke dalam daftar nilai data yang ditemukan dengan menempatkan semua dalam urutan yang diurutkan.

Setelah penggabungan terakhir, daftarnya akan terlihat seperti ini -

Sekarang kita harus mempelajari beberapa aspek pemrograman dari merge sorting.

Algoritma

Merge sort terus membagi daftar menjadi dua bagian yang sama hingga tidak dapat lagi dibagi. Menurut definisi, jika hanya satu elemen dalam daftar, itu diurutkan. Lalu, gabungkan sortir menggabungkan daftar yang diurutkan yang lebih kecil yang membuat daftar baru juga diurutkan.

Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.

Pseudocode

Sekarang kita akan melihat pseudocodes untuk fungsi merge sort. Karena algoritme kami menunjukkan dua fungsi utama - bagi & gabungkan.

Merge sort berfungsi dengan rekursi dan kita akan melihat implementasi kita dengan cara yang sama.

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
   
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
   
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
   
   return c
	
end procedure

Untuk mengetahui tentang implementasi merge sort dalam bahasa pemrograman C, silakan klik di sini .