ANALISIS PENGARUH STRUKTUR DATA TERHADAP KOMPLEKSITAS WAKTU KOMPUTASI ALGORITMA SELECTION SORT DAN MERGE SORT
TESIS
JIJON SAGALA 117038054
PROGRAM STUDI MAGISTER (S2) TEKNIK INFORMATIKA FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2013
Universitas Sumatera Utara
ANALISIS PENGARUH STRUKTUR DATA TERHADAP KOMPLEKSITAS WAKTU KOMPUTASI ALGORITMA SELECTION SORT DAN MERGE SORT
TESIS
Diajukan untuk melengkapi tugas dan memnuhi syarat memperoleh ijazah Magister Teknik Informatika JIJON SAGALA 117038054
PROGRAM STUDI MAGISTER (S2) TEKNIK INFORMATIKA FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2013
Universitas Sumatera Utara
PERSETUJUAN
Judul Tesis
: ANALISIS PENGARUH STRUKTUR DATA TERHADAP KOMPLEKSITAS WAKTU KOMPUTASI ALGORITMA SELECTION SORT DAN MERGE SORT
Nama Mahasiswa
: JIJON SAGALA
No. Induk Mahasiswa
: 117038054
Program Studi
: MAGISTER TEKNIK INFORMATIKA
Fakultas
: ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA
Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Prof. Dr. Drs. Iryanto, M.Si
Prof. Drs. Tulus, Vordipl.Math, M.Si, Ph.D
Diketahui/Disetujui oleh Program Studi S2 Teknik Informatika Ketua,
Prof. Dr. Muhammad Zarlis Nip. 19570701 198601 1 003
Universitas Sumatera Utara
PERNYATAAN
ANALISIS PENGARUH STRUKTUR DATA TERHADAP KOMPLEKSITAS WAKTU KOMPUTASI ALGORITMA SELECTION SORT DAN MERGE SORT
TESIS
Saya yang mengakui bahwa tesis ini adalah hasil karya tulis saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing telah saya sebutkan sumbernya.
Medan, 30 Oktober 2013
JIJON SAGALA NIM : 110738054
Universitas Sumatera Utara
PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS
Sebagai civitas akademika Universitas Sumatera Utara, saya yang bertanda tangan dibawah ini :
Nama
: Jijon Sagala
NIM
: 117038054
Program Studi
: S2 Teknik Informatika
Jenis Karya Ilmiah
: Tesis
Demi pengembangan ilmu pengetahuan, menyetujui untuk memberikan kepada Universitas Sumatera Utara Hak Bebas Royalti Non-Eksklusif ( Non-Exclusive Rayalty Free Eight ) atas tesis saya yang berjudul:
ANALISIS PENGARUH STRUKTUR DATA TERHADAP KOMPLEKSITAS WAKTU KOMPUTASI ALGORITMA SELECTION SORT DAN MERGE SORT
Beserta perangkat yang ada(jika diperlukan). Dengan Hak Bebas Royalti Non-Eksklusif ini, Universitas Sumatera Utara berhak menyimpan, mengalih media, menformat, mengelola dalam bentuk database, merawat dan mempublikasikan tesis saya tanpa meminta izin dari saya selama tetap mencantumkan nama saya sebagai penulis dan sebagai pemegang dan/atau sebagai pemilik hak cipta Demikian pernyataan ini dibuat dengan sebernarnya. Medan, 30 Oktober 2013
Jijon Sagala 117038054
Universitas Sumatera Utara
Telah diuji pada Tanggal : Rabu 30 Oktober 2013
PANITIA PENGUJIAN TESIS Prof. Drs. Tulus, Vordipl.Math, M.Si, Ph.D
Ketua
:
Anggota
: 1. Prof. Dr. Drs. Iryanto, M.Si 2. Prof. Dr. Muhammad Zarlis 3. Prof. Dr. Herman Mawengkang 4. Dr. Erna Budhiarti Nababan, M.IT
Universitas Sumatera Utara
DAFTAR RIWAYAT HIDUP
DATA PRIBADI Nama Lengkap ( Berikut Gelar ) : Jijon Sagala, S.Kom Tempat dan Tanggal Lahir
: Situnggaling, 4 September 1984
Alamat Rumah
: Jln. B.W. Kusuma No.14C, Pasar 4 Padang Bulan
Telepon/Fax/HP
: 081361587795
E-Mail
:
[email protected]
Instansi Tempat Bekerja
: YPN Medicom
Alamat Kantor
: Jln. Bantam No 12 Medan
DATA PENDIDIKAN SD
SD Inpres Merek
TAMAT 1998
SMP
SMP Negeri 1 Merek
TAMAT 2001
SMA
SMA Sw Dharma Pancasila Medan
TAMAT 2004
D1
PABT D1 Medicom Medan
TAMAT 2005
D3
AMIK D3 Medicom Medan
TAMAT 2007
S1
STMIK Sisingamangaraja XII Medan
TAMAT 2011
S2
Teknik Informatika USU
TAMAT 2013
Universitas Sumatera Utara
UCAPAN TERIMA KASIH
Puji dan syukur kehadirat Tuhan Yang Maha Esa atas anugerahNya dan berkatNya Penulis dapat menyelesaikan Tesis ini, yang berjudul “ ANALISIS PENGARUH STRUKTUR DATA
TERHADAP
KOMPLEKSITAS
WAKTU
KOMPUTASI
ALGORITMA
SELECTION SORT DAN MERGER SORT ”. Tesis ini merupakan Tugas Akhir pada Program Studi Magister S2 Teknik Informatika Fakultas Ilmu Komputer dan Teknologi Informasi, Universitas Sumatera Utara. Dalam menyelesaikan pendidikan di Program Studi Magister S2 Teknik Informatika Universitas Sumatera Utara ini, penulis banyak mendapat dukungan dari berbagai pihak, maka pada kesempatan ini Penulis mengucapkan terima kasih dan penghargaan yang sebesar-besarnya kepada: 1. Prof. Dr. dr. Syahril Pasaribu, DTM&H, M.Sc(CTM), Sp,A(K) selaku Rektor Universitas Sumatera Utara. 2. Prof. Dr. Muhammad Zarlis selaku Dekan Fakultas Ilmu Komputer dan Teknologi Informasi
Universitas Sumatera Utara dan Ketua Program Studi Magister Teknik
Informatika dan juga sebagai pembanding pada penulisan Tesis ini dan berkat saran dan bantuanya beliau sehingga penulisan Tesis ini dapat diselesaikan dengan baik. 3. Muhammad Andri Budiman, ST., M.Comp.Sc., selaku sekretaris Program Studi Magister Teknik Informatika yang telah banyak memberikan bantuan dan motivasinya selama perkuliahan sehingga Penulis dapat menyelesaikan Tesis dan Perkualiahan ini. 4. Prof. Drs. Tulus, Vordipl.Math, M.Si, Ph.D, selaku Ketua Komisi Pembimbing pada penulisan Tesis ini, berkat dorongan dan bantuan beliau sehingga penulisan Tesis ini dapat diselesaikan dengan baik. 5. Prof. Dr. Drs. Iryanto, M.Si, selaku Anggota Komisi Pembimbing II yang telah
memberikan bimbingan dan petunjuk sehingga Tesis ini dapat diselesaikan dengan baik. 6. Prof. Dr. Herman Mawengkang selaku pembanding, atas saran dan bantuanya untuk kesempurnaan penulisan Tesis ini serta bimbingan selama perkuliahan berlangsung.
Universitas Sumatera Utara
7. Dr. Erna Budhiarti Nababan, M.IT selaku pembanding, atas saran dan bantuanya untuk kesempurnaan penulisan Tesis ini serta bimbingan selama perkuliahan berlangsung. 8. Seluruh Staf pengajar pada Program Studi Magister Teknik Informatika, Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara, yang telah memberikan ilmu pengetahuan kepada penulis selama perkuliahan hingga selesai. 9. Seluruh Staf administrasi Program Studi Magister Teknik Informatika mbak Widia, mbak Ines, bang Jawaher dan yang lainnya yang telah banyak memberikan bantuan dan pelayanan terbaik kapada Penulis. 10. Seluruh rekan-rekan seperjuangan mahasiswa angkatan ketiga stambuk 2011 Kom B Pak Pirmando Gultom, Bu Ertina Barus, Pak Andi Marwan, Bu Yulia Dalimunthe, Bu Fitri Marina, Pak Arman Barus, Pak Arta Pinem, Bu Wulan, Pak Muhazir dan yang lainnya, yang telah bersama-sama selama perkuliahan atas kerjasama, kebersamaan dan saling pengertiannya selama ini dalam mengatasi berbagai masalah yang dihadapi selama perkualiahan
tanpa menegenal lelah sehingga tugas-tugas bersama dapat
diselesaikan dengan baik. 11. dr. Reinhard Silalahi selaku Pimpinan Yayasan Pendidikan Nasional Medicom beserta seluruh staf yayasan dan staf pengajar yang telah memberikan dorongan dan dukungan sehingga Penulis dengan tetap suka cita dan bersemangat untuk menyelesaikan kuliah dengan baik. 12. Penulis menyampaikan terima kasih yang sangat luar biasa pada istri tercinta Marisa Natarlian Br Ginting, S.Pd atas cinta dan kasih serta doa yang tulus diberikan kepada penulis, sehingga dapat menyelesaikan Tesis dengan baik. 13. Penulis menyampaikan terima kasih yang tak terhingga kepada Bapak tercinta J. Sagala dan Mamak Tersayang S Br Munthe, saudaraku terkasih bang Jasa Sagala & Kak Rentina Br Sijabat, Kak Risa Br Sagala & bang Adi, Kak Riahta Br Sagala, SE, bang Junner Sagala & Kak Erti Br Sidabuke dan Adiku Irma Sari Br Sagala, SS serta keponakan ku Ozi, Enjel, Destri, Jesen Sagala, Jon Steven Sagala dan Jaren Sagala, kasih sayang dan dukungan tulus dari kalian adalah semangat hidupku. 14. Penulis juga menyampaikan terima kasih yang sangat besar kepada Bapak Mertua D. Ginting dan Ibu Mertua R Br Sebayang serta silihku Yuda Ginting & Novita Br Sembiring, Ari Widana Ginting, Amd dan Rio Febri Ginting, Amd dan keponaku Zikri
Universitas Sumatera Utara
Ginting, Giovani Ginting dan Tercio Ginting yang telah banyak memberikan doa yang tulus dan dukungan kepada penulis. Kepada semua pihak yang telah turut membantu penulisan Tesis ini baik langsung maupun tidak langsung yang penulis dapatkan selama ini. Semoga Tesis ini bermanfaat bagi pembaca dan pihak-pihak yang membutuhkannya.
Medan, 30 Oktober 2013 Penulis,
Jijon Sagala 117038054
Universitas Sumatera Utara
ABSTRAK
Seiring berkembangnya kemajuan di bidang informatika dan komputasi, tuntutan untuk menemukan metode pemecahan masalah secara lebih tepat, efektif dan kuat menjadi sebuah kebutuhan, terutama untuk permasalahan klasik. Salah satu masalah klasik di bidang informatika dan komputasi adalah pengurutan data ( sorting ). Pengurutan data ( sorting ) memegang peranan penting dalam banyak aplikasi dan persoalan yang mengacu pada banyak data (minimal lebih dari satu), dan seringkali menjadi upa-masalah yang banyak dipertimbangkan agar keseluruhan permasalahan dapat diselesaikan dengan lebih baik dan cepat. Algoritma pengurutan (sorting) yang dipakai adalah algoritma Merge Sort dan selection sort. Pada penilitian ini akan dipaparkan penjelasan singkat dan perbandingan kecepatan dan keefektifan algoritma-algoritma pengurutan data dengan elemen integer. Kata Kunci : Algoritma Pengurutan, Kompleksitas waktu, Selection Sort, Merge Sort
Universitas Sumatera Utara
DATA STRUCTURE INFLUENCE ANALYSIS TOWARDS ALGORITHM COMPUTATION TIME COMPLEXITY SELECTION SORT AND MERGE SORT
ABSTRACT
As the development advances in the field of informatics and computing, the demand to find a method of solving the problem more precise, effective and powerful become a necessity, especially for classical problems. One of the classic problems in the field of informatics and computing are data sorting (sorting). Data sorting (sorting) plays an important role in many applications and issues that refer to the data (at least more than one), and the ceremony is often a problem that many considered that the whole problem can be solved with better and faster. Sorting algorithms (sorting) is used and the Merge Sort algorithm selection sort. In this research will be presented a brief description and comparison of the speed and effectiveness of data sorting algorithms with integer elements. Keywords: Sorting Algorithms, Time Complexity, Selection Sort, Merge Sort.
Universitas Sumatera Utara
DAFTAR ISI Halaman PENGESAHAN
ii
PERNYATAAN ORISINALITAS
iii
PERSETUJUAN PUBLIKASI
iv
PANITIA PENGUJI
v
RIWAYAT HIDUP
vi
UCAPAN TERIMA KASIH
vii
ABSTRAK
x
ABSTACT
xi
DAFTAR ISI
xii
DAFTAR TABEL
xiv
DAFTAR GAMBAR
xv
BAB 1 PENDAHULUAN
1
1.1 Latar Belakang Masalah
1
1.2 Perumusan Masalah
3
1.3 Batasan Masalah
3
1.4 Tujuan Penelitian
3
BAB 2 TINJAUAN PUSTAKA
4
2.1 Pengertian Algoritma
4
2.2 Algoritma Pengurutan
5
2.3 Kompleksitas Algoritma
6
2.4 Growth Function
7
2.5 Notasi Asimptotik
8
2.6 Pengertian Selection Sort
8
2.7 Pengertian Merge Sort
9
2.8 Struktur Data
10
2.9 Penelitian Terdahulu
12
BAB 3 METODOLOGI PENELITIAN
13
3.1 Algoritma Selection Sort
13
Universitas Sumatera Utara
3.1.1 Pseudocode Minimum Selection Sort
13
3.1.2 Pseudocode Maximum Selection Sort
14
3.1.3 Loop Invariant Minimum Selection Sort
14
3.2 Simulasi Algoritma Pengurutan Selection Sort
15
3.3 Analisis Dan Running Time Selection Sort
17
3.4 Selection Sort Model Insert(Sisip)
18
3.4.1 Pseudecode Selection Sort Model Insert
18
3.4.2 Simulasi Algoritma Pengurutan Selection Sort Model Insert
19
3.5 Selection Sort Model New List(Dua List)
20
3.5.1 Pseudecode Selection Sort Model New List
20
3.5.2 Simulasi Algoritma Pengurutan Selection Sort Model New List
20
3.6 Penjelasan Singkat Merge Sort
21
3.6.1 Pseudocode Merge Sort
21
3.6.2 Loop Invariant Pada Prosedure Merge Sot
22
3.7 Simulasi Algoritma Merge Sort
23
3.8 Analisis Dan Running Time Merge Sort
28
BAB 4 HASIL DAN PEMBAHASAN
30
4.1 Pendahuluan
30
4.2 Hasil Dan Uji Coba
30
4.2.1 Pengurutan pada Max Item = 10
30
4.2.2 Pengurutanpada Max Item = 500
35
4.2.3 Pengurutanpada Max Item = 1000
39
4.3 Pembahasan
44
4.4 Analisis Perbandingan Selection Sort dengan Merge Sort
45
BAB 5 KESIMPULAN DAN SARAN
47
DAFTAR PUSTAKA LAMPIRAN
Universitas Sumatera Utara
DAFTAR TABEL
Tabel 2.1
Tabel Notasi Big O
7
Tabel 2.2
Perbedaan mendetail antara Array dan List
12
Tabel 3.1
Tabel Running Time
17
Universitas Sumatera Utara
DAFTAR GAMBAR
Gambar 4.1
Item Tampilan hasil pada max item 10 danMax Value 1000
31
Gambar 4.2
Pengurutan pada Max Item 10 Max Item Value = 1000
32
Gambar 4.3
Grafik perbandingan keempat pengurutan untuk Max Item 10 Max Item Value = 1000
32
Gambar 4.4
Tampilanhasilpada max item 10 danMax Item Value 1000000
33
Gambar 4.5
Hasil pengurutan pada Max item 10 dan Max Item Value 1000000
34
Gambar 4.6
Grafik perbandingan keempat pengurutan untuk Max Item 10 Max Item Value = 1000000
35
Gambar 4.7
PengurutanPada Max Item 500 Max Item Value=1000
35
Gambar 4.8
Hasil pengurutan pada Max item 500 dan Max Item Value = 1000
36
Gambar 4.9
Grafik perbandingan keempat pengurutan untuk Max Item 500 Max Item Value = 1000
37
Gambar 4.10
Pengurutan Pada Max Item 500 Max Item Value = 1000000
37
Gambar 4.11
Hasil pengurutan pada Max item 500 dan Max Item Value 1000000
38
Gambar 4.12
Grafik perbandingan keempat pengurutan untuk Max Item 500 Max Item Value = 1000000
39
Gambar 4.13
PengurutanPada Max Item 1000 Max Item Value=1000
40
Gambar 4.14
Hasil pengurutan pada Max item 1000 dan Max Item Value 1000
41
Gambar 4.15
Grafik perbandingan keempat pengurutan untuk Max Item 1000 Max Item Value = 1000
41
Gambar 4.16
PengurutanPada Max Item 1000 Max Item Value=1000000
42
Gambar 4.17
Hasil pengurutan pada Max item 1000 dan Max Item Value 1000
43
Gambar 4.18
Grafik perbandingan keempat pengurutan untuk Max Item 1000 Max Item Value = 1000
44
Universitas Sumatera Utara
