Minggu, 26 Desember 2010

Metode Merge Sort


Merge sort menggunakan pola divide and conquer. Dengan hal ini deskripsi dari 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.
Contoh:
Inputan datanya adalah sebagai berikut:
7
2
6
5


Membagi rangkaian menjadi dua bagian:
7
2

6
5
Kedua bagian tersebut bisa dinamai LeftArr dan RightArr

Membagi LeftArr menjadi dua bagian:
7

2

Membandingkannya kemudian dikombinasikan:
2
7
7 dan 2 kemudian tukar posisi karena 2 < 7

Membagi RightArr menjadi dua bagian:
6

5

Membandingkannya kemudian dikombinasikan:
5
6
6 dan 5 kemudian tukar posisi karena  5 < 6

Membandingkan LeftArr dan RightArr.
2
7
5
6
Kemudian dilakukan proses membandingkan lagi antara angka di LeftArr dengan RightArr.

Pembandingan biasanya dimulai dari angka terdepan di masing-masing bagian.

Mengkombinasikan LeftArr dengan RightArr.
2
5
6
7
Sehingga menjadi: 2<5<6<7

Ini dia listing Program Merge Sort pada Pascal : MergeSort

0 comments:

Posting Komentar

Twitter Delicious Facebook Digg Stumbleupon Favorites More

 
Design by Free WordPress Themes | Bloggerized by Lasantha - Premium Blogger Themes | Best WordPress Web Hosting