KATA PENGANTAR

Puji syukur kami penjatkan kehadirat Allah SWT, yang atas rahmat-Nya sehingga kami dapat menyelesaikan penyusunan makalah yang berjudul “Merge Sort”. Penulisan makalah ini merupakan salah satu tugas yang diberikan dalam mata kuliah Struktur Data dan Algoritma di Universitas Sains Alqur’an

Dalam Penulisan makalah ini kami merasa masih banyak kekurangan baik pada teknis penulisan maupun materi, mengingat akan kemampuan yang kami miliki. Untuk itu, kritik dan saran dari semua pihak sangat kami harapkan demi penyempurnaan pembuatan makalah ini.

Dalam penulisan makalah ini penulis menyampaikan ucapan terima kasih yang sebesar-besarnya kepada pihak-pihak yang membantu dalam menyelesaikan makalah ini, khususnya kepada Dosen kami yang telah memberikan tugas dan petunjuk kepada kami, sehingga kami dapat menyelesaikan tugas ini.

Wonosobo, 19 Mei 2015

Penyusun

BAB I

PENDAHULUAN

1.1. Latar Belakang

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.

1. 2. Rumusan Masalah

Bagaimana penjelasan tentang algoritma Merge Sort dan penerapannya?

1. 3. Tujuan Penulisan

Memahami algoritma Merge Sort dan penerapannya

BAB II

PEMBAHASAN

2. 1. Algoritma

Ditinjau dari asal-usul katanya, kata Algoritma sendiri mempunyai sejarah yang aneh. Orang hanya menemukan kata algorism yang berarti proses menghitung dengan angka arab. Anda dikatakan algorist jika Anda menghitung menggunakan angka arab. Para ahli bahasa berusaha menemukan asal kata ini namun hasilnya kurang memuaskan. Akhirnya para ahli sejarah matematika menemukan asal kata tersebut yang berasal dari nama penulis buku arab yang terkenal yaitu Abu Ja’far Muhammad Ibnu Musa Al-Khuwarizmi. Al-Khuwarizmi dibaca orang barat menjadi Algorism. Al-Khuwarizmi menulis buku yang berjudul Kitab Al Jabar Wal-Muqabala yang artinya “Buku pemugaran dan pengurangan” (The book of restoration and reduction). Dari judul buku itu kita juga memperoleh akar kata “Aljabar” (Algebra). Perubahan kata dari algorism menjadi algorithm muncul karena kata algorism sering dikelirukan dengan arithmetic, sehingga akhiran –sm berubah menjadi –thm. Karena perhitungan dengan angka Arab sudah menjadi hal yang biasa, maka lambat laun kata algorithm berangsur-angsur dipakai sebagai metode perhitungan (komputasi) secara umum, sehingga kehilangan makna kata aslinya. Dalam bahasa Indonesia, kata algorithm diserap menjadi algoritma.

“Algoritma adalah urutan langkah-langkah logis penyelesaian masalah yang disusun secara sistematis dan logis”. Kata logis merupakan kata kunci dalam algoritma. Langkah-langkah dalam algoritma harus logis dan harus dapat ditentukan bernilai salah atau benar. Dalam beberapa konteks, algoritma adalah spesifikasi urutan langkah untuk melakukan pekerjaan tertentu. Pertimbangan dalam pemilihan algoritma adalah, pertama, algoritma haruslah benar. Artinya algoritma akan memberikan keluaran yang dikehendaki dari sejumlah masukan yang diberikan. Tidak peduli sebagus apapun algoritma, kalau memberikan keluaran yang salah, pastilah algoritma tersebut bukanlah algoritma yang baik.

Pertimbangan kedua yang harus diperhatikan adalah kita harus mengetahui seberapa baik hasil yang dicapai oleh algoritma tersebut. Hal ini penting terutama pada algoritma untuk menyelesaikan masalah yang memerlukan aproksimasi hasil (hasil yang hanya berupa pendekatan). Algoritma yang baik harus mampu memberikan hasil yang sedekat mungkin dengan nilai yang sebenarnya.

Ketiga adalah efisiensi algoritma. Efisiensi algoritma dapat ditinjau dari 2 hal yaitu efisiensi waktu dan memori. Meskipun algoritma memberikan keluaran yang benar (paling mendekati), tetapi jika kita harus menunggu berjam-jam untuk mendapatkan keluarannya, algoritma tersebut biasanya tidak akan dipakai, setiap orang menginginkan keluaran yang cepat. Begitu juga dengan memori, semakin besar memori yang terpakai maka semakin buruklah algoritma tersebut. Dalam kenyataannya, setiap orang bisa membuat algoritma yang berbeda untuk menyelesaikan suatu permasalahan, walaupun terjadi perbedaan dalam menyusun algoritma, tentunya kita mengharapkan keluaran yang sama. Jika terjadi demikian, carilah algoritma yang paling efisien dan cepat.

2. 1. 1. Algoritma Sorting

Dalam Ilmu Komputer, Algoritma Sorting merupakan algoritma yang menempatkan elemen list pada urutan tertentu. Urutan yang paling sering digunakan ialah urutan numerikal dan urutan lexicographical. Sorting yang efisien sangat dibutuhkan untuk mengoptimisasi penggunaan dari algoritma lain seperti pencarian dan penggabungan yang membutuhkan list terurut untuk berjalan dengan sempurna, yang juga sering digunakan untuk Canonicalisisasi data dan menghasilkan output yang dapat dibaca manusia. Untuk lebih lanjutnya, output harus melengkapi dua syarat ini:

Output merupakan urutan yang tidak menurut (nondecreasing), setiap elemen tidak lebih kecil dari elemen sebelumnya menurut dari urutan keseluruhan yang diinginkan.
Output merupakan permutasi (pengurutan kembali) dari inputan yang diberikan.

2.1 . Merge Sort

Merge sort juga menggunakan prinsip divide and conquer. Merge sort membagi array menjadi dua secara terus menerus hingga hanya tersisa satu elemen pada sub-array yang terbentuk. Kemudian elemen-elemen tersebut di urutkan lalu di gabung secara terus menerus hingga terbentuk array dengan ukuran yang sama dengan array asal.

Algoritma pengurutan data merge sort dilakukan dengan menggunakan cara divide and conquer. Sebuah algoritma divide and conquer (selanjutnya disebut dengan D&C) memiliki tiga langkah, yaitu:

Divide (Membagi): pada langkah ini kita memecahkan masalah atau data ke dalam bentuk yang sama, tetapi dalam ukuran yang lebih kecil. Pemecahan langkah biasanya dilakukan dengan menggunakan algoritma rekursif, sampai ukuran data menjadi sangat kecil dan dapat diselesaikan dengan algoritma sederhana.
Conquer (Menaklukkan): dalam langkah ini kita mencoba menyelesaikan masalah atau data yang telah dipecahkan pada langkah pertama, dengan menggunakan algoritma sederhana.
Combine (Menggabungkan): setelah menjalankan langkah conquer, tentunya kita harus menggabungkan kembali hasil dari masing-masing pecahan yang ada, untuk mendapatkan hasil akhir kalkulasi. Langkah combine mencoba mencapai hal tersebut.

2.2.2. Algoritma Merge Sort

Secara konseptual, untuk sebuah array berukuran n, Merge Sort bekerja sebagai berikut:

Jika bernilai 0 atau 1, maka array sudah terurut. Sebaliknya:
Bagi array yang tidak terurut menjadi dua subarray, dimana bagian pertama merupakan setengah (jika data genap) atau setengah minus satu (jika data ganjil) dari seluruh data.
Urutkan setiap sub-array. Jika sub-array tidak cukup kecil, lakukan rekursif langkah 2 terhadap sub-array.

4. Menggabungkan dua sub-array kembali menjadi satu array yang terurut

Pseudocode Merge Sort

input : Array

output : Array yang terurut

algoritma :

1. if length(m) _ 1 then

2. return m

3. else

4. tengah = length(m) div 2

5. for x = m to tengah do

6. add x to kiri

7. end for

8. for x = m after tengah do

9. add x to kanan

10. end for

11. while length(kiri) > 0 and length(kanan) > 0 do

12. if first(kiri) _ first(kanan) then

13. Append first(kiri) to hasil

14. kiri = rest(kiri)

15. else

16. append first(kanan) to hasil

17. kanan = rest(kanan)

18. end if

19. end while

20. if length(kiri) > 0 then

21. append rest(kiri) to hasil

22. end if

23. if length(kanan) > 0 then

24. append rest(kanan) to hasil

25. end if

26. return hasi

2.2.3. Kompleksitas Merge Sort

Merge sort memiliki kasus terburuk dan kasus rata-rata. Kasus terburuk adalah saat tiap 2 lemen dibandingkan selalu dilakukan pertukaran. Bila waktu yang diperlukan untuk melakukan merge sort adalah T(n) maka untuk saat rekursif waktu yang dihabiskan adalah T(n) = 2T(n/2) + n. T (n/2) adalah waktu yang diperlukan untuk merge setengah dari ukuran list, dan ditambah n sebagai langkah dari penggabungan list. Kompleksitas waktu terburuk dan rata-rata dari merge sort adalah O(n log n). Merge Sort akan selalu membagi dua tiap sub-arraynya, sehingga kompleksitas dari algoritma Merge Sort berlaku untuk semua kasus (Worst Case = Best Case = Average Case).

2.2.4. Implementasi Program Merge Sort

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace programmergesort

{

class Program

{

static void Main(string[] args)

{

int[] data;

int[] temp;

Console.WriteLine("PROGRAM MERGE SORT");

Console.WriteLine(" Oleh Kelompok 2 ");

Console.WriteLine("-------------------");

Console.Write("masukan jumlah bilangan : ");

int jumlah_bilangan = int.Parse(Console.ReadLine());

data = new int[jumlah_bilangan];

temp = new int[jumlah_bilangan];

for (int i = 0; i < jumlah_bilangan; i++)

{

Console.Write("masukan bilangan ke-{0} = ", i + 1);

data[i] = int.Parse(Console.ReadLine());

}

//lakukan pemecahan

devide(data, temp, 0, jumlah_bilangan - 1);

Console.WriteLine("\nBilangan terurut : \n");

for (int i = 0; i < jumlah_bilangan; i++)

{

Console.Write("{0} ", data[i]);

}

Console.ReadLine();

}

public static void devide(int[] data, int[] temp, int awal, int akhir)

{

if (awal < akhir)

{

int mid = (akhir + awal) / 2;

devide(data, temp, awal, mid);

devide(data, temp, mid + 1, akhir);

combine(data, temp, awal, mid, akhir);

}

public static void combine(int[] data, int[] temp, int awal, int mid, int akhir)

{

int kiri1 = awal;

int kanan1 = mid;

int kiri2 = mid + 1;

int kanan2 = akhir;

int i = awal;

while (kiri1 <= kanan1 && kiri2 <= kanan2)

{

if (data[kiri1] <= data[kiri2])

{

temp[i] = data[kiri1];

kiri1++;

}

else

{

temp[i] = data[kiri2];

kiri2++;

}

i++;

}

while (kiri1 <= kanan1)

{

temp[i] = data[kiri1];

kiri1++;

i++;

}

while (kiri2 <= kanan2)

{

temp[i] = data[kiri2];

i++;

kiri2++;

}

int j = awal;

while (j <= akhir)

{

data[j] = temp[j];

j++;

}

BAB 3

KESIMPULAN

Merge sort adalah sort yang dilakukan dengan teknik merge (menggabungkan) dua buah array kedalam sebuah array yang baru. Algoritma merge sort membagi tabel menjadi dua tabel yang sama besar. Masing-masing tabel diurutkan secara rekursif, dan kemudian digabungkan kembali untuk membentuk tabel yang terurut. Implementasi dasar dari algoritma merge sort memakai tiga buah tabel, dua untuk menyimpan elemen dari tabel yang telah di bagi dua dan satu untuk menyimpan elemen yang telah terurut. Namun algoritma ini dapat juga dilakukan langsung pada dua tabel, sehingga menghemat ruang atau memori yang dibutuhkan.