Algoritma Merge Sort

Posted by Admin on 23 Mei 2019, 14:10 algoritma sorting, merge sort, algoritma merge sort, merge sort php

Merge sort merupakan algoritma pengurutan dalam ilmu komputer yang dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar. Algoritma ini ditemukan oleh John von Neumann pada tahun 1945.

Algoritma pengurutan data merge sort dilakukan dengan menggunakan cara divide and conquer yaitu dengan memecah kemudian menyelesaikan setiap bagian kemudian menggabungkannya kembali. Pertama data dipecah menjadi 2 bagian dimana bagian pertama merupakan setengah (jika data genap) atau setengah minus satu (jika data ganjil) dari seluruh data, kemudian dilakukan pemecahan kembali untuk masing-masing blok sampai hanya terdiri dari satu data tiap blok.

Setelah itu digabungkan kembali dengan membandingkan pada blok yang sama apakah data pertama lebih besar daripada data ke-tengah+1, jika ya maka data ke-tengah+1 dipindah sebagai data pertama, kemudian data ke-pertama sampai ke-tengah digeser menjadi data ke-dua sampai ke-tengah+1, demikian seterusnya sampai menjadi satu blok utuh seperti awalnya. Sehingga metode merge sort merupakan metode yang membutuhkan fungsi rekursi untuk penyelesaiannya.

Algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort.

  1. Divide, Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
  2. Conquer, Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif
  3. Kombinasi, Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan

Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.

Simulasi

Algoritma Merge Sort

 

Contoh Perhitungan

Angka Sebelum Diurutkan : 6 3 5 1 8 2 4 7

Algoritma Merge Sort

  1. Pertama kali larik tersebut dibagi menjadi dua bagian, {6, 3, 5, 1} dan {8, 2, 4, 7}
  2. Kedua larik kemudian diurutkan secara terpisah sehingga menjadi {6, 3}, {5, 1}, {8, 2}, dan  {4, 7}
  3. Ketiga larik kemudian diurutkan secara terpisah sehingga menjadi {6}, {3}, {5}, {1}, {8}, {2}, {4}, dan {7}
  4. Sebuah larik baru dibentuk yang sebagai penggabungan dari setiap dua larik dan diurutkan, sehingga masing-masing larik memilik nilai {3, 6}, {1, 5}, {2, 8}, dan {4, 7}
  5. Bentuk larik baru lagi yang merupakan penggabungan dari setiap dua larik dan diurutkan, sehingga masing-masing lari memilik nilai {1, 3, 5, 6} dan {2, 4, 7, 8}
  6. Langkah berikutnya adalah penggabungan dari masing-masing larik ke dalam larik baru yang dibuat sebelumnya, sehingga memiliki nilai {1, 2, 4, 5, 6, 7, 8}

Source Code PHP Algoritma Merge Sort

function merge_sort($my_array){
	if(count($my_array) == 1 ) return $my_array;
	$mid = count($my_array) / 2;
    $left = array_slice($my_array, 0, $mid);
    $right = array_slice($my_array, $mid);
	$left = merge_sort($left);
	$right = merge_sort($right);
	return merge($left, $right);
}
function merge($left, $right){
	$res = array();
	while (count($left) > 0 && count($right) > 0){
		if($left[0] > $right[0]){
			$res[] = $right[0];
			$right = array_slice($right , 1);
		}else{
			$res[] = $left[0];
			$left = array_slice($left, 1);
		}
	}
	while (count($left) > 0){
		$res[] = $left[0];
		$left = array_slice($left, 1);
	}
	while (count($right) > 0){
		$res[] = $right[0];
		$right = array_slice($right, 1);
	}
	return $res;
}

Cara Pakai

$test_array = array(100, 54, 7, 2, 5, 4, 1);
print_r(merge_sort($test_array));

Demo Program dapat dilihat disini

Referensi

http://ilmuduniainformatika.blogspot.com/2013/03/merge-sorting-algorithm.html

http://www.informatika.unsyiah.ac.id/tfa/ds/mergesort.pdf

https://www.w3resource.com/php-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-17.php