ANALISIS PERBANDINGAN ALGORITMA SELECTION SORT DENGAN MERGE SORT

ANALISIS PERBANDINGAN ALGORITMA SELECTION SORT DENGAN MERGE SORT Disusun untuk memenuhi tugas UTS mata kuliah : Analisis Algoritma

Oleh : Eka Risky Firmansyah 1110091000043

Program Studi Teknik Informatika Fakultas Sains dan Teknologi Universitas Islam Negeri Syarif Hidayatullah Jakarta 2012

DAFTAR ISI

DAFTAR ISI ....................................................................................................................... 1 KATA PENGANTAR ......................................................................................................... 2 BAB I PENDAHULUAN .................................................................................................... 3 1. LATAR BELAKANG ...................................................................................................... 3 2. METODE PENULISAN ................................................................................................... 3 3. TUJUAN PENULISAN .................................................................................................... 3 4. MANFAAT PENULISAN ................................................................................................. 3 BAB II LANDASAN TEORI .............................................................................................. 4 1. ALGORITMA PENGURUTAN .......................................................................................... 4 2. KOMPLEKSITAS ALGORITMA ....................................................................................... 5 3. GROWTH FUNCTION .................................................................................................... 5 4. NOTASI ASIMPTOTIK ................................................................................................... 6 BAB III PEMBAHASAN .................................................................................................... 7 1. SELECTION SORT .......................................................................................................... 7 Penjelasan Singkat Selection Sort .............................................................................. 7 Pseudocode Minimum Selection Sort ......................................................................... 7 Pseudocode Maximum Selection Sort ......................................................................... 8 Loop Invariant Minimum Selection Sort ..................................................................... 8 Simulasi Algoritma Pengurutan Seleksi (Selection Sort)............................................. 9 Analisis dan Running Time Selection Sort ................................................................ 10 2. MERGE SORT ............................................................................................................. 12 Penjelasan Singkat Merge Sort ................................................................................ 12 Rekurensi (Reccurence) ........................................................................................... 12 Divide and Conquer ................................................................................................. 12 Pseudocode Merge Sort ........................................................................................... 12 Loop Invariant pada Prosedur Merge ...................................................................... 13 Simulasi Algoritma Merge Sort ................................................................................ 14 Analisis dan Running Time Merge Sort .................................................................... 19 3. ANALISIS PERBANDINGAN SELECTION SORT DENGAN MERGE SORT .............................. 20 BAB IV KESIMPULAN & SARAN ................................................................................. 22 1. KESIMPULAN ............................................................................................................. 22 2. SARAN ...................................................................................................................... 22 DAFTAR PUSTAKA ........................................................................................................ 23

1

KATA PENGANTAR

Bismillahirrahmanirrahiim. Assalamualaikum, wr. wb. Puji dan syukur penulis panjatkan kepada Allah SWT, shalawat serta salam semoga senantiasa dilimpahkan kepada Nabi Muhammad SAW, juga untuk para keluarga, sahabat dan pengikutnya sampai akhir zaman. Karena atas rahmat-Nya, penulis dapat menyelesaikan karya tulis ini yang berjudul “Analisis Perbandingan Algoritma Selection Sort dengan Merge Sort”. Karya tulis ini dibuat untuk memenuhi tugas Ujian Tengah Semester Genap dari mata kuliah Analisis Algoritma. Penulis ingin mengucapkan terima kasih kepada Ibu Ria Hari Gusmita, ST., M.Kom. selaku dosen pengampu, teman-teman dan semua pihak yang membantu dalam penyelesaian karya tulis ini. Penulis juga menyadari jika karya tulis ini masih jauh dari kesempurnaan dan terdapat banyak kekurangan. Untuk itu penulis mengharapkan kritik, koreksi dan saran dari semua pembaca dalam penyempurnaan karya tulis ini. Semoga karya tulis ini bermanfaat bagi pembaca, khususnya bagi penulis mengenai pemahaman analisis algoritma. Penulis menghaturkan permohonan maaf jika masih terdapat kekurangan dalam karya tulis ini. Wassalamualaikum, wr. wb.

Penulis

2

BAB I PENDAHULUAN

1. Latar Belakang Dalam pembuatan sebuah aplikasi seringkali kita membutuhkan sebuah algoritma yang dapat digunakan untuk melakukan pengurutan data, baik data yang berupa bilangan, karakter dan string. Algoritma yang digunakan tersebut selain harus menghasilkan data yang benar, juga harus efektif dan efisien. Namun ada hal lain yang harus dipertimbangkan, misalnya jumlah data yang akan diurutkan. Jika hanya sedikit data yang akan diurutkan maka perbedaan antar algoritma pengurutan tidak terlalu berpengaruh, sebaliknya jika terdapat banyak data yang akan diurutkan maka akan terlihat perbedaan dan keunggulan suatu algoritma, terutama dalam hal kecepatan dan pemakaian jumlah memori. Untuk itulah dalam karya tulis ini akan dibahas mengenai dua buah algoritma pengurutan yaitu algoritma pengurutan seleksi (selection sort) dan algoritma pengurutan merge (merge sort) dengan analisis dan perbandingan kompleksitasnya.

2. Metode Penulisan Penulisan karya tulis ini menggunakan metode pustaka terutama dengan sumber atau referensi dari internet dan analisis dari penulis.

3. Tujuan Penulisan Penulisan karya tulis ini bertujuan sebagai berikut : 

Memenuhi nilai tugas UTS mata kuliah Analisis Algoritma yang diampu oleh ibu Ria Hari Gusmita, ST., M.Kom.



Menambah pengetahuan penulis mengenai analisis algoritma terutama algoritma pengurutan yang dibahas di karya tulis ini.

4. Manfaat Penulisan Penulis berharap semoga karya tulis ini dapat menambah pemahaman bagi pembaca dan penulis mengenai analisis algoritma.

3

BAB II LANDASAN TEORI

1. Algoritma Pengurutan Algoritma merupakan urutan aksi-aksi yang dinyatakan dengan jelas dan tidak rancu untuk memecahkan suatu masalah dalam rentang waktu tertentu. Sedangkan pengurutan adalah proses pengaturan sekumpulan objek berdasarkan urutan atau susunan tertentu, dapat berupa pengurutan menaik (ascending) atau menurun (descending). Contoh, sebuah larik atau array terdiri dari kumpulan bilangan : [3,12,1,50,33,5,28] 

Hasil pengurutan menaik (ascending) : [1,3,5,12,28,33,50]



Hasil pengurutan menurun (descending) : [50,33,28,12,5,3,1] Sebuah algoritma dikatakan baik jika menghasilkan nilai yang benar, efektif dan

efisien. Efektif yaitu tepat sasaran, jelas dan tidak rancu dalam menjalankan aksi-aksinya serta menghasilkan data yang benar. Efisien yaitu penghematan proses dari sebuah algoritma, seperti running time dan penggunaan memori. Metode atau algoritma pengurutan dapat diklasifikasikan menjadi : 1.

Metode atau algoritma pengurutan internal, yaitu pengurutan yang dilakukan di dalam larik itu sendiri. Datanya disimpan di dalam memori komputer.

2.

Metode atau algoritma pengurutan eksternal, yaitu pengurutan yang datanya disimpan di dalam disk storage. Metode ini disebut juga pengurutan arsip. Sedangkan berdasarkan kestabilan (stability), algoritma pengurutan dapat dibagi menjadi dua jenis, yaitu :

1. Metode pengurutan stabil (stable sorting algorithm), merupakan algoritma pengurutan yang menjaga/mempertahankan (maintenance) urutan dari beberapa elemen array yang bernilai sama. 2. Metode pengurutan tidak stabil (non stable sorting algorithm), merupakan metode pengurutan yang tidak menjaga/mempertahankan (maintenance) urutan dari beberapa elemen array yang bernilai sama. Dengan kata lain, urutan beberapa elemen yang sama berbeda antara sebelum dan sesudah pengurutan. Algoritma memiliki dua skema, yaitu iteratif dan rekursif. Iteratif yaitu algoritma yang melakukan perulangan biasa, sedangkan rekursif adalah algoritma yang melakukan perulangan dengan melakukan pemanggilan terhadap dirinya sendiri. Contoh algoritma pengurutan yang termasuk dalam skema iteratif, yaitu pengurutan apung (bubble sort), 4

pengurutan seleksi (selection sort), pengurutan sisipan (insertion sort), shell (shell sort). Contoh algoritma pengurutan yang termasuk dalam skema rekursif, yaitu pengurutan merge (merge sort), pengurutan heap (heap sort) dan pengurutan cepat (quick sort). Tidak semua algoritma tersebut hanya memiliki satu skema, misalnya algoritma pengurutan seleksi atau selection sort yang dapat menggunakan skema rekursif, namun di dalam karya tulis ini selection sort yang dibahas menggunakan skema iteratif.

2. Kompleksitas Algoritma Efisiensi sebuah algoritma tergantung dari beberapa hal, diantaranya adalah : 

Kinerja CPU



Kinerja Memori



Kinerja Disk



Kinerja Jaringan Algoritma memiliki kompleksitas, kompleksitas merupakan acuan utama utama

untuk mengetahui kecepatan dari sebuah algoritma. Kompleksitas dibagi menjadi tiga, yaitu : 1. Best case (Ω), yaitu kompleksitas algoritma dimana algoritma tersebut berjalan dalam kondisi terbaik. 2. Average case (Θ), yaitu kompleksitas algoritma dimana algoritma tersebut berjalan dalam kondisi sedang, biasanya inputnya secara acak. 3. Worst case (Ο), yaitu kompleksitas algoritma dimana algoritma tersebut berjalan dalam kondisi terburuk.

3. Growth Function Kinerja sebuah algoritma biasanya di ukur dengan mengacu pada kondisi terburuknya, yaitu worst case yang dilambangkan dengan notasi Big O. Notasi Big O adalah fungsi yang berkaitan dengan kelajuan proses dan kelajuan pertambahan data. Notasi

Nama

O(1)

Konstan

O(log * n)

Iterasi logaritmik

O(log n)

Logaritmik

O((log n)c)

Polilogaritmik

O(n)

Linear

Contoh Aplikasi Menentukan apakah suatu bilangan ganjil atau genap Algoritma pencarian Hopcraft dan Ullman untuk himpunan disjoint Pencarian dalam list terurut dengan Binary Search Algorithm Menentukan bilangan prima dengan AKS primality test Pencarian dalam list tidak terurut 5

O(n log n) O(n2)

Linearitmik Kuadratik

O(nc), c > 1

Poliomial

O(cn)

Eksponensial

O(n!)

Faktorial

O(2cn)

Dobel Eksponensial

Mengurutkan list dengan Heapsort Mengurutkan list dengan Insertion Sort Pencarian shortest path dengan algoritma FloydWarshall Pencarian solusi untuk traveling salesman problem Menyelesaikan traveling salesman problem dengan menggunakan brute force Pencarian himpunan lengkap dari AC-unifiers (associative-commutative unifiers)

4. Notasi Asimptotik Notasi asimptotik digunakan untuk menentukan kompleksitas suatu algoritma dengan melihat waktu tempuh (running time) sebuah algoritma. Waktu tempuh algoritma merupakan fungsi : N → R+. Notasi asimptotik memungkinkan untuk membandingkan suatu algoritma dengan algoritma lainnya. Notasi asimptotik dapat dituliskan dengan beberapa simbol, yaitu : 

Notasi Big O, yaitu notasi asimptotik sebuah fungsi algoritma untuk batas atas.



Notasi Little o, yaitu notasi asimptotik sebuah fungsi algoritma untuk batas atas namun tidak secara ketat terikat (not asymptotically tight).



Notasi Theta (), yaitu notasi asimptotik sebuah fungsi algoritma untuk batas atas dan bawah.



Notasi Similaritas/Tilda (~), yaitu notasi asimptotik yang digunakan untuk membandingkan level of performance dua buah fungsi algoritma.



Notasi Omega (), yaitu notasi asimptotik sebuah fungsi algoritma untuk batas bawah, notasi ini berlawanan dengan notasi little-o.

6

BAB III PEMBAHASAN

1. Selection Sort Penjelasan Singkat Selection Sort Algoritma pengurutan seleksi atau selection sort merupakan kombinasi antara sorting dan searching. Konsep dari atau selection sort yaitu dengan memilih elemen larik yang memiliki nilai paling besar atau paling kecil, lalu menempatkannya pada posisi awal atau akhir elemen larik (array). Lalu elemen terujung pada larik diisolasi. Proses tersebut dilakukan sebanyak n-1 (jumlah elemen larik dikurang 1). Algoritma pengurutan seleksi atau selection sort dapat menggunakan skema iteratif (perulangan biasa) maupun skema rekursif (perulangan dengan memanggil dirinya sendiri). Namun kali ini kita hanya akan membahas algoritma pengurutan seleksi atau selection sort yang menggunakan skema iteratif. Algoritma pengurutan seleksi atau selection sort dibagi menjadi dua, yaitu : 1. Algoritma pengurutan seleksi minimum atau minimum selection sort Yaitu dengan mencari nilai terkecil dari array dan digunakan sebagai pembanding. 2. Algoritma pengurutan seleksi maksimum atau maximum selection sort Yaitu dengan mencari nilai terbesar dari array dan digunakan sebagai pembanding. Pseudocode Minimum Selection Sort procedure MinSelectionSort(input/output A : Larik, input n : integer) DEKLARASI : i, j : integer imin : integer temp : integer ALGORITMA : for i  1 to n-1 do imin  i for j  i+1 to n do if A[j] < A[imin] then imin  j endif endfor temp  A[i] A[i]  A[imin] A[imin]  temp endfor end procedure

7

Pseudocode Maximum Selection Sort procedure MaxSelectionSort(input/output L : Larik, input n : integer) DEKLARASI : i, j : integer imaks : integer temp : integer DEFINISI : for i  n downto 2 do imaks  1 for j  2 to i do if L[j] > L[imaks] then imaks  j endif endfor temp  L[i] L[i]  L[imaks] L[imaks]  temp endfor end procedure

Algoritma pengurutan seleksi (selection sort) adalah algoritma yang tidak stabil, karena urutan beberapa elemen yang sama berbeda antara sebelum dan sesudah pengurutan. Algoritma ini juga termasuk algoritma pengurutan internal, karena melakukan sorting di dalam array itu sendiri, dan menyimpan datanya di dalam memori komputer. Yang akan dibahas kali ini adalah menggunakan pengurutan seleksi minimum (minimum selection sort) secara menaik (ascending), yaitu selection sort dengan menggunakan nilai terkecil di dalam array sebagai pembanding. Loop Invariant Minimum Selection Sort  Statement Saat awal algoritma dijalankan, nilai imin berisi indeks elemen terkecil dari larik A[1...j - 1]. 

Initialization

Sebelum iterasi atau pass pertama dilakukan, nilai j = i + 1, imin berisi indeks elemen terkecil dari larik A[i...i] yang merupakan indeks elemen paling pertama larik A. 

Maintenance

Sebelum iterasi ke- jth, imin berisi indeks elemen terkecil dari larik A[i...j - 1]. Kemudian setelah dijalankan, jika A[j] < A[imin] maka imin bernilai sama dengan j dan menyimpan indeks terkecil larik A[i...j]. 

Termination 8

Sebelum iterasi ke- (n + 1)th, j = n + 1, imin berisi indeks terkecil dari elemen larik A[i...n].

Simulasi Algoritma Pengurutan Seleksi (Selection Sort) Contoh, kita memiliki sebuah larik (array) (A) yang memiliki 7 buah elemen. Larik tersebut akan diurutkan secara menaik (ascending) dengan mencari nilai minimum sebagai pembanding. 26

19

38

3

9

13

21

1. Pass 1 

Cari nilai elemen terkecil dari array (larik) A[1...7] dengan membandingkan antar nilai elemen array, didapatkan elemen terkecil A[4] = 3.



Tukarkan dengan nilai elemen terujung (awal) yaitu A[1]. Lalu elemen A[1] tersebut sudah terurut. 3

19

38

26

9

13

21

2. Pass 2 





9

38

26

19

13

21

3. Pass 3 





9

13

26

19

38

21

4. Pass 4 


9




9

13

19

26

38

21

5. Pass 5 





9

13

19

21

38

26

6. Pass 6 (n-1) 





9

13

19

21

26

38

Elemen yang tersisa yaitu elemen terakhir A[7] = 38. Elemen tersebut tidak perlu diurutkan karena elemen tersebut berada pada posisi yang sudah terurut. Jadi array atau larik A sudah terurut. Hasil array A yang sudah terurut yaitu : 3

9

13

19

21

26

38

Analisis dan Running Time Selection Sort Running time algoritma pengurutan seleksi (selection sort) dapat dihitung dengan : SELECTION SORT

Cost

Times

for i  1 to n-1 do

C1

n

imin  i

C2

n-1

for j  i+1 to n do

C3

∑(

C4

∑( )

C5

∑(

if L[j] < L[imin] then imin  j

10

)

)

0

∑( )

endfor

0

∑(

temp  L[i]

C6

n-1

C7 C8 0

n-1 n-1 n

endif

L[i]  L[imin] L[imin]  temp endfor

)

Keterangan : 

ti,j bernilai 1 jika kondisi if benar, 0 jika salah.



C3.∑

(



C4.∑

( ) = C4.



C5.∑

(

) = C3.∑ (

) = C5.

( ) + C3.∑

( ) = C3.

(

)

+ C3.(

)

) (

)

ti,j dapat bernilai 1 atau 0.

o Ketika kondisi best case maka kondisi if salah, ti,j = 0. Kondisi best case terjadi jika data dalam elemen array sudah terurut. Maka : ( )

(

)

(

)

(

)

( ) Didapatkan notasi asimptotik best case selection sort adalah ( )

(

)

o Ketika kondisi worst case maka kondisi if benar, ti,j = 1. Kondisi worst case terjadi jika data dalam elemen array terurut secara terbalik. Maka : ( )

(

)

(

)

(

)

( ) Didapatkan notasi asimptotik worst case selection sort adalah ( )

(

)

o Jadi baik dalam kondisi worst case, average case maupun best case didapatkan kompleksitas waktu algoritma selection sort yaitu : ( )

11

(

)

2. Merge Sort Penjelasan Singkat Merge Sort Algoritma merge sort dirancang untuk memenuhi kebutuhan pengurutan jika data yang diurutkan berjumlah banyak, dan tidak memungkinkan untuk ditampung dalam memori komputer. Cara kerja atau konsep dari algoritma merge sort adalah menggunakan metode rekursif dan teknik divide and conquer. Rekurensi (Reccurence) Merupakan sebuah fungsi atau prosedur yang digambarkan secara rekursif. Rekursif adalah proses untuk memanggil dirinya sendiri. Dan fungsi running time-nya dapat digambarkan oleh recurrence (Rekurensi). Definisi rekursif disusun oleh dua bagian, yaitu : 1. Basis, yaitu bagian yang berisi kasus yang terdefinisi secara eksplisit dan berguna untuk menghentikan rekursif (memberikan sebuah nilai yang terdefinisi pada fungsi rekursif). 2. Rekurens, yaitu bagian yang mendefinisikan objek dalam terminologi dirinya sendiri. Misalnya pada proses untuk menghitung faktorial dari n, maka : 

Basis :

n!=1

,n=0



Rekurens :

n ! = n x (n - 1) !

,n>0

Divide and Conquer 1. Divide : membagi sebuah array menjadi dua array, sebuah problem dipecah menjadi sub-sub problem yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil. 2. Conquer : menyelesaikan masalah secara rekursif, yaitu mengurutkan setiap array. 3. Combine : menggabungkan solusi yaitu dua array yang sudah terurut. Pseudocode Merge Sort PROCEDURE MERGESORT(A, p, r) IF p < r // Check for base case THEN q = FLOOR⌊(p + r)/2⌋ MERGESORT(A, p, q) MERGESORT(A, q + 1, r) MERGE(A, p, q, r)

// Divide step. // Conquer step. // Conquer step. // Conquer step.

PROCEDURE MERGE(A, p, q, r)

12

n1 ← q − p + 1 n2 ← r − q Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1] FOR i ← 1 TO n1 DO L[i] ← A[p + i − 1] FOR j ← 1 TO n2 DO R[j] ← A[q + j] L[n1 + 1] ← ∞ R[n2 + 1] ← ∞ i ← 1 j ← 1 FOR k ← p TO r DO IF L[i] ≤ R[j] THEN A[k] ← L[i] i ← i + 1 ELSE A[k] ← R[j] j ← j + 1

Loop Invariant pada Prosedur Merge  Statement Setiap iterasi pada for (pengulang) yang terakhir, sub-array A[p...k - 1] berisi nilai k-p elemen terkecil dari array L dan R dalam keadaan yang sudah terurut. L[i] dan R[j] merupakan elemen terkecil dari array L dan R yang tidak di-copy ke array A. 

Initialization

Sebelum iterasi pertama dilakukan, k = p. Sub-array A[p…k - 1] berisi 0 elemen terkecil dari array L dan R. Ketika i = j = 1, L[i] dan R[j] adalah elemen terkecil dari array yang tidak di-copy ke array A. Kedua array L dan R dalam keadaan yang terurut. 

Maintenance Misalkan L[i] ≤ R[j], maka L[i] adalah elemen terkecil yang tidak di-copy ke array A. A[p…k - 1] adalah k - p elemen terkecil, L[i] adalah (k – p + 1)th elemen terkecil. Kemudian L[i] di-copy ke A[k], A[p…k] berisi k – p + 1 elemen terkecil. Secara berulang, nilai k + i membuat perulangan (loop invariant). Jika L[i] > R[j], maka nilai R[j] di-copy ke array A[k], dan nilai j + 1 agar pengulangan dapat terus dilakukan.



Termination Ketika nilai k = r + 1, A[p…k - 1] = A[p…r] berisi k - p elemen terkecil dalam keadaan yang terurut. Menghasilkan k - p = r + 1 - p elemen terkecil dalam keadaan yang terurut. Kedua array L dan R berisi n1 + n2 + 2 = r -p + 3 elemen, dan dua buah ∞ telah di-copy kembali ke array A.

13

Simulasi Algoritma Merge Sort Contoh, kita memiliki sebuah larik (array) (A) yang memiliki 4 buah elemen. Larik tersebut akan diurutkan secara menaik (ascending). Dengan nilai p adalah indeks elemen awal, yaitu p = 0. Nilai r adalah indeks elemen akhir, yaitu r = 3. 12

9

24

2

A[0...3] = 1. MERGESORT(A, 0, 3). 

Kemudian diperiksa apakah jika p < r, (0 < 3), jika benar maka dihitung q = ⌊(p + r)/2⌋ = 1.



Kemudian dipanggil MERGESORT(A, 0, 1), MERGESORT(A, 2, 3) dan MERGE(A, 0, 1, 3).

1.1. MERGESORT(A, 0, 1) 




Kemudian dipanggil MERGESORT(A, 0, 0), MERGESORT(A, 1, 1) dan MERGE(A, 0, 0, 1). 12



9

A[0...1] =

1.1.1. MERGESORT(A, 0, 0) Kemudian diperiksa apakah jika p < r, (0 < 0), karena salah maka rekursif pada bagian ini selesai. 1.1.2. MERGESORT(A, 1, 1) Kemudian diperiksa apakah jika p < r, (1 < 1), karena salah maka rekursif pada bagian ini selesai. 1.1.3. MERGE(A, 0, 0, 1) 

Sesuai dengan algoritma maka nilai : o n1 = q − p + 1 = 1 o n2 = r – q = 1.



Lalu buat dua buah array bernama L dan R dengan jumlah elemen o L[1 . . n1 + 1] yaitu L[1...2] o R[1 . . n2 + 1] yaitu R[1...2]



Perulangan pada : 14

o FOR i ← 1 TO n1 DO L[i] ← A[p + i − 1] o nilai L[1] = A[0] = 12. 12

o L[1] = 

Perulangan pada : o FOR j ← 1 TO n2 DO R[j] ← A[q + j] o nilai R[1] = A[1] = 9. 9

o R[1] = 

Kemudian ditambahkan L[n1 + 1] ← ∞ dan R[n2 + 1] ← ∞, sehingga L[2] = ∞ dan R[2] = ∞. Sehingga array L dan R berisi : ∞

12

Array L =

9

∞

dan Array R =

Kedua array tersebut sudah dalam keadaan terurut. 

Nilai i dan j di inisialisasi menjadi i = 1 dan j = 1. Kemudian lakukan pengulangan pada : o FOR k ← p TO r DO IF L[i] ≤ R[j] THEN A[k] ← L[i] i ← i + 1 ELSE A[k] ← R[j] j ← j + 1 o Untuk menggabungkan array L dan R ke array A dalam keadaan terurut. o Didapatkan : 

L[1] ≤ R[1], 12 ≤ 9 = False, maka A[0] = R[1] = 9



L[1] ≤ R[2], 12 ≤ ∞ = True, maka A[1] = L[1] = 12. 9

12

o A[0...1] = 1.2. MERGESORT(A, 2, 3)

15






Kemudian dipanggil MERGESORT(A, 2, 2), MERGESORT(A, 3, 3) dan MERGE(A, 2, 2, 3). 24



2

A[2...3] =

1.2.1. MERGESORT(A, 2, 2) Kemudian diperiksa apakah jika p < r, (2 < 2), karena salah maka rekursif pada bagian ini selesai. 1.2.2. MERGESORT(A, 3, 3) Kemudian diperiksa apakah jika p < r, (3 < 3), karena salah maka rekursif pada bagian ini selesai. 1.2.3. MERGE(A, 2, 2, 3) 







Perulangan pada : o FOR i ← 1 TO n1 DO L[i] ← A[p + i − 1] o nilai L[1] = A[2] = 24. 24

o L[1] = 

Perulangan pada : o FOR j ← 1 TO n2 DO R[j] ← A[q + j] o nilai R[1] = A[3] = 2. 2

o R[1] =

16



Kemudian ditambahkan L[n1 + 1] ← ∞ dan R[n2 + 1] ← ∞, sehingga L[2] = ∞ dan R[2] = ∞. Sehingga array L dan R berisi : ∞

24

Array L =

2

∞

dan Array R =



L[1] ≤ R[1], 24 ≤ 2 = False, maka A[2] = R[1] = 2



L[1] ≤ R[2], 24 ≤ ∞ = True, maka A[3] = L[1] = 24. 2

24

o A[2...3] = 1.3. MERGE(A, 0, 1, 3) 







Perulangan pada : o FOR i ← 1 TO n1 DO L[i] ← A[p + i − 1] o nilai L[1] = A[0] = 9 dan L[2] = A[1] = 12. 9

12

o L[1...2] = 17



Perulangan pada : o FOR j ← 1 TO n2 DO R[j] ← A[q + j] o nilai R[1] = A[2] = 2 dan R[2] = A[3] = 24. 2

24

o R[1...2] = 

Kemudian ditambahkan L[n1 + 1] ← ∞ dan R[n2 + 1] ← ∞, sehingga L[2] = ∞ dan R[2] = ∞. Sehingga array L dan R berisi : 9

∞

12

Array L =

2

24

∞

dan Array R =



L[1] ≤ R[1], 9 ≤ 2 = False, maka A[0] = R[1] = 2



L[1] ≤ R[2], 9 ≤ 24 = True, maka A[1] = L[1] = 9.



L[2] ≤ R[2], 12 ≤ 24 = True, maka A[2] = L[2] = 12



L[3] ≤ R[2], ∞ ≤ 24 = False, maka A[3] = R[2] = 24. 2

9

12

24

o A[0...3] = Jika digambarkan secara sederhana maka proses eksekusi algoritma merge sort adalah :

18

Array unsorted

12

A[0...3]

9

24

2

divide to sub-array

A[0...1]

12

9

24

L[]

A[0...1]

merge & sort sub-array L & R to array A

9

A[2...3]

divide to sub-array L & R

divide to sub-array L & R

12

2

9

24

R[]

L[]

12

2 merge & sort sub-array L & R to array A

2

R[]

24

A[2...3]

merge & sort subarray to array A Sorted Array

A[0...3]

2

9

12

24

Hasil pengurutannya adalah array A dengan elemen seperti dibawah. 2

9

12

24

A[0...3] = Analisis dan Running Time Merge Sort Merge sort selalu membagi setiap array menjadi dua sub-array hingga mencapai basis, sehingga kompleksitas dari algoritma merge sort, berlaku untuk semua kasus (Worst Case = Best Case = Average Case). 

Untuk memudahkan, kita anggap jumlah elemen array (n) adalah kelipatan 2, jadi setiap dilakukan divide (pemecahan menjadi dua sub-array), kedua sub-array akan berukuran n/2.



Basis : untuk n = 1, maka array tersebut sudah terurut dengan sendirinya.



Rekurens : untuk n > 1, maka akan dilakukan langkah-langkah merge sort, yaitu : o Divide : Hitung nilai q yang merupakan rata-rata dari p + r, yang bernilai Θ(1). o Conquer : Secara rekursif menyelesaikan 2 sub-array, setiap sub-array berukuran n/2, maka bernilai 2T(n/2). 19

o Combine : Menggabungkan element dari sub-array ke dalam array dengan prosedur MERGE, bernilai Θ(n). 

Jumlahkan semua fungsi yang dihasilkan, sehingga dihasilkan rekurens : ( )



( ) {

( )

}

( )

Dari rekurens tersebut di ubah untuk mendapatkan kompleksitas waktu algoritma merge sort, sehingga ( )

(

)

Catatan : log n = log2 n = 2log n. 

Kompleksitas waktu tersebut dapatk dijelaskan dari recursif tree berikut : o Array awal (cn), yang memiliki dua sub-array, masing-masing bernilai T(n/2).

o Kemudian sub-array tersebut di bagi lagi menjadi dua sub-sub-array, jadi bernilai T(n/4) dan seterusya.

o Di dapatkan tinggi pohon rekursif adalah log n, dan memiliki sebanyak log n + 1 level. Setiap level bernilai cn, sehingga cn log n + cn. o Koefisien c tidak perlu di masukkan, sehingga kompleksitas waktunya menjadi ( )

(

)

3. Analisis Perbandingan Selection Sort dengan Merge Sort Dari hasil analisis sebelumnya telah didapatkan kompleksitas waktu algoritma pengurutan seleksi (selection sort) dan merge sort, yaitu : 1. Selection sort memiliki kompleksitas waktu untuk kondisi best case, average case maupun worst case dengan : ( )

(

20

)

2. Merge sort memiliki kompleksitas waktu untuk kondisi best case, average case maupun worst case dengan : ( )

(

)

Jika dibandingkan dari kompleksitas waktu kedua algoritma tersebut maka algoritma yang running time-nya lebih cepat adalah algoritma merge sort. Baik dalam keadaan best case, average case maupun worst case. Merge sort memiliki running time yang lebih cepat dibandingkan selection sort, karena nilai n log n lebih kecil dari n2. Untuk jumlah data atau elemen array yang sedikit, perbedaan running time selection sort dan merge sort tidak terlalu terlihat, bisa saja lebih cepat selection sort atau merge sort. Hal ini dapat dipengaruhi oleh kemampuan komputer, jumlah memori dan faktor lain. Namun jika jumlah data atau elemen array yang sangat banyak, perbedaan running time selection sort dan merge sort akan sangat terlihat, semakin banyak data yang akan diurutkan, semakin terlihat perbedaan running time-nya.

21

BAB IV KESIMPULAN & SARAN

1. Kesimpulan Hasil analisis perbandingan selection sort dan merge sort menunjukkan bahwa running time merge sort lebih cepat. Hal ini akan terlihat jika jumlah data yang akan diurutkan berjumlah banyak, semakin banyak data semakin terlihat perbedaan kecepatan algoritma. Sedangkan jika data berjumlah sedikit maka perbedaan antara selection sort dan merge sort tidak begitu siginifikan. Perlu dipertimbangkan juga faktor lain yang mempengaruhi kecepatan eksekusi sebuah algoritma selain kompleksitas waktu dan jumlah data, yaitu faktor kemampuan komputer, jumlah memori dan lain-lain. Selain itu pertimbangan dari penggunaan sebuah algoritma tidak hanya di lihat dari running time-nya, tetapi dari kebutuhan. Misalnya kita membutuhkan algoritma untuk mengurutkan jumlah data yang sedikit (kurang dari 100 elemen), maka kita dapat menggunakan selection sort daripada merge sort karena perbedaan kecepatan yang tidak signifikan.

2. Saran Penulis menyarankan untuk penulisan karya tulis selanjutnya agar algoritma pengurutan yang dibahas lebih banyak lagi disertai dengan simulasi dan analisis, serta diberikan contoh program atau program simulasi step-by-step untuk memperjelas materi pembahasan.

22

DAFTAR PUSTAKA

Fanani, Ikhsan. Penggunaan ”Big O Notation” untuk Menganalisa Efisiensi Algoritma. Program Studi Teknik Informatika, Institut Teknologi Bandung. M. Fachrurrozi, Dwi Rosa Indah. 2006. Modul Praktikum “Algoritma dan Pemrograman I”. Laboratorium Dasar Komputer Program Ilmu Komputer Universitas Sriwijaya. Ria Hari Gusmita, ST., M.Kom. Algoritma dan Pemrograman 2 : Pengurutan (Bubble dan Selection Sort). Internet : http://andikafisma.wordpress.com/algoritma-divide-and-conquer/, diakses pada 29 Mei 2012, 22:15. http://blog.ub.ac.id/satriabram/2012/03/13/rangkuman-mengenai-asymptotic-notationjenis-notationnya-beserta-contoh-algoritma-dan-perhitungan-notationnya/, diakses pada 31 Mei 2012, 21:58. http://informatikauad.files.wordpress.com/2010/03/catatan-analisis-algoritma.doc, diakses pada 31 Mei 2012, 21:53. http://personal.denison.edu/~kretchmar/272/SelectionSortAnalysis.pdf, diakses pada 31 Mei 2012, 23:44. http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/sortingII/mergeSort/mergeSort.html , diakses pada 31 Mei 2012, 15:35. http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/merge/mergen.htm,

diakses

pada 30 Mei 2012, 23:08. http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/mergeS ort.htm, diakses pada 30 Mei 2012, 23:10. http://www.scribd.com/doc/51164311/pengurutan, diakses pada 30 Mei 2012, 22:08. http://www.shannarasite.org/kb/kbse30.html, diakses pada 31 Mei 2012, 09:35. 23

http://www.rodensi.blog.usu.ac.id/2010/11/28/merge-sort-dengan-java/, diakses pada 31 Mei 2012, 22:30.

24

ANALISIS PERBANDINGAN ALGORITMA SELECTION SORT DENGAN MERGE SORT

Recommend Documents