My first Magazine pemrograman-kompetitif-dasar | Page 53

5.2 Studi Kasus 1: Merge Sort
5.2
Studi Kasus 1: Merge Sort
Merge sort adalah algoritma pengurutan yang memiliki kompleksitas O(N log N). Algoritma
merge sort terus membagi array yang ingin diurutkan menjadi dua sampai tersisa satu elemen,
kemudian menggabungkannya kembali sambil mengurutkannya. Inti pengurutan merge sort ada
pada tahap combine.
Cara kerja algoritma ini adalah:
1. Divide : jika array yang akan diurutkan lebih dari 1 elemen, bagi array tersebut menjadi dua
array sama besar (atau mendekati sama besar jika panjang array tersebut ganjil). Kemudian
lakukan merge sort pada masing-masing subarray tersebut.
2. Conquer : ketika array berisi hanya 1 elemen, tidak perlu lakukan apapun. Array yang
berisi 1 elemen sudah pasti terurut.
3. Combine : saat kita memiliki dua array yang telah terurut, kita bisa menggabungkan (merge )
keduanya menjadi sebuah array yang terurut.
Mengapa array yang berukuran 1 bisa kita katakan sudah terurut? Jika ada sebuah array
berukuran 1 (contohnya [42]), maka elemen tersebut tidak memiliki elemen lain yang bisa
dibandingkan dengan elemen tersebut. Jadi, array tersebut sudah terurut.
5.2.1
Contoh Eksekusi Merge Sort
Diberikan sebuah array [5, 2, 7, 6, 1, 8, 9, 3]. Kita ingin mengurutkan array tersebut menggu-
nakan merge sort . Gambar 5.2 hingga Gambar 5.8 mengilustrasikan proses yang terjadi dari
awal hingga array tersebut terurut.
Kita memulai proses pengurutan dari tahap divide. Kita akan membagi array menjadi bebera-
pa subarray hingga masing-masing memiliki 1 elemen.
5 2 7 6 1 8 9 3
5 2 7 6
1 8 9 3
Gambar 5.2: Langkah 1: Karena ukuran array lebih dari 1 elemen, kita bagi array yang kita miliki
menjadi dua bagian.
5 2 7 6
5 2
7 6
1 8 9 3
1 8
9 3
Gambar 5.3: Langkah 2: Array yang kita miliki masih lebih dari 1 elemen, bagi lagi masing-masing
menjadi dua.
43