Archive for September 2016
Cara Membuat Algoritma Merge Sorting (Urut Gabung) dengan PHP
Urut gabung atau
sering juga disebut dalam istilah Inggrisnya 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.
Prinsip utama yang diimplementasikan pada algoritma urut gabung
seringkali disebut sebagai pecah-belah dan taklukkan (bahasa
Inggris:divide and conquer). Cara kerja algoritma urut gabung adalah membagi larik data
yang diberikan menjadi dua bagian yang lebih kecil. Kedua larik yang
baru tersebut kemudian akan diurutkan secara terpisah. Setelah kedua
buah list tersusun, maka akan dibentuk larik baru sebagai hasil penggabungan
dari dua buah larik sebelumnya. Menurut keefektifannya, algoritma ini
bekerja dengan tingkat keefektifan O(nlog(n)).
Berikut ini adalah gambaran dari sistem kerja dari
algoritma Merge Sort :
Seperti pada prinsip nya array di bagi hingga bagian
terkecil, kemudian di urutkan kembali menjadi sebuah urutan dan yang sudah
tersusun.
Algoritma Merge sorting pada PHP adalah sebagai berikut :
function mergesort($arr){
if(count($arr)
== 1 ) return $arr;
$tengah
= count($arr) / 2;
$kiri = array_slice($arr, 0, $tengah);
$kanan = array_slice($arr, $tengah);
$kiri
= mergesort($kiri);
$kanan
= mergesort($kanan);
return
merge($kiri, $kanan);
}
function merge($kiri, $kanan){
$asc = array();
while (count($kiri) > 0 && count($kanan) > 0){
if($kiri[0] > $kanan[0]){
$asc[] = $kanan[0];
$kanan = array_slice($kanan , 1);
}else{
$asc[] = $kiri[0];
$kiri = array_slice($kiri, 1);
}
}
while (count($kiri) > 0){
$asc[] = $kiri[0];
$kiri = array_slice($kiri, 1);
}
while (count($kanan) > 0){
$asc[] = $kanan[0];
$kanan = array_slice($kanan, 1);
}
return $asc;
}
Untuk penjelasan lebih lanjut ada di dalam file PHP. Sekian Posting kali ini, semoga bermanfaat dan menambah ilmu bagi yang membacanya.
Link download untuk
Merge Sorting dengan PHP :
Sumber : https://rosettacode.org/