Mergesort dan Quicksort

Sebelum mendalami algoritma Mergesort dan Quicksort, perlu diketahui garis besar dari konsep divide and conquer karena Mergesort dan Quicksort mengadaptasi pola tersebut.

POLA DIVIDE AND CONQUER

Beberapa algoritma mengimplementasikan konsep rekursi untuk menyelesaikan permasalahan.   Permasalahan   utama   kemudian   dipecah   menjadi   sub-masalah, kemudian solusi dari sub-masalah akan membimbing menuju solusi permasalahan utama.

Pada setiap tingkatan rekursi, pola tersebut terdiri atas 3 langkah.

1. Divide

Memilah masalah menjadi sub masalah

2. Conquer

Selesaikan sub masalah tersebut secara rekursif. Jika sub-masalah tersebut cukup ringkas dan sederhana, pendekatan penyelesaian secara langsung akan lebih efektif

3.  Kombinasi

Mengkombinasikan solusi dari sub-masalah, yang akan membimbing menuju penyelesaian atas permasalahan utama

MERGE SORT

Seperti yang telah dijelaskan sebelumnya, 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. Merge Sort termasuk pada pendekatan mudah membagi, susah menggabung (easy split/ hard join).

QUICK SORT

Algoritma ini juga berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini hanya mengikuti langkah – langkah sebagai berikut :

1. Divide

Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot.  Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.

2. Conquer

Mengurutkan elemen pada sub-rangkaian secara rekursif

Pada algoritma quicksort, langkah ”kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array. Quick Sort termasuk pada pendekatan sulit membagi, mudah menggabung (hard split/easy join)

Cara pemilihan pivot:

1)      Pivot = elemen pertama/elemen terakhir/elemen tengah tabel

2)      Pivot dipilih secara acak  dari salah satu elemen tabel.

3)      Pivot = elemen median tabel

Dari berbagai sumber

Iklan