Analisis Algoritma Sorting dan Searching pada Struktur Data: Studi Efisiensi Kompleksitas Waktu dan Ruang Menggunakan Flowchart, Pseudocode dan Bahasa Javascript
PutuWidyaRusmanandaY
156 views
57 slides
Apr 05, 2025
Slide 1 of 57
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
About This Presentation
Makalah ini mmembahas mengenai analisis kompleksitas algoritma Bubble Sort, baik dari sisi waktu maupun ruang. Di dalamnya dijelaskan bagaimana algoritma ini bekerja dalam tiga skenario berbeda: best case, average case, dan worst case. Untuk setiap kasus, dijabarkan alur proses iterasi dan pertukar...
Slide Content
Analisis Algoritma Sorting dan Searching pada Struktur
Data: Studi Efisiensi Kompleksitas Waktu dan Ruang
Menggunakan Flowchart, Pseudocode dan Bahasa
Javascript
Disusun Oleh:
Putu Widya Rusmananda Yasa
2301020042
PROGRAM STUDI INFORMATIKA
FAKULTAS TEKNOLOGI INFORMASI DAN DESAIN
PRIMAKARA UNIVERSITY
2025
Data: Studi Efisiensi Kompleksitas Waktu dan Ruang
Menggunakan Flowchart, Pseudocode dan Bahasa
Javascript
Disusun Oleh:
Putu Widya Rusmananda Yasa
2301020042
PROGRAM STUDI INFORMATIKA
FAKULTAS TEKNOLOGI INFORMASI DAN DESAIN
PRIMAKARA UNIVERSITY
2025
ABSTRAK
Penelitian ini membahas analisis algoritma sorting dan searching dalam
struktur data berdasarkan efisiensi kompleksitas waktu dan ruang. Dengan
menggunakan pendekatan visual seperti flowchart dan representasi
algoritmik berupa pseudocode, penelitian ini juga mengimplementasikan
algoritma dalam bahasa pemrograman JavaScript. Tujuan dari penelitian ini
adalah untuk memahami perbedaan performa masing-masing algoritma
serta mengetahui faktor-faktor yang memengaruhi efisiensinya dalam
konteks praktikal maupun teoritis.
Algoritma sorting yang dianalisis meliputi Bubble Sort, Quick Sort, dan
Selection Sort, sedangkan algoritma searching yang dibahas adalah Linear
Search, Binary Search, dan Hash Search. Masing-masing algoritma diuji
berdasarkan skenario kasus tertentu untuk mengukur efisiensi waktu (time
complexity) dan penggunaan memori (space complexity). Hasil penelitian
menunjukkan bahwa pemilihan algoritma yang tepat sangat bergantung
pada kondisi data dan kebutuhan aplikasi. Selain itu, penggunaan flowchart
dan pseudocode terbukti mempermudah proses analisis dan pemahaman
alur kerja algoritma.
Kata kunci: Algoritma, Sorting, Searching, Kompleksitas Waktu,
Kompleksitas Ruang, Flowchart, Pseudocode, JavaScript
i
Penelitian ini membahas analisis algoritma sorting dan searching dalam
struktur data berdasarkan efisiensi kompleksitas waktu dan ruang. Dengan
menggunakan pendekatan visual seperti flowchart dan representasi
algoritmik berupa pseudocode, penelitian ini juga mengimplementasikan
algoritma dalam bahasa pemrograman JavaScript. Tujuan dari penelitian ini
adalah untuk memahami perbedaan performa masing-masing algoritma
serta mengetahui faktor-faktor yang memengaruhi efisiensinya dalam
konteks praktikal maupun teoritis.
Algoritma sorting yang dianalisis meliputi Bubble Sort, Quick Sort, dan
Selection Sort, sedangkan algoritma searching yang dibahas adalah Linear
Search, Binary Search, dan Hash Search. Masing-masing algoritma diuji
berdasarkan skenario kasus tertentu untuk mengukur efisiensi waktu (time
complexity) dan penggunaan memori (space complexity). Hasil penelitian
menunjukkan bahwa pemilihan algoritma yang tepat sangat bergantung
pada kondisi data dan kebutuhan aplikasi. Selain itu, penggunaan flowchart
dan pseudocode terbukti mempermudah proses analisis dan pemahaman
alur kerja algoritma.
Kata kunci: Algoritma, Sorting, Searching, Kompleksitas Waktu,
Kompleksitas Ruang, Flowchart, Pseudocode, JavaScript
i
KATA PENGANTAR
Puji syukur penulis panjatkan ke hadirat Tuhan Yang Maha Esa atas segala
rahmat dan karunia-Nya sehingga penulis dapat menyelesaikan karya tulis
ilmiah yang berjudul “Analisis Algoritma Sorting dan Searching pada
Struktur Data: Studi Efisiensi Kompleksitas Waktu dan Ruang
Menggunakan Flowchart, Pseudocode dan Bahasa JavaScript” dengan
lancar.
Tujuan dari penulisan karya tulis ini adalah untuk memberikan pemahaman
mendalam mengenai cara kerja dan efisiensi berbagai algoritma sorting dan
searching dalam pengolahan data, baik secara visual melalui flowchart dan
pseudocode, maupun secara praktis melalui implementasi menggunakan
bahasa pemrograman JavaScript. Penulisan ini diharapkan dapat menjadi
referensi bagi mahasiswa, akademisi, maupun praktisi yang ingin
memperdalam pengetahuan mengenai algoritma dan analisis
kompleksitasnya.
Penulis menyadari bahwa karya tulis ini masih jauh dari kesempurnaan, oleh
karena itu kritik dan saran yang membangun sangat diharapkan untuk
perbaikan di masa mendatang.
Akhir kata, semoga karya tulis ini dapat memberikan manfaat dan
menambah wawasan bagi para pembaca.
Denpasar, 2
April 2025
Penulis
ii
Puji syukur penulis panjatkan ke hadirat Tuhan Yang Maha Esa atas segala
rahmat dan karunia-Nya sehingga penulis dapat menyelesaikan karya tulis
ilmiah yang berjudul “Analisis Algoritma Sorting dan Searching pada
Struktur Data: Studi Efisiensi Kompleksitas Waktu dan Ruang
Menggunakan Flowchart, Pseudocode dan Bahasa JavaScript” dengan
lancar.
Tujuan dari penulisan karya tulis ini adalah untuk memberikan pemahaman
mendalam mengenai cara kerja dan efisiensi berbagai algoritma sorting dan
searching dalam pengolahan data, baik secara visual melalui flowchart dan
pseudocode, maupun secara praktis melalui implementasi menggunakan
bahasa pemrograman JavaScript. Penulisan ini diharapkan dapat menjadi
referensi bagi mahasiswa, akademisi, maupun praktisi yang ingin
memperdalam pengetahuan mengenai algoritma dan analisis
kompleksitasnya.
Penulis menyadari bahwa karya tulis ini masih jauh dari kesempurnaan, oleh
karena itu kritik dan saran yang membangun sangat diharapkan untuk
perbaikan di masa mendatang.
Akhir kata, semoga karya tulis ini dapat memberikan manfaat dan
menambah wawasan bagi para pembaca.
Denpasar, 2
April 2025
Penulis
ii
DAFTAR ISI
ABSTRAK.............................................................................................................i
KATA PENGANTAR ............................................................................................ii
DAFTAR ISI.......................................................................................................iii
DAFTAR TABEL..................................................................................................v
DAFTAR GAMBAR ............................................................................................vi
BAB I PENDAHULUAN ......................................................................................1
1.1 Latar Belakang...............................................................................................1
1.2 Rumusan Masalah.........................................................................................2
1.3 Tujuan Penulisan............................................................................................2
1.4 Manfaat Penulisan.........................................................................................2
1.4.1 Manfaat Teoritis...........................................................................................3
1.4.2 Manfaat Praktis............................................................................................3
BAB II TINJAUAN PUSTAKA.............................................................................4
2.1 Pengertian Algoritma....................................................................................4
2.2 Pseudocode....................................................................................................4
2.3 Flowchart..........................................................................................................4
2.4 Bahasa Pemrograman Javascript.................................................................4
2.5 Algoritma Sorting...........................................................................................4
2.5.1 Bubble Sort.....................................................................................................5
2.5.2 Quick Sort........................................................................................................5
2.5.3 Selection Sort..................................................................................................5
2.6 Algoritma Searching.......................................................................................5
2.6.1 Linear Search..................................................................................................6
2.6.2 Binary Search................................................................................................6
2.6.3 Hash Search..................................................................................................6
2.7 Kompleksitas Waktu & Ruang......................................................................7
BAB III METODE PENELITIAN..........................................................................8
3.1 Metode Pengumpulan Data.........................................................................8
iii
ABSTRAK.............................................................................................................i
KATA PENGANTAR ............................................................................................ii
DAFTAR ISI.......................................................................................................iii
DAFTAR TABEL..................................................................................................v
DAFTAR GAMBAR ............................................................................................vi
BAB I PENDAHULUAN ......................................................................................1
1.1 Latar Belakang...............................................................................................1
1.2 Rumusan Masalah.........................................................................................2
1.3 Tujuan Penulisan............................................................................................2
1.4 Manfaat Penulisan.........................................................................................2
1.4.1 Manfaat Teoritis...........................................................................................3
1.4.2 Manfaat Praktis............................................................................................3
BAB II TINJAUAN PUSTAKA.............................................................................4
2.1 Pengertian Algoritma....................................................................................4
2.2 Pseudocode....................................................................................................4
2.3 Flowchart..........................................................................................................4
2.4 Bahasa Pemrograman Javascript.................................................................4
2.5 Algoritma Sorting...........................................................................................4
2.5.1 Bubble Sort.....................................................................................................5
2.5.2 Quick Sort........................................................................................................5
2.5.3 Selection Sort..................................................................................................5
2.6 Algoritma Searching.......................................................................................5
2.6.1 Linear Search..................................................................................................6
2.6.2 Binary Search................................................................................................6
2.6.3 Hash Search..................................................................................................6
2.7 Kompleksitas Waktu & Ruang......................................................................7
BAB III METODE PENELITIAN..........................................................................8
3.1 Metode Pengumpulan Data.........................................................................8
iii
3.2 Metode Analisis Algoritma............................................................................8
BAB IV HASIL DAN PEMBAHASAN ..................................................................9
4.1 Algoritma Sorting...........................................................................................9
4.1.1 Bubble Sort.....................................................................................................9
4.1.2 Quick Sort......................................................................................................13
4.1.3 Selection Sort................................................................................................19
4.2 Algoritma Searching....................................................................................23
4.2.1 Linear Search..............................................................................................23
4.2.2 Binary Search..............................................................................................28
4.2.3 Hash Search................................................................................................34
4.3 Perbandingan Efisiensi Algoritma.............................................................38
4.3.1 Algoritma Sorting.......................................................................................38
4.3.2 Algoritma Searching..................................................................................40
BAB V KESIMPULAN DAN SARAN ..................................................................42
5.1 Kesimpulan...................................................................................................42
5.2 Saran..............................................................................................................42
iv
BAB IV HASIL DAN PEMBAHASAN ..................................................................9
4.1 Algoritma Sorting...........................................................................................9
4.1.1 Bubble Sort.....................................................................................................9
4.1.2 Quick Sort......................................................................................................13
4.1.3 Selection Sort................................................................................................19
4.2 Algoritma Searching....................................................................................23
4.2.1 Linear Search..............................................................................................23
4.2.2 Binary Search..............................................................................................28
4.2.3 Hash Search................................................................................................34
4.3 Perbandingan Efisiensi Algoritma.............................................................38
4.3.1 Algoritma Sorting.......................................................................................38
4.3.2 Algoritma Searching..................................................................................40
BAB V KESIMPULAN DAN SARAN ..................................................................42
5.1 Kesimpulan...................................................................................................42
5.2 Saran..............................................................................................................42
iv
DAFTAR TABEL
Tabel 2. 1 Perbandingan Nilai Kompleksitas Big-O Notation...............................7
Tabel 4. 1 Kompleksitas waktu dan ruang Bubble Sort.......................................11
Tabel 4. 2 Waktu eksekusi algoritma bubble sort.................................................12
Tabel 4. 3 Kompleksitas waktu dan ruang Quick Sort.........................................16
Tabel 4. 4 Waktu eksekusi algoritma Quick Sort...................................................17
Tabel 4. 5 Kompleksitas waktu dan ruang Selection Sort...................................21
Tabel 4. 6 Waktu eksekusi algoritma Quick Sort...................................................22
Tabel 4. 7 Kompleksitas waktu dan ruang Linear Search...................................26
Tabel 4. 8 Waktu eksekusi algoritma Linear Search.............................................26
Tabel 4. 9 Kompleksitas Waktu dan Ruang Binary Search..................................31
Tabel 4. 10 Waktu eksekusi algoritma Binary Search..........................................32
Tabel 4. 11 Kompleksitas waktu dan ruang Hash Search...................................37
Tabel 4. 12 Waktu eksekusi algoritma Hash Search.............................................38
Tabel 4. 13 Hasil perbandingan waktu eksekusi algoritma pengurutan.........38
Tabel 4. 14 Kelebihan dan kekurangan algoritma sorting.................................39
Tabel 4. 15 Hasil perbandingan waktu eksekusi algoritma searching.............40
Tabel 4. 16 Kelebihan dan kekurangan algoritma searching............................40
v
Tabel 2. 1 Perbandingan Nilai Kompleksitas Big-O Notation...............................7
Tabel 4. 1 Kompleksitas waktu dan ruang Bubble Sort.......................................11
Tabel 4. 2 Waktu eksekusi algoritma bubble sort.................................................12
Tabel 4. 3 Kompleksitas waktu dan ruang Quick Sort.........................................16
Tabel 4. 4 Waktu eksekusi algoritma Quick Sort...................................................17
Tabel 4. 5 Kompleksitas waktu dan ruang Selection Sort...................................21
Tabel 4. 6 Waktu eksekusi algoritma Quick Sort...................................................22
Tabel 4. 7 Kompleksitas waktu dan ruang Linear Search...................................26
Tabel 4. 8 Waktu eksekusi algoritma Linear Search.............................................26
Tabel 4. 9 Kompleksitas Waktu dan Ruang Binary Search..................................31
Tabel 4. 10 Waktu eksekusi algoritma Binary Search..........................................32
Tabel 4. 11 Kompleksitas waktu dan ruang Hash Search...................................37
Tabel 4. 12 Waktu eksekusi algoritma Hash Search.............................................38
Tabel 4. 13 Hasil perbandingan waktu eksekusi algoritma pengurutan.........38
Tabel 4. 14 Kelebihan dan kekurangan algoritma sorting.................................39
Tabel 4. 15 Hasil perbandingan waktu eksekusi algoritma searching.............40
Tabel 4. 16 Kelebihan dan kekurangan algoritma searching............................40
v
DAFTAR GAMBAR
Gambar 4. 1 Flowchart Bubble Sort...........................................................................9
Gambar 4. 2 Implementasi Bubble Sort di Javascript..........................................10
Gambar 4. 3 Grafik perbandingan waktu eksekusi algoritma bubble sort.....12
Gambar 4. 4 Flowchart Quick Sort...........................................................................14
Gambar 4. 5 Implementasi Quick Sort di Javascript.............................................15
Gambar 4. 6 Grafik perbandingan waktu eksekusi algoritma quick sort........18
Gambar 4. 7 Flowchart Selection Sort.....................................................................19
Gambar 4. 8 Implementasi Quick Sort di Javascript.............................................20
Gambar 4. 9 Grafik perbandingan waktu eksekusi algoritma selection sort.22
Gambar 4. 10 Flowchart Linear Search...................................................................23
Gambar 4. 11 Implementasi Linear Search di Javascript....................................24
Gambar 4. 12 Grafik perbandingan waktu eksekusi algoritma linear search27
Gambar 4. 13 Flowchart Binary Search...................................................................28
Gambar 4. 14 Implementasi Binary Search di Javascript....................................30
Gambar 4. 15 Grafik perbandingan waktu eksekusi algoritma binary search
.........................................................................................................................................33
Gambar 4. 16 Flowchart Hash Search.....................................................................34
Gambar 4. 17 Implementasi Hash Search di Javascript.......................................35
Gambar 4. 18 Grafik perbandingan waktu eksekusi algoritma hash search..38
vi
Gambar 4. 1 Flowchart Bubble Sort...........................................................................9
Gambar 4. 2 Implementasi Bubble Sort di Javascript..........................................10
Gambar 4. 3 Grafik perbandingan waktu eksekusi algoritma bubble sort.....12
Gambar 4. 4 Flowchart Quick Sort...........................................................................14
Gambar 4. 5 Implementasi Quick Sort di Javascript.............................................15
Gambar 4. 6 Grafik perbandingan waktu eksekusi algoritma quick sort........18
Gambar 4. 7 Flowchart Selection Sort.....................................................................19
Gambar 4. 8 Implementasi Quick Sort di Javascript.............................................20
Gambar 4. 9 Grafik perbandingan waktu eksekusi algoritma selection sort.22
Gambar 4. 10 Flowchart Linear Search...................................................................23
Gambar 4. 11 Implementasi Linear Search di Javascript....................................24
Gambar 4. 12 Grafik perbandingan waktu eksekusi algoritma linear search27
Gambar 4. 13 Flowchart Binary Search...................................................................28
Gambar 4. 14 Implementasi Binary Search di Javascript....................................30
Gambar 4. 15 Grafik perbandingan waktu eksekusi algoritma binary search
.........................................................................................................................................33
Gambar 4. 16 Flowchart Hash Search.....................................................................34
Gambar 4. 17 Implementasi Hash Search di Javascript.......................................35
Gambar 4. 18 Grafik perbandingan waktu eksekusi algoritma hash search..38
vi
BAB I
PENDAHULUAN
I.1 Latar Belakang
Dalam bidang pemrograman, algoritma merupakan rangkaian
langkah yang dirancang secara khusus untuk menyelesaikan suatu tugas.
Menemukan algoritma yang dapat memberikan solusi yang benar saja tidak
cukup, karena algoritma yang baik harus mampu menghasilkan keluaran
yang sesuai dengan masukan yang diberikan. Jika suatu algoritma tidak
menghasilkan output yang benar, maka algoritma tersebut tidak dapat
dianggap efektif, seberapa canggih pun metode yang digunakannya. Oleh
karena itu, algoritma yang berkualitas harus memiliki karakteristik yang
efisien, terstruktur dengan baik, dan tepat sasaran. Kualitas ini dapat dinilai
berdasarkan dua aspek utama, yaitu kecepatan eksekusi dan penggunaan
ruang penyimpanan. Algoritma yang efisien mampu meminimalkan
penggunaan waktu serta sumber daya memori. Untuk mengukur efisiensi
ini, digunakan konsep kompleksitas algoritma yang mencakup kompleksitas
waktu dan ruang.
Kompleksitas waktu, yang dinotasikan sebagai T(n), mengacu pada
jumlah operasi yang diperlukan untuk menjalankan algoritma berdasarkan
ukuran masukan (n). Dalam analisis ini, jumlah operasi dihitung untuk
mengetahui seberapa optimal kinerja algoritma. Untuk menyatakan
kompleksitas waktu, digunakan notasi O besar (Big-O notation). Jika suatu
algoritma memiliki kompleksitas O(f(n)), maka ketika nilai n bertambah
besar, waktu eksekusi algoritma tidak akan melebihi suatu konstanta
tertentu yang dikalikan dengan f(n). Dengan kata lain, f(n) menggambarkan
batas atas dari T(n) ketika n bernilai besar. Nilai O(n) dalam suatu algoritma
dihitung berdasarkan jumlah operasi perbandingan yang dilakukan selama
proses eksekusi. Dengan memahami kompleksitas algoritma, pengembang
dapat memilih strategi pemrograman yang lebih optimal sehingga sistem
yang dibuat dapat bekerja lebih cepat dan menggunakan sumber daya
secara efisien.
Salah satu algoritma yang sering digunakan dalam pemrograman
adalah algoritma pengurutan atau sorting. Proses pengurutan data sangat
penting dalam pengolahan data, sehingga banyak metode pengurutan telah
dikembangkan, dan kemungkinan akan terus bermunculan teknik-teknik
baru. Beberapa metode pengurutan yang umum digunakan antara lain
bubble sort, bidirectional bubble sort, selection sort, shaker sort, insertion
1
PENDAHULUAN
I.1 Latar Belakang
Dalam bidang pemrograman, algoritma merupakan rangkaian
langkah yang dirancang secara khusus untuk menyelesaikan suatu tugas.
Menemukan algoritma yang dapat memberikan solusi yang benar saja tidak
cukup, karena algoritma yang baik harus mampu menghasilkan keluaran
yang sesuai dengan masukan yang diberikan. Jika suatu algoritma tidak
menghasilkan output yang benar, maka algoritma tersebut tidak dapat
dianggap efektif, seberapa canggih pun metode yang digunakannya. Oleh
karena itu, algoritma yang berkualitas harus memiliki karakteristik yang
efisien, terstruktur dengan baik, dan tepat sasaran. Kualitas ini dapat dinilai
berdasarkan dua aspek utama, yaitu kecepatan eksekusi dan penggunaan
ruang penyimpanan. Algoritma yang efisien mampu meminimalkan
penggunaan waktu serta sumber daya memori. Untuk mengukur efisiensi
ini, digunakan konsep kompleksitas algoritma yang mencakup kompleksitas
waktu dan ruang.
Kompleksitas waktu, yang dinotasikan sebagai T(n), mengacu pada
jumlah operasi yang diperlukan untuk menjalankan algoritma berdasarkan
ukuran masukan (n). Dalam analisis ini, jumlah operasi dihitung untuk
mengetahui seberapa optimal kinerja algoritma. Untuk menyatakan
kompleksitas waktu, digunakan notasi O besar (Big-O notation). Jika suatu
algoritma memiliki kompleksitas O(f(n)), maka ketika nilai n bertambah
besar, waktu eksekusi algoritma tidak akan melebihi suatu konstanta
tertentu yang dikalikan dengan f(n). Dengan kata lain, f(n) menggambarkan
batas atas dari T(n) ketika n bernilai besar. Nilai O(n) dalam suatu algoritma
dihitung berdasarkan jumlah operasi perbandingan yang dilakukan selama
proses eksekusi. Dengan memahami kompleksitas algoritma, pengembang
dapat memilih strategi pemrograman yang lebih optimal sehingga sistem
yang dibuat dapat bekerja lebih cepat dan menggunakan sumber daya
secara efisien.
Salah satu algoritma yang sering digunakan dalam pemrograman
adalah algoritma pengurutan atau sorting. Proses pengurutan data sangat
penting dalam pengolahan data, sehingga banyak metode pengurutan telah
dikembangkan, dan kemungkinan akan terus bermunculan teknik-teknik
baru. Beberapa metode pengurutan yang umum digunakan antara lain
bubble sort, bidirectional bubble sort, selection sort, shaker sort, insertion
1
sort, inplace merge sort, double storage merge sort, comb sort, shell sort,
heap sort, exchange sort, merge sort, quick sort, quick sort with bubble sort,
enhanced quick sort, fast quick sort, radix sort, dan swap sort. Untuk
membatasi cakupan pembahasan, makalah ini akan berfokus pada tiga
metode sorting, yaitu bubble sort, quick sort, dan selection sort.
Selain pengurutan, algoritma pencarian atau searching juga
merupakan bagian penting dalam pengolahan data. Proses pencarian data
sangat krusial, sehingga berbagai metode pencarian telah dikembangkan
dan terus mengalami inovasi. Beberapa metode pencarian yang umum
digunakan antara lain linear search, binary search, sentinel linear search,
meta binary search, ternary search, jump search, interpolation search,
exponential search, fibonacci search, dan hash search. Dalam pembahasan
ini, akan difokuskan pada tiga metode utama, yaitu linear search, binary
search, dan hash search. Analisis akan dilakukan dengan menguji waktu
eksekusi dari enam algoritma yang telah disebutkan dengan menggunakan
data berupa bilangan bulat dalam bentuk list atau array yang diacak.
Masing-masing dari keenam algoritma tersebut memiliki kecepatan
eksekusi yang berbeda dalam proses pengurutan maupun pencarian data.
Untuk mengetahui kecepatan eksekusi setiap algoritma, diperlukan bahasa
pemrograman yang mendukung pengukuran ini. Dalam penelitian ini,
bahasa pemrograman yang digunakan adalah Javascript. Pemilihan
Javascript didasarkan pada sifatnya sebagai bahasa tingkat tinggi yang
sederhana, mudah dipelajari, serta mampu meningkatkan produktivitas dan
kualitas dalam pengembangan perangkat lunak.
I.2 Rumusan Masalah
1.2.1 Bagaimana analisis kecepatan tiap algoritma pengurutan
tersebut berdasarkan nilai kompleksitas waktu dan ruangnya?
1.2.2Bagaimana analisis kecepatan tiap algoritma pencarian tersebut
berdasarkan nilai kompleksitas waktu dan ruangnya?
1.2.3 Bagaimana hasil perbandingan ketiga algoritma pengurutan
tersebut? Algoritma mana yang mempunyai waktu eksekusi
tercepat dan terlama?
1.2.4 Bagaimana hasil perbandingan ketiga algoritma pencarian
tersebut? Algoritma mana yang mempunyai waktu eksekusi
tercepat dan terlama?
2
heap sort, exchange sort, merge sort, quick sort, quick sort with bubble sort,
enhanced quick sort, fast quick sort, radix sort, dan swap sort. Untuk
membatasi cakupan pembahasan, makalah ini akan berfokus pada tiga
metode sorting, yaitu bubble sort, quick sort, dan selection sort.
Selain pengurutan, algoritma pencarian atau searching juga
merupakan bagian penting dalam pengolahan data. Proses pencarian data
sangat krusial, sehingga berbagai metode pencarian telah dikembangkan
dan terus mengalami inovasi. Beberapa metode pencarian yang umum
digunakan antara lain linear search, binary search, sentinel linear search,
meta binary search, ternary search, jump search, interpolation search,
exponential search, fibonacci search, dan hash search. Dalam pembahasan
ini, akan difokuskan pada tiga metode utama, yaitu linear search, binary
search, dan hash search. Analisis akan dilakukan dengan menguji waktu
eksekusi dari enam algoritma yang telah disebutkan dengan menggunakan
data berupa bilangan bulat dalam bentuk list atau array yang diacak.
Masing-masing dari keenam algoritma tersebut memiliki kecepatan
eksekusi yang berbeda dalam proses pengurutan maupun pencarian data.
Untuk mengetahui kecepatan eksekusi setiap algoritma, diperlukan bahasa
pemrograman yang mendukung pengukuran ini. Dalam penelitian ini,
bahasa pemrograman yang digunakan adalah Javascript. Pemilihan
Javascript didasarkan pada sifatnya sebagai bahasa tingkat tinggi yang
sederhana, mudah dipelajari, serta mampu meningkatkan produktivitas dan
kualitas dalam pengembangan perangkat lunak.
I.2 Rumusan Masalah
1.2.1 Bagaimana analisis kecepatan tiap algoritma pengurutan
tersebut berdasarkan nilai kompleksitas waktu dan ruangnya?
1.2.2Bagaimana analisis kecepatan tiap algoritma pencarian tersebut
berdasarkan nilai kompleksitas waktu dan ruangnya?
1.2.3 Bagaimana hasil perbandingan ketiga algoritma pengurutan
tersebut? Algoritma mana yang mempunyai waktu eksekusi
tercepat dan terlama?
1.2.4 Bagaimana hasil perbandingan ketiga algoritma pencarian
tersebut? Algoritma mana yang mempunyai waktu eksekusi
tercepat dan terlama?
2
I.3 Tujuan Penulisan
1.3.1 Untuk mengetahui analisis kecepatan tiap algoritma pengurutan
berdasarkan nilai kompleksitas waktu dan ruangnya.
1.3.2 Untuk mengetahui analisis kecepatan tiap algoritma pencarian
berdasarkan nilai kompleksitas waktu dan ruangnya.
1.3.3Untuk mengetahui hasil perbandingan ketiga algoritma
pengurutan dan mengetahui algoritma mana yang memiliki
waktu eksekusi tercepat dan terlama.
1.3.4Untuk mengetahui hasil perbandingan ketiga algoritma
pencarian dan mengetahui algoritma mana yang memiliki waktu
eksekusi tercepat dan terlama.
I.4 Manfaat Penulisan
I.4.1 Manfaat Teoritis
Secara teoritis, hasil penelitian ini diharapkan dapat memberikan
kontribusi pemikiran yang memperluas pemahaman mengenai konsep
algoritma dalam pemrograman. Fokusnya adalah pada pemahaman
efisiensi dan kompleksitas waktu dari berbagai metode pengurutan dan
pencarian. Selain itu, penelitian ini juga bertujuan untuk memperdalam
pemahaman tentang analisis kompleksitas algoritma dengan
menggunakan notasi O besar (Big-O notation) serta menjelaskan
bagaimana ukuran data mempengaruhi kinerja algoritma dalam
pengolahan data.
I.4.2 Manfaat Praktis
Hasil penelitian ini diharapkan dapat memberikan panduan praktis
bagi pengembang perangkat lunak, mahasiswa, dan praktisi
pemrograman dalam memilih algoritma yang paling efisien untuk
pengolahan data. Dengan menganalisis perbandingan waktu eksekusi
berbagai algoritma pengurutan dan pencarian menggunakan bahasa
pemrograman Javascript, penelitian ini dapat mendukung pengambilan
keputusan terkait pemilihan algoritma yang sesuai dengan kebutuhan
sistem yang sedang dikembangkan. Selain itu, penelitian ini juga
berpotensi menjadi referensi untuk penelitian selanjutnya dalam upaya
mengembangkan algoritma yang lebih optimal di masa depan.
3
1.3.1 Untuk mengetahui analisis kecepatan tiap algoritma pengurutan
berdasarkan nilai kompleksitas waktu dan ruangnya.
1.3.2 Untuk mengetahui analisis kecepatan tiap algoritma pencarian
berdasarkan nilai kompleksitas waktu dan ruangnya.
1.3.3Untuk mengetahui hasil perbandingan ketiga algoritma
pengurutan dan mengetahui algoritma mana yang memiliki
waktu eksekusi tercepat dan terlama.
1.3.4Untuk mengetahui hasil perbandingan ketiga algoritma
pencarian dan mengetahui algoritma mana yang memiliki waktu
eksekusi tercepat dan terlama.
I.4 Manfaat Penulisan
I.4.1 Manfaat Teoritis
Secara teoritis, hasil penelitian ini diharapkan dapat memberikan
kontribusi pemikiran yang memperluas pemahaman mengenai konsep
algoritma dalam pemrograman. Fokusnya adalah pada pemahaman
efisiensi dan kompleksitas waktu dari berbagai metode pengurutan dan
pencarian. Selain itu, penelitian ini juga bertujuan untuk memperdalam
pemahaman tentang analisis kompleksitas algoritma dengan
menggunakan notasi O besar (Big-O notation) serta menjelaskan
bagaimana ukuran data mempengaruhi kinerja algoritma dalam
pengolahan data.
I.4.2 Manfaat Praktis
Hasil penelitian ini diharapkan dapat memberikan panduan praktis
bagi pengembang perangkat lunak, mahasiswa, dan praktisi
pemrograman dalam memilih algoritma yang paling efisien untuk
pengolahan data. Dengan menganalisis perbandingan waktu eksekusi
berbagai algoritma pengurutan dan pencarian menggunakan bahasa
pemrograman Javascript, penelitian ini dapat mendukung pengambilan
keputusan terkait pemilihan algoritma yang sesuai dengan kebutuhan
sistem yang sedang dikembangkan. Selain itu, penelitian ini juga
berpotensi menjadi referensi untuk penelitian selanjutnya dalam upaya
mengembangkan algoritma yang lebih optimal di masa depan.
3
BAB II
TINJAUAN PUSTAKA
II.1 Pengertian Algoritma
Algoritma adalah prosedur komputasi yang mengambil beberapa
nilai atau kumpulan nilai sebagai input kemudian di proses sebagai output
sehingga algoritma merupakan urutan langkah komputasi yang mengubah
input menjadi output.
II.2 Pseudocode
Pseudocode merupakan alat yang sangat berguna untuk merumuskan
logika suatu program komputer atau bagian penting dari program sebelum
penulisan kode dilakukan, serta untuk mendokumentasikan logika program
setelah selesai dibuat. Pseudocode dapat digunakan untuk menggambarkan
logika tingkat tinggi dari program tradisional, detail tingkat rendah dari
fungsi inti dalam sistem operasi atau pustaka waktu proses, perilaku dan
metode dalam program berbasis agen atau berorientasi objek, serta
berbagai skenario lainnya. Meskipun pseudocode sangat bermanfaat,
terdapat satu kendala: tidak seperti bahasa pemrograman yang formal atau
bahasa alami, pseudocode tidak memiliki kosakata atau tata bahasa yang
baku. Pseudocode dapat ditulis dalam hampir semua bahasa yang ada, dan
bentuknya bisa sangat mirip dengan tulisan formal yang terstruktur, tetapi
juga dapat menyerupai kode pemrograman sehingga tampak seperti
bahasa pemrograman yang sesungguhnya.
II.3 Flowchart
Flowchart atau diagram alir adalah representasi grafis dari langkah-
langkah dan urutan prosedur dalam suatu program. Flowchart membantu
analis dan programmer dalam memecah masalah menjadi segmen-segmen
yang lebih kecil serta menganalisis berbagai alternatif dalam
pengoperasiannya. Terdapat lima jenis flowchart, yaitu flowchart sistem,
flowchart paperwork, flowchart skematik, flowchart program, dan flowchart
proses.
II.4 Bahasa Pemrograman Javascript
JavaScript adalah bahasa pemrograman yang banyak digunakan
dalam pengembangan web untuk menciptakan halaman yang interaktif dan
dinamis. Sebagai salah satu pilar utama pengembangan web modern,
JavaScript memungkinkan pengembang untuk menambahkan berbagai
fitur, seperti animasi, formulir interaktif, dan elemen responsif yang
meningkatkan pengalaman pengguna. Bahasa ini pertama kali
dikembangkan oleh Brendan Eich pada tahun 1995 dan sejak saat itu telah
4
TINJAUAN PUSTAKA
II.1 Pengertian Algoritma
Algoritma adalah prosedur komputasi yang mengambil beberapa
nilai atau kumpulan nilai sebagai input kemudian di proses sebagai output
sehingga algoritma merupakan urutan langkah komputasi yang mengubah
input menjadi output.
II.2 Pseudocode
Pseudocode merupakan alat yang sangat berguna untuk merumuskan
logika suatu program komputer atau bagian penting dari program sebelum
penulisan kode dilakukan, serta untuk mendokumentasikan logika program
setelah selesai dibuat. Pseudocode dapat digunakan untuk menggambarkan
logika tingkat tinggi dari program tradisional, detail tingkat rendah dari
fungsi inti dalam sistem operasi atau pustaka waktu proses, perilaku dan
metode dalam program berbasis agen atau berorientasi objek, serta
berbagai skenario lainnya. Meskipun pseudocode sangat bermanfaat,
terdapat satu kendala: tidak seperti bahasa pemrograman yang formal atau
bahasa alami, pseudocode tidak memiliki kosakata atau tata bahasa yang
baku. Pseudocode dapat ditulis dalam hampir semua bahasa yang ada, dan
bentuknya bisa sangat mirip dengan tulisan formal yang terstruktur, tetapi
juga dapat menyerupai kode pemrograman sehingga tampak seperti
bahasa pemrograman yang sesungguhnya.
II.3 Flowchart
Flowchart atau diagram alir adalah representasi grafis dari langkah-
langkah dan urutan prosedur dalam suatu program. Flowchart membantu
analis dan programmer dalam memecah masalah menjadi segmen-segmen
yang lebih kecil serta menganalisis berbagai alternatif dalam
pengoperasiannya. Terdapat lima jenis flowchart, yaitu flowchart sistem,
flowchart paperwork, flowchart skematik, flowchart program, dan flowchart
proses.
II.4 Bahasa Pemrograman Javascript
JavaScript adalah bahasa pemrograman yang banyak digunakan
dalam pengembangan web untuk menciptakan halaman yang interaktif dan
dinamis. Sebagai salah satu pilar utama pengembangan web modern,
JavaScript memungkinkan pengembang untuk menambahkan berbagai
fitur, seperti animasi, formulir interaktif, dan elemen responsif yang
meningkatkan pengalaman pengguna. Bahasa ini pertama kali
dikembangkan oleh Brendan Eich pada tahun 1995 dan sejak saat itu telah
4
berkembang pesat, menjadi salah satu bahasa yang paling penting dalam
dunia teknologi. JavaScript dapat digunakan tidak hanya di sisi klien tetapi
juga di sisi server melalui platform seperti Node.js, menjadikannya sangat
fleksibel dan berguna untuk berbagai aplikasi, mulai dari situs web
sederhana hingga aplikasi kompleks.
II.5 Algoritma Sorting
Sorting adalah proses pengurutan sekumpulan data berdasarkan nilai
kunci tertentu. Pengurutan ini dapat dilakukan dari nilai terkecil ke terbesar
(ascending) atau sebaliknya (descending). Algoritma sorting merupakan
contoh yang memiliki banyak solusi. Dalam tulisan ini, akan dibahas tiga
algoritma sorting yang paling umum digunakan, yaitu bubble sort, quick sort,
dan selection sort. Setiap algoritma memiliki kelebihan dan kekurangan
masing-masing. Oleh karena itu, ada kecenderungan bahwa beberapa
algoritma lebih disukai dan lebih sering digunakan dibandingkan yang lain.
Faktor-faktor yang membuat suatu algoritma sering dipilih meliputi
kestabilan, kesesuaian dengan kebutuhan, kesesuaian dengan struktur data
yang digunakan, kealamian, dan efisiensi. Ukuran untuk menggambarkan
efisiensi algoritma ini dapat dinyatakan melalui kompleksitas algoritma.
II.5.1 Bubble Sort
Bubble sort adalah metode pengurutan yang membandingkan
elemen saat ini dengan elemen berikutnya. Jika elemen saat ini lebih
besar dari elemen berikutnya, maka posisi keduanya akan ditukar; jika
tidak, tidak ada pertukaran yang dilakukan. Misalnya, untuk n = 7, proses
ini akan dilakukan sebanyak (n – 1) = 6 tahap (dari 0 hingga n - 2).
Algoritma bubble sort membandingkan setiap elemen dan melakukan
penukaran jika ada elemen yang tidak berada dalam urutan yang benar.
Proses perbandingan ini akan terus berlangsung hingga tidak ada lagi
pertukaran data yang diperlukan.
II.5.2 Quick Sort
Quick Sort adalah metode pengurutan yang menggunakan
pendekatan Divide and Conquer, di mana proses dilakukan secara
bertahap untuk membagi data menjadi dua bagian yang lebih kecil.
Algoritma Quick Sort dikenal sangat efisien dibandingkan dengan
algoritma pengurutan lainnya, karena ia menyelesaikan pengurutan
dengan membagi masalah menjadi sub-masalah, dan kemudian
membagi sub-masalah tersebut menjadi sub-sub-masalah. Meskipun
Quick Sort dapat memakan ruang memori yang cukup besar, proses
pengurutannya menjadi lebih cepat.
5
dunia teknologi. JavaScript dapat digunakan tidak hanya di sisi klien tetapi
juga di sisi server melalui platform seperti Node.js, menjadikannya sangat
fleksibel dan berguna untuk berbagai aplikasi, mulai dari situs web
sederhana hingga aplikasi kompleks.
II.5 Algoritma Sorting
Sorting adalah proses pengurutan sekumpulan data berdasarkan nilai
kunci tertentu. Pengurutan ini dapat dilakukan dari nilai terkecil ke terbesar
(ascending) atau sebaliknya (descending). Algoritma sorting merupakan
contoh yang memiliki banyak solusi. Dalam tulisan ini, akan dibahas tiga
algoritma sorting yang paling umum digunakan, yaitu bubble sort, quick sort,
dan selection sort. Setiap algoritma memiliki kelebihan dan kekurangan
masing-masing. Oleh karena itu, ada kecenderungan bahwa beberapa
algoritma lebih disukai dan lebih sering digunakan dibandingkan yang lain.
Faktor-faktor yang membuat suatu algoritma sering dipilih meliputi
kestabilan, kesesuaian dengan kebutuhan, kesesuaian dengan struktur data
yang digunakan, kealamian, dan efisiensi. Ukuran untuk menggambarkan
efisiensi algoritma ini dapat dinyatakan melalui kompleksitas algoritma.
II.5.1 Bubble Sort
Bubble sort adalah metode pengurutan yang membandingkan
elemen saat ini dengan elemen berikutnya. Jika elemen saat ini lebih
besar dari elemen berikutnya, maka posisi keduanya akan ditukar; jika
tidak, tidak ada pertukaran yang dilakukan. Misalnya, untuk n = 7, proses
ini akan dilakukan sebanyak (n – 1) = 6 tahap (dari 0 hingga n - 2).
Algoritma bubble sort membandingkan setiap elemen dan melakukan
penukaran jika ada elemen yang tidak berada dalam urutan yang benar.
Proses perbandingan ini akan terus berlangsung hingga tidak ada lagi
pertukaran data yang diperlukan.
II.5.2 Quick Sort
Quick Sort adalah metode pengurutan yang menggunakan
pendekatan Divide and Conquer, di mana proses dilakukan secara
bertahap untuk membagi data menjadi dua bagian yang lebih kecil.
Algoritma Quick Sort dikenal sangat efisien dibandingkan dengan
algoritma pengurutan lainnya, karena ia menyelesaikan pengurutan
dengan membagi masalah menjadi sub-masalah, dan kemudian
membagi sub-masalah tersebut menjadi sub-sub-masalah. Meskipun
Quick Sort dapat memakan ruang memori yang cukup besar, proses
pengurutannya menjadi lebih cepat.
5
II.5.3 Selection Sort
Selection sort adalah metode pengurutan yang membandingkan
elemen saat ini dengan elemen berikutnya hingga elemen terakhir. Jika
ditemukan elemen yang lebih kecil dari elemen saat ini, maka posisi
elemen tersebut dicatat dan langsung ditukar.
Algoritma selection sort bekerja dengan memilih nilai terkecil dan
menukarnya dengan elemen pertama, kemudian melanjutkan
perbandingan antara elemen saat ini dan elemen berikutnya hingga
mencapai elemen terakhir. Proses perbandingan ini terus dilakukan
sampai tidak ada lagi pertukaran data yang diperlukan.
II.6 Algoritma Searching
Algoritma searching atau pencarian merupakan algoritma yang
digunakan untuk menemukan lokasi suatu data yang disebut kata kunci
dalam kumpulan data yang sudah ada. Setelah proses pencarian
dilakukan, hasilnya akan menunjukkan salah satu dari dua kemungkinan:
data yang dicari ditemukan atau tidak ditemukan. Terdapat dua jenis
teknik pencarian, yaitu pencarian sekuensial dan pencarian biner.
Perbedaan antara kedua teknik ini terletak pada kondisi data. Pencarian
sekuensial diterapkan ketika data berada dalam keadaan acak atau tidak
terurut, sedangkan pencarian biner digunakan untuk data yang sudah
terurut.
II.6.1 Linear Search
Algoritma Linear Search, yang juga dikenal sebagai pencarian
sekuensial, adalah metode untuk mencari elemen tertentu dalam suatu
kumpulan data dengan memeriksa setiap elemen secara berurutan
sampai elemen yang dicari ditemukan atau seluruh kumpulan data telah
ditelusuri. Algoritma ini efektif digunakan pada data yang terstruktur
maupun tidak terstruktur, meskipun efisiensi eksekusinya dapat
dipengaruhi oleh ukuran data.
Keunggulan utama dari algoritma ini adalah kesederhanaannya dan
kemudahan dalam penerapannya. Algoritma ini cocok untuk digunakan
pada data kecil atau ketika data tidak terurut. Namun, pada kumpulan
data yang sangat besar, algoritma ini mungkin menjadi kurang efisien
dibandingkan dengan algoritma pencarian lain yang menerapkan
strategi lebih canggih.
II.6.2 Binary Search
Binary Search adalah teknik pencarian data yang dilakukan dengan
cara membagi jumlah data yang dicari menjadi dua bagian secara
berulang hingga lokasi pencarian menyusut menjadi satu data. Dengan
metode ini, kita dapat mengeliminasi setengah dari jumlah data pada
6
Selection sort adalah metode pengurutan yang membandingkan
elemen saat ini dengan elemen berikutnya hingga elemen terakhir. Jika
ditemukan elemen yang lebih kecil dari elemen saat ini, maka posisi
elemen tersebut dicatat dan langsung ditukar.
Algoritma selection sort bekerja dengan memilih nilai terkecil dan
menukarnya dengan elemen pertama, kemudian melanjutkan
perbandingan antara elemen saat ini dan elemen berikutnya hingga
mencapai elemen terakhir. Proses perbandingan ini terus dilakukan
sampai tidak ada lagi pertukaran data yang diperlukan.
II.6 Algoritma Searching
Algoritma searching atau pencarian merupakan algoritma yang
digunakan untuk menemukan lokasi suatu data yang disebut kata kunci
dalam kumpulan data yang sudah ada. Setelah proses pencarian
dilakukan, hasilnya akan menunjukkan salah satu dari dua kemungkinan:
data yang dicari ditemukan atau tidak ditemukan. Terdapat dua jenis
teknik pencarian, yaitu pencarian sekuensial dan pencarian biner.
Perbedaan antara kedua teknik ini terletak pada kondisi data. Pencarian
sekuensial diterapkan ketika data berada dalam keadaan acak atau tidak
terurut, sedangkan pencarian biner digunakan untuk data yang sudah
terurut.
II.6.1 Linear Search
Algoritma Linear Search, yang juga dikenal sebagai pencarian
sekuensial, adalah metode untuk mencari elemen tertentu dalam suatu
kumpulan data dengan memeriksa setiap elemen secara berurutan
sampai elemen yang dicari ditemukan atau seluruh kumpulan data telah
ditelusuri. Algoritma ini efektif digunakan pada data yang terstruktur
maupun tidak terstruktur, meskipun efisiensi eksekusinya dapat
dipengaruhi oleh ukuran data.
Keunggulan utama dari algoritma ini adalah kesederhanaannya dan
kemudahan dalam penerapannya. Algoritma ini cocok untuk digunakan
pada data kecil atau ketika data tidak terurut. Namun, pada kumpulan
data yang sangat besar, algoritma ini mungkin menjadi kurang efisien
dibandingkan dengan algoritma pencarian lain yang menerapkan
strategi lebih canggih.
II.6.2 Binary Search
Binary Search adalah teknik pencarian data yang dilakukan dengan
cara membagi jumlah data yang dicari menjadi dua bagian secara
berulang hingga lokasi pencarian menyusut menjadi satu data. Dengan
metode ini, kita dapat mengeliminasi setengah dari jumlah data pada
6
setiap langkah. Jika ditemukan kecocokan, program akan
mengembalikan hasilnya; jika tidak, pencarian akan dilanjutkan hingga
seluruh pembagian data selesai. Algoritma ini sering digunakan dalam
program yang menangani jumlah data besar, dengan kompleksitas
algoritma sebesar O(log n), di mana n adalah jumlah item. Penting untuk
dicatat bahwa sebelum menggunakan binary search, data dalam array
harus diurutkan terlebih dahulu.
II.6.3 Hash Search
Metode pencarian Relatif (Hash Search) mirip dengan metode pencarian
langsung (Direct Search), karena keduanya menggunakan rumus tertentu
baik saat menempatkan maupun mencari data. Hash search menawarkan
efisiensi penggunaan ruang yang lebih baik dibandingkan dengan
pencarian langsung. Fungsi (I – 1) yang digunakan dalam pencarian
langsung memiliki efisiensi ruang yang rendah, sehingga pencarian
Relatif memperbaikinya dengan menerapkan fungsi operasi modulo
(mod).
Fungsi operasi modulo ini sering disebut sebagai Fungsi Hash, dan
tempat penyimpanan data dikenal sebagai Tabel Hash. Berbeda dengan
fungsi satu-satu yang digunakan dalam pencarian langsung, Fungsi Hash
tidak selalu menghasilkan nilai unik, sehingga beberapa data bisa
memiliki hasil fungsi yang sama. Hal ini dapat menyebabkan terjadinya
tabrakan (collision) saat menempatkan data dalam tabel, sehingga
diperlukan strategi untuk mengatasi masalah tersebut. Terdapat
berbagai strategi untuk menangani tabrakan, masing-masing dengan
kelebihan dan kekurangan tersendiri.
II.7 Kompleksitas Waktu & Ruang
Kebenaran suatu algoritma perlu diuji dengan sejumlah masukan
tertentu untuk mengevaluasi kinerjanya, termasuk waktu yang diperlukan
untuk menjalankan algoritma dan ruang memori yang dibutuhkan untuk
struktur datanya. Algoritma yang baik adalah yang efisien. Efisiensi
algoritma diukur berdasarkan waktu dan ruang memori yang diperlukan
untuk menjalankannya. Algoritma yang efisien adalah yang meminimalkan
kebutuhan akan waktu dan ruang.
Terdapat dua jenis kompleksitas algoritma, yaitu kompleksitas waktu
dan kompleksitas ruang. Kompleksitas waktu mengukur jumlah perhitungan
(komputasi) yang dilakukan oleh komputer saat menyelesaikan suatu
masalah menggunakan algoritma tertentu. Ukuran ini mengacu pada
7
mengembalikan hasilnya; jika tidak, pencarian akan dilanjutkan hingga
seluruh pembagian data selesai. Algoritma ini sering digunakan dalam
program yang menangani jumlah data besar, dengan kompleksitas
algoritma sebesar O(log n), di mana n adalah jumlah item. Penting untuk
dicatat bahwa sebelum menggunakan binary search, data dalam array
harus diurutkan terlebih dahulu.
II.6.3 Hash Search
Metode pencarian Relatif (Hash Search) mirip dengan metode pencarian
langsung (Direct Search), karena keduanya menggunakan rumus tertentu
baik saat menempatkan maupun mencari data. Hash search menawarkan
efisiensi penggunaan ruang yang lebih baik dibandingkan dengan
pencarian langsung. Fungsi (I – 1) yang digunakan dalam pencarian
langsung memiliki efisiensi ruang yang rendah, sehingga pencarian
Relatif memperbaikinya dengan menerapkan fungsi operasi modulo
(mod).
Fungsi operasi modulo ini sering disebut sebagai Fungsi Hash, dan
tempat penyimpanan data dikenal sebagai Tabel Hash. Berbeda dengan
fungsi satu-satu yang digunakan dalam pencarian langsung, Fungsi Hash
tidak selalu menghasilkan nilai unik, sehingga beberapa data bisa
memiliki hasil fungsi yang sama. Hal ini dapat menyebabkan terjadinya
tabrakan (collision) saat menempatkan data dalam tabel, sehingga
diperlukan strategi untuk mengatasi masalah tersebut. Terdapat
berbagai strategi untuk menangani tabrakan, masing-masing dengan
kelebihan dan kekurangan tersendiri.
II.7 Kompleksitas Waktu & Ruang
Kebenaran suatu algoritma perlu diuji dengan sejumlah masukan
tertentu untuk mengevaluasi kinerjanya, termasuk waktu yang diperlukan
untuk menjalankan algoritma dan ruang memori yang dibutuhkan untuk
struktur datanya. Algoritma yang baik adalah yang efisien. Efisiensi
algoritma diukur berdasarkan waktu dan ruang memori yang diperlukan
untuk menjalankannya. Algoritma yang efisien adalah yang meminimalkan
kebutuhan akan waktu dan ruang.
Terdapat dua jenis kompleksitas algoritma, yaitu kompleksitas waktu
dan kompleksitas ruang. Kompleksitas waktu mengukur jumlah perhitungan
(komputasi) yang dilakukan oleh komputer saat menyelesaikan suatu
masalah menggunakan algoritma tertentu. Ukuran ini mengacu pada
7
jumlah langkah perhitungan dan waktu pemrosesan yang dibutuhkan.
Kompleksitas waktu sangat penting untuk menilai efisiensi suatu algoritma.
Kompleksitas waktu dari sebuah algoritma dinyatakan sebagai fungsi dari
ukuran masalah, mencakup ekspresi numerik dan jumlah langkah yang
diperlukan sebagai fungsi dari ukuran permasalahan. Sementara itu,
kompleksitas ruang berhubungan dengan jumlah memori yang diperlukan
selama eksekusi program.
Tabel 2. 1 Perbandingan Nilai Kompleksitas Big-O Notation
Kompleksita
s
Arti Contoh Algoritma Performa
O(1) Konstan Akses array
langsung (arr[i])
Sangat cepat
O(log n) Logaritmik Binary Search Cepat
O(n) Linier Linear Search, Single
Loop
Normal
O(n log n)Lebih Cepat dari
O(n
2
)
Merge Sort, Quick
Sort
Efisien
O(n
2
) Kuadratik Bubble Sort,
Selection Sort
Lambat untuk
data besar
O(2
n
) Eksponensial Rekursi tanpa
optimasi
Sangat lambat
8
Kompleksitas waktu sangat penting untuk menilai efisiensi suatu algoritma.
Kompleksitas waktu dari sebuah algoritma dinyatakan sebagai fungsi dari
ukuran masalah, mencakup ekspresi numerik dan jumlah langkah yang
diperlukan sebagai fungsi dari ukuran permasalahan. Sementara itu,
kompleksitas ruang berhubungan dengan jumlah memori yang diperlukan
selama eksekusi program.
Tabel 2. 1 Perbandingan Nilai Kompleksitas Big-O Notation
Kompleksita
s
Arti Contoh Algoritma Performa
O(1) Konstan Akses array
langsung (arr[i])
Sangat cepat
O(log n) Logaritmik Binary Search Cepat
O(n) Linier Linear Search, Single
Loop
Normal
O(n log n)Lebih Cepat dari
O(n
2
)
Merge Sort, Quick
Sort
Efisien
O(n
2
) Kuadratik Bubble Sort,
Selection Sort
Lambat untuk
data besar
O(2
n
) Eksponensial Rekursi tanpa
optimasi
Sangat lambat
8
BAB III
METODE PENELITIAN
III.1 Metode Pengumpulan Data
Metode pengumpulan data dalam penelitian ini dilakukan dengan
memanfaatkan sumber-sumber yang tersedia di internet. Data dikumpulkan
melalui berbagai teknik, seperti pencarian informasi menggunakan mesin
pencari dan analisis konten dari artikel atau dokumen yang relevan. Semua
data yang dikumpulkan diseleksi berdasarkan relevansi dan keakuratan
untuk mendukung analisis algoritma secara optimal.
III.2 Metode Analisis Algoritma
Metode analisis algoritma dilakukan dengan menguji kinerja algoritma
menggunakan beberapa jumlah data tertentu. Proses pengujian melibatkan
penerapan algoritma sorting dan searching pada dataset dengan ukuran
yang bervariasi untuk mengukur waktu eksekusi dan efisiensi memori yang
digunakan. Pengujian dilakukan secara berulang untuk memastikan hasil
yang konsisten, serta mencatat kompleksitas waktu (time complexity) dan
ruang (space complexity) dari setiap algoritma. Hasil pengujian ini kemudian
dianalisis untuk menentukan algoritma yang paling efisien berdasarkan
kebutuhan sistem yang ditentukan.
9
METODE PENELITIAN
III.1 Metode Pengumpulan Data
Metode pengumpulan data dalam penelitian ini dilakukan dengan
memanfaatkan sumber-sumber yang tersedia di internet. Data dikumpulkan
melalui berbagai teknik, seperti pencarian informasi menggunakan mesin
pencari dan analisis konten dari artikel atau dokumen yang relevan. Semua
data yang dikumpulkan diseleksi berdasarkan relevansi dan keakuratan
untuk mendukung analisis algoritma secara optimal.
III.2 Metode Analisis Algoritma
Metode analisis algoritma dilakukan dengan menguji kinerja algoritma
menggunakan beberapa jumlah data tertentu. Proses pengujian melibatkan
penerapan algoritma sorting dan searching pada dataset dengan ukuran
yang bervariasi untuk mengukur waktu eksekusi dan efisiensi memori yang
digunakan. Pengujian dilakukan secara berulang untuk memastikan hasil
yang konsisten, serta mencatat kompleksitas waktu (time complexity) dan
ruang (space complexity) dari setiap algoritma. Hasil pengujian ini kemudian
dianalisis untuk menentukan algoritma yang paling efisien berdasarkan
kebutuhan sistem yang ditentukan.
9
BAB IV
HASIL DAN PEMBAHASAN
IV.1 Algoritma Sorting
IV.1.1 Bubble Sort
a)Flowchart Bubble Sort
Gambar 4. 1 Flowchart Bubble Sort
b)Pseudocode Bubble Sort
BUBBLE_SORT(array, n)
for i from 0 to n-1 do
for j from 0 to n-1-i do
10
HASIL DAN PEMBAHASAN
IV.1 Algoritma Sorting
IV.1.1 Bubble Sort
a)Flowchart Bubble Sort
Gambar 4. 1 Flowchart Bubble Sort
b)Pseudocode Bubble Sort
BUBBLE_SORT(array, n)
for i from 0 to n-1 do
for j from 0 to n-1-i do
10
if array[j] > array[j+1] then
SWAP(array[j], array[j+1])
end for
if swapped = false then
break
end for
END
c)Implementasi Bubble Sort
Gambar 4. 2 Implementasi Bubble Sort di Javascript
d)Kompleksitas Bubble Sort
Kompleksitas Bubble Sort dapat dianalisis berdasarkan tiga
kondisi utama, yaitu kasus terbaik (best-case), kasus rata-rata
(average-case), dan kasus terburuk (worst-case).
Pada kasus terbaik, data sudah tersusun dengan benar
sebelumnya, sehingga Bubble Sort hanya memerlukan (n-1)
perbandingan dalam satu iterasi tanpa adanya pertukaran elemen.
Karena tidak ada proses pertukaran, kompleksitas waktu menjadi
O(n), yang berarti algoritma berjalan secara linier.
11
SWAP(array[j], array[j+1])
end for
if swapped = false then
break
end for
END
c)Implementasi Bubble Sort
Gambar 4. 2 Implementasi Bubble Sort di Javascript
d)Kompleksitas Bubble Sort
Kompleksitas Bubble Sort dapat dianalisis berdasarkan tiga
kondisi utama, yaitu kasus terbaik (best-case), kasus rata-rata
(average-case), dan kasus terburuk (worst-case).
Pada kasus terbaik, data sudah tersusun dengan benar
sebelumnya, sehingga Bubble Sort hanya memerlukan (n-1)
perbandingan dalam satu iterasi tanpa adanya pertukaran elemen.
Karena tidak ada proses pertukaran, kompleksitas waktu menjadi
O(n), yang berarti algoritma berjalan secara linier.
11
Pada kasus terburuk, data berada dalam kondisi benar-benar
tidak terurut, dengan elemen terkecil berada di posisi terakhir dalam
array. Dalam situasi ini, setiap iterasi hanya akan memindahkan satu
elemen terkecil ke posisi yang benar. Misalnya, jika elemen terkecil
berada di urutan keempat dan harus dipindahkan ke posisi pertama,
maka diperlukan tiga iterasi untuk memindahkannya, ditambah satu
iterasi tambahan untuk memastikan seluruh data sudah terurut.
Dalam kondisi ini, jumlah total proses dapat dirumuskan sebagai n² +
n, sehingga kompleksitasnya adalah O(n²).
Pada kasus rata-rata, jumlah iterasi yang dibutuhkan
bergantung pada jumlah elemen yang perlu dipindahkan ke posisi
yang benar. Secara umum, jumlah perbandingan dapat dirumuskan
sebagai x² + x, yang menghasilkan kompleksitas waktu O(n²).
Selain kompleksitas waktu, algoritma ini juga memiliki
kompleksitas ruang (space complexity), yang mengukur penggunaan
memori tambahan selama eksekusi. Karena proses pengurutan
dilakukan langsung pada array tanpa menggunakan array tambahan
(in-place sorting), kompleksitas ruangnya adalah O(1), yang berarti
penggunaan memori tetap konstan meskipun ukuran data
bertambah.
Dengan demikian, Bubble Sort memiliki kompleksitas waktu
O(n) pada best-case (data sudah terurut), O(n²) pada average-case
(data acak), O(n²) pada worst-case (data terbalik urutannya), dan
kompleksitas ruang O(1).
Tabel 4. 1 Kompleksitas waktu dan ruang Bubble Sort
Jenis Kompleksitas Nilai Penjelasan
Waktu (Best-Case) O(n) Jika array sudah terurut, hanya
perlu satu iterasi.
Waktu (Worst-Case) O(n²) Jika array acak, butuh banyak
perbandingan dan pertukaran.
Waktu (Average-Case) O(n²) Jika array dalam urutan terbalik,
setiap elemen harus ditukar.
Ruang (Space
Complexity)
O(1) Tidak menggunakan array
tambahan, hanya beberapa
variabel.
e)Analisa Bubble Sort
Bubble sort adalah salah satu algoritma pengurutan tertua
dan paling sederhana untuk diimplementasikan. Algoritma ini juga
12
tidak terurut, dengan elemen terkecil berada di posisi terakhir dalam
array. Dalam situasi ini, setiap iterasi hanya akan memindahkan satu
elemen terkecil ke posisi yang benar. Misalnya, jika elemen terkecil
berada di urutan keempat dan harus dipindahkan ke posisi pertama,
maka diperlukan tiga iterasi untuk memindahkannya, ditambah satu
iterasi tambahan untuk memastikan seluruh data sudah terurut.
Dalam kondisi ini, jumlah total proses dapat dirumuskan sebagai n² +
n, sehingga kompleksitasnya adalah O(n²).
Pada kasus rata-rata, jumlah iterasi yang dibutuhkan
bergantung pada jumlah elemen yang perlu dipindahkan ke posisi
yang benar. Secara umum, jumlah perbandingan dapat dirumuskan
sebagai x² + x, yang menghasilkan kompleksitas waktu O(n²).
Selain kompleksitas waktu, algoritma ini juga memiliki
kompleksitas ruang (space complexity), yang mengukur penggunaan
memori tambahan selama eksekusi. Karena proses pengurutan
dilakukan langsung pada array tanpa menggunakan array tambahan
(in-place sorting), kompleksitas ruangnya adalah O(1), yang berarti
penggunaan memori tetap konstan meskipun ukuran data
bertambah.
Dengan demikian, Bubble Sort memiliki kompleksitas waktu
O(n) pada best-case (data sudah terurut), O(n²) pada average-case
(data acak), O(n²) pada worst-case (data terbalik urutannya), dan
kompleksitas ruang O(1).
Tabel 4. 1 Kompleksitas waktu dan ruang Bubble Sort
Jenis Kompleksitas Nilai Penjelasan
Waktu (Best-Case) O(n) Jika array sudah terurut, hanya
perlu satu iterasi.
Waktu (Worst-Case) O(n²) Jika array acak, butuh banyak
perbandingan dan pertukaran.
Waktu (Average-Case) O(n²) Jika array dalam urutan terbalik,
setiap elemen harus ditukar.
Ruang (Space
Complexity)
O(1) Tidak menggunakan array
tambahan, hanya beberapa
variabel.
e)Analisa Bubble Sort
Bubble sort adalah salah satu algoritma pengurutan tertua
dan paling sederhana untuk diimplementasikan. Algoritma ini juga
12
mudah dipahami. Cara kerjanya adalah dengan membandingkan
nilai setiap elemen dalam tabel dengan elemen berikutnya, lalu
menukar posisinya jika memenuhi kondisi tertentu. Proses ini
dilakukan secara berulang hingga semua elemen dalam tabel terurut
dengan benar. Namun, bubble sort dikenal sebagai algoritma yang
paling lambat dan kurang efisien dibandingkan algoritma
pengurutan lainnya untuk penggunaan umum.
Dalam kasus terbaik, ketika daftar sudah terurut, kompleksitas
algoritma ini adalah O(n). Sementara itu, untuk kasus umum,
kompleksitasnya menjadi O(n²). Pengujian dilakukan dengan
menggunakan data berukuran antara 100 hingga 1.000 elemen,
dengan proses pengulangan hingga 100 kali untuk mendapatkan
rata-rata hasilnya. Waktu eksekusi diukur dalam satuan milidetik
(ms).
Tabel 4. 2 Waktu eksekusi algoritma bubble sort
Jumlah Elemen ArrayWaktu (ms)
100 0.658
250 3.788
500 8.581
750 9.629
1.000 11.561
13
nilai setiap elemen dalam tabel dengan elemen berikutnya, lalu
menukar posisinya jika memenuhi kondisi tertentu. Proses ini
dilakukan secara berulang hingga semua elemen dalam tabel terurut
dengan benar. Namun, bubble sort dikenal sebagai algoritma yang
paling lambat dan kurang efisien dibandingkan algoritma
pengurutan lainnya untuk penggunaan umum.
Dalam kasus terbaik, ketika daftar sudah terurut, kompleksitas
algoritma ini adalah O(n). Sementara itu, untuk kasus umum,
kompleksitasnya menjadi O(n²). Pengujian dilakukan dengan
menggunakan data berukuran antara 100 hingga 1.000 elemen,
dengan proses pengulangan hingga 100 kali untuk mendapatkan
rata-rata hasilnya. Waktu eksekusi diukur dalam satuan milidetik
(ms).
Tabel 4. 2 Waktu eksekusi algoritma bubble sort
Jumlah Elemen ArrayWaktu (ms)
100 0.658
250 3.788
500 8.581
750 9.629
1.000 11.561
13
Gambar 4. 3 Grafik perbandingan waktu eksekusi algoritma bubble sort
IV.1.2 Quick Sort
a)Flowchart Quick Sort
14
IV.1.2 Quick Sort
a)Flowchart Quick Sort
14
Gambar 4. 4 Flowchart Quick Sort
b)Pseudocode Quick Sort
QUICK_SORT(array, low, high)
if low < high then
15
b)Pseudocode Quick Sort
QUICK_SORT(array, low, high)
if low < high then
15
pivotIndex ← PARTITION(array, low, high)
QUICK_SORT(array, low, pivotIndex - 1)
QUICK_SORT(array, pivotIndex + 1, high)
end if
END
PARTITION(array, low, high)
pivot ← array[high]
i ← low - 1
for j from low to high - 1 do
if array[j] < pivot then
i ← i + 1
SWAP(array[i], array[j])
end for
SWAP(array[i + 1], array[high])
return i + 1
END
c)Implementasi Quick Sort
16
QUICK_SORT(array, low, pivotIndex - 1)
QUICK_SORT(array, pivotIndex + 1, high)
end if
END
PARTITION(array, low, high)
pivot ← array[high]
i ← low - 1
for j from low to high - 1 do
if array[j] < pivot then
i ← i + 1
SWAP(array[i], array[j])
end for
SWAP(array[i + 1], array[high])
return i + 1
END
c)Implementasi Quick Sort
16
Gambar 4. 5 Implementasi Quick Sort di Javascript
d)Kompleksitas Quick Sort
Kompleksitas Quick Sort dapat dianalisis berdasarkan tiga
skenario utama, yaitu kasus terbaik (best-case), kasus rata-rata
(average-case), dan kasus terburuk (worst-case).
Pada kasus terbaik, pemilihan pivot selalu membagi array
menjadi dua bagian yang sama besar di setiap langkah rekursi.
Dengan demikian, ukuran array akan terus dibagi dua hingga tersisa
satu elemen. Dalam kondisi ini, jumlah pembagian dan
penggabungan yang dilakukan menghasilkan kompleksitas O(n log
n), karena terdapat log n tingkat rekursi, dengan setiap tingkat
memproses n elemen.
Pada kasus terburuk, pemilihan pivot tidak optimal, misalnya
ketika pivot selalu berupa elemen terbesar atau terkecil dalam array.
Hal ini menyebabkan array terbagi menjadi satu bagian besar (n-1
elemen) dan satu bagian kecil (0 elemen), sehingga pembagian tidak
seimbang. Dalam kondisi ini, Quick Sort berfungsi serupa dengan
Bubble Sort, di mana setiap iterasi hanya menghilangkan satu
elemen dari daftar yang belum terurut. Akibatnya, jumlah total
proses dapat dirumuskan sebagai n² + n, yang menghasilkan
kompleksitas O(n²).
Pada kasus rata-rata, Quick Sort biasanya membagi array
menjadi dua bagian yang cukup seimbang meskipun tidak selalu
tepat di tengah. Dalam kondisi ini, jumlah operasi tetap berada
dalam O(n log n), karena rata-rata tingkat rekursi tetap log n dengan
setiap tingkat melakukan operasi sebanyak n.
Selain kompleksitas waktu, Quick Sort juga memiliki
kompleksitas ruang (space complexity), yang mengukur memori
tambahan yang dibutuhkan selama eksekusi. Karena Quick Sort
adalah algoritma in-place, proses sorting dilakukan langsung pada
array tanpa memerlukan array tambahan. Namun, penggunaan
rekursi memerlukan memori tambahan untuk stack rekursi, yang
dalam kondisi umum memiliki kompleksitas O(log n). Ini berarti
kebutuhan memori bertambah secara logaritmik terhadap ukuran
data (n).
Dengan demikian, Quick Sort memiliki kompleksitas O(n log n)
pada best-case (jika pivot membagi array secara merata), O(n log n)
pada average-case (pembagian cukup seimbang), O(n²) pada worst-
case (jika pivot selalu memilih elemen terbesar atau terkecil), dan
kompleksitas ruang O(log n).
Tabel 4. 3 Kompleksitas waktu dan ruang Quick Sort
17
d)Kompleksitas Quick Sort
Kompleksitas Quick Sort dapat dianalisis berdasarkan tiga
skenario utama, yaitu kasus terbaik (best-case), kasus rata-rata
(average-case), dan kasus terburuk (worst-case).
Pada kasus terbaik, pemilihan pivot selalu membagi array
menjadi dua bagian yang sama besar di setiap langkah rekursi.
Dengan demikian, ukuran array akan terus dibagi dua hingga tersisa
satu elemen. Dalam kondisi ini, jumlah pembagian dan
penggabungan yang dilakukan menghasilkan kompleksitas O(n log
n), karena terdapat log n tingkat rekursi, dengan setiap tingkat
memproses n elemen.
Pada kasus terburuk, pemilihan pivot tidak optimal, misalnya
ketika pivot selalu berupa elemen terbesar atau terkecil dalam array.
Hal ini menyebabkan array terbagi menjadi satu bagian besar (n-1
elemen) dan satu bagian kecil (0 elemen), sehingga pembagian tidak
seimbang. Dalam kondisi ini, Quick Sort berfungsi serupa dengan
Bubble Sort, di mana setiap iterasi hanya menghilangkan satu
elemen dari daftar yang belum terurut. Akibatnya, jumlah total
proses dapat dirumuskan sebagai n² + n, yang menghasilkan
kompleksitas O(n²).
Pada kasus rata-rata, Quick Sort biasanya membagi array
menjadi dua bagian yang cukup seimbang meskipun tidak selalu
tepat di tengah. Dalam kondisi ini, jumlah operasi tetap berada
dalam O(n log n), karena rata-rata tingkat rekursi tetap log n dengan
setiap tingkat melakukan operasi sebanyak n.
Selain kompleksitas waktu, Quick Sort juga memiliki
kompleksitas ruang (space complexity), yang mengukur memori
tambahan yang dibutuhkan selama eksekusi. Karena Quick Sort
adalah algoritma in-place, proses sorting dilakukan langsung pada
array tanpa memerlukan array tambahan. Namun, penggunaan
rekursi memerlukan memori tambahan untuk stack rekursi, yang
dalam kondisi umum memiliki kompleksitas O(log n). Ini berarti
kebutuhan memori bertambah secara logaritmik terhadap ukuran
data (n).
Dengan demikian, Quick Sort memiliki kompleksitas O(n log n)
pada best-case (jika pivot membagi array secara merata), O(n log n)
pada average-case (pembagian cukup seimbang), O(n²) pada worst-
case (jika pivot selalu memilih elemen terbesar atau terkecil), dan
kompleksitas ruang O(log n).
Tabel 4. 3 Kompleksitas waktu dan ruang Quick Sort
17
Jenis Kompleksitas Nilai Penjelasan
Waktu (Best-Case) O(n x log
n)
Jika pivot selalu membagi array
secara merata, jumlah rekursi
logaritmik.
Waktu (Worst-Case) O(n²) Jika pivot selalu dipilih buruk
(elemen terbesar/terkecil),
rekursi berjalan hingga n
tingkat.
Waktu (Average-Case) O(n x log
n)
Pembagian elemen cukup
seimbang, menghasilkan
rekursi logaritmik.
Ruang (Space
Complexity)
O(log n) Sorting dilakukan secara in-
place, tetapi menggunakan
memori tambahan untuk stack
rekursi.
e)Analisa Quick Sort
Quick Sort merupakan salah satu algoritma pengurutan yang
sangat efisien dan sering digunakan dalam berbagai aplikasi.
Algoritma ini menggunakan pendekatan divide and conquer, di mana
data dibagi menjadi dua bagian berdasarkan elemen pivot, sehingga
proses pengurutan dapat dilakukan dengan lebih cepat
dibandingkan metode lainnya, seperti Bubble Sort. Cara kerja Quick
Sort adalah dengan memilih elemen pivot, lalu membagi elemen
lainnya menjadi dua kelompok: elemen yang lebih kecil dari pivot dan
elemen yang lebih besar dari pivot. Proses ini dilakukan secara
rekursif hingga semua elemen dalam tabel terurut.
Quick Sort dikenal sebagai algoritma pengurutan yang sangat cepat
dalam sebagian besar kasus. Pada kasus terbaik dan rata-rata,
kompleksitas algoritma ini adalah O(n log n), menjadikannya jauh
lebih efisien dibandingkan algoritma lain seperti Bubble Sort dan
Selection Sort. Namun, pada kasus terburuk, ketika pemilihan pivot
tidak optimal (misalnya selalu memilih elemen terbesar atau terkecil),
kompleksitasnya dapat meningkat menjadi O(n²).
Dengan menggunakan data berukuran antara 100 hingga
1.000 elemen dan mengulangi proses hingga 100 kali untuk
mendapatkan rata-rata waktu eksekusi, performa Quick Sort dapat
diukur dengan lebih akurat. Waktu eksekusi dihitung dalam satuan
milidetik (ms) untuk menunjukkan efisiensi algoritma dalam
menangani berbagai ukuran data.
Tabel 4. 4 Waktu eksekusi algoritma Quick Sort
18
Waktu (Best-Case) O(n x log
n)
Jika pivot selalu membagi array
secara merata, jumlah rekursi
logaritmik.
Waktu (Worst-Case) O(n²) Jika pivot selalu dipilih buruk
(elemen terbesar/terkecil),
rekursi berjalan hingga n
tingkat.
Waktu (Average-Case) O(n x log
n)
Pembagian elemen cukup
seimbang, menghasilkan
rekursi logaritmik.
Ruang (Space
Complexity)
O(log n) Sorting dilakukan secara in-
place, tetapi menggunakan
memori tambahan untuk stack
rekursi.
e)Analisa Quick Sort
Quick Sort merupakan salah satu algoritma pengurutan yang
sangat efisien dan sering digunakan dalam berbagai aplikasi.
Algoritma ini menggunakan pendekatan divide and conquer, di mana
data dibagi menjadi dua bagian berdasarkan elemen pivot, sehingga
proses pengurutan dapat dilakukan dengan lebih cepat
dibandingkan metode lainnya, seperti Bubble Sort. Cara kerja Quick
Sort adalah dengan memilih elemen pivot, lalu membagi elemen
lainnya menjadi dua kelompok: elemen yang lebih kecil dari pivot dan
elemen yang lebih besar dari pivot. Proses ini dilakukan secara
rekursif hingga semua elemen dalam tabel terurut.
Quick Sort dikenal sebagai algoritma pengurutan yang sangat cepat
dalam sebagian besar kasus. Pada kasus terbaik dan rata-rata,
kompleksitas algoritma ini adalah O(n log n), menjadikannya jauh
lebih efisien dibandingkan algoritma lain seperti Bubble Sort dan
Selection Sort. Namun, pada kasus terburuk, ketika pemilihan pivot
tidak optimal (misalnya selalu memilih elemen terbesar atau terkecil),
kompleksitasnya dapat meningkat menjadi O(n²).
Dengan menggunakan data berukuran antara 100 hingga
1.000 elemen dan mengulangi proses hingga 100 kali untuk
mendapatkan rata-rata waktu eksekusi, performa Quick Sort dapat
diukur dengan lebih akurat. Waktu eksekusi dihitung dalam satuan
milidetik (ms) untuk menunjukkan efisiensi algoritma dalam
menangani berbagai ukuran data.
Tabel 4. 4 Waktu eksekusi algoritma Quick Sort
18
Jumlah Elemen ArrayWaktu (ms)
100 0.173
250 0.467
500 0.603
750 1.296
1.000 1.384
Gambar 4. 6 Grafik perbandingan waktu eksekusi algoritma quick sort
19
100 0.173
250 0.467
500 0.603
750 1.296
1.000 1.384
Gambar 4. 6 Grafik perbandingan waktu eksekusi algoritma quick sort
19
IV.1.3 Selection Sort
a)Flowchart Selection Sort
20
a)Flowchart Selection Sort
20
Gambar 4. 7 Flowchart Selection Sort
b)Pseudocode Selection Sort
21
b)Pseudocode Selection Sort
21
SELECTION_SORT(array, n)
for i from 0 to n-1 do
minIndex ← i
for j from i+1 to n-1 do
if array[j] < array[minIndex] then
minIndex ← j
end for
SWAP(array[i], array[minIndex])
end for
END
c)Implementasi Selection Sort
Gambar 4. 8 Implementasi Quick Sort di Javascript
d)Kompleksitas Selection Sort
22
for i from 0 to n-1 do
minIndex ← i
for j from i+1 to n-1 do
if array[j] < array[minIndex] then
minIndex ← j
end for
SWAP(array[i], array[minIndex])
end for
END
c)Implementasi Selection Sort
Gambar 4. 8 Implementasi Quick Sort di Javascript
d)Kompleksitas Selection Sort
22
Kompleksitas Selection Sort dapat dianalisis berdasarkan tiga
kondisi utama, yaitu kasus terbaik (best-case), kasus rata-rata
(average-case), dan kasus terburuk (worst-case).
Pada kasus terbaik, meskipun data sudah terurut sebelumnya,
algoritma tetap harus mencari elemen terkecil di setiap iterasi untuk
memastikan urutan tetap benar. Dalam kondisi ini, proses
perbandingan tetap dilakukan sebanyak n² kali, meskipun jumlah
pertukaran elemen lebih sedikit dibandingkan kondisi lainnya. Oleh
karena itu, kompleksitasnya tetap O(n²).
Pada kasus terburuk, ketika data benar-benar tidak terurut
dengan elemen terkecil berada di akhir array, algoritma akan tetap
mencari elemen terkecil di setiap iterasi dan menempatkannya di
posisi yang benar. Karena jumlah perbandingan yang dilakukan
selalu n² terlepas dari kondisi array, kompleksitasnya tetap O(n²).
Pada kasus rata-rata, Selection Sort bekerja dengan cara yang
sama seperti pada kasus terbaik dan terburuk. Jumlah perbandingan
yang dilakukan tidak berubah, karena algoritma selalu mencari
elemen terkecil di setiap iterasi. Dengan demikian, jumlah total
perbandingan menghasilkan kompleksitas waktu O(n²).
Selain kompleksitas waktu, Selection Sort juga memiliki
kompleksitas ruang (space complexity), yang menunjukkan
penggunaan memori tambahan selama eksekusi. Karena algoritma
ini merupakan in-place sorting, proses pengurutan dilakukan
langsung pada array tanpa memerlukan array tambahan. Hanya
beberapa variabel sementara yang digunakan untuk menyimpan
indeks dan nilai selama pertukaran elemen. Oleh sebab itu,
kompleksitas ruangnya adalah O(1), yang berarti penggunaan
memori tetap konstan meskipun ukuran data bertambah.
Dengan demikian, Selection Sort memiliki kompleksitas O(n²)
pada best-case (data sudah terurut), average-case (data acak), dan
worst-case (data terbalik urutannya), serta kompleksitas ruang O(1).
Tabel 4. 5 Kompleksitas waktu dan ruang Selection Sort
Jenis Kompleksitas Nilai Penjelasan
Waktu (Best-Case) O(n²) Meskipun data sudah terurut,
algoritma tetap melakukan
perbandingan sebanyak n².
Waktu (Worst-Case) O(n²) Dalam kondisi acak, algoritma
23
kondisi utama, yaitu kasus terbaik (best-case), kasus rata-rata
(average-case), dan kasus terburuk (worst-case).
Pada kasus terbaik, meskipun data sudah terurut sebelumnya,
algoritma tetap harus mencari elemen terkecil di setiap iterasi untuk
memastikan urutan tetap benar. Dalam kondisi ini, proses
perbandingan tetap dilakukan sebanyak n² kali, meskipun jumlah
pertukaran elemen lebih sedikit dibandingkan kondisi lainnya. Oleh
karena itu, kompleksitasnya tetap O(n²).
Pada kasus terburuk, ketika data benar-benar tidak terurut
dengan elemen terkecil berada di akhir array, algoritma akan tetap
mencari elemen terkecil di setiap iterasi dan menempatkannya di
posisi yang benar. Karena jumlah perbandingan yang dilakukan
selalu n² terlepas dari kondisi array, kompleksitasnya tetap O(n²).
Pada kasus rata-rata, Selection Sort bekerja dengan cara yang
sama seperti pada kasus terbaik dan terburuk. Jumlah perbandingan
yang dilakukan tidak berubah, karena algoritma selalu mencari
elemen terkecil di setiap iterasi. Dengan demikian, jumlah total
perbandingan menghasilkan kompleksitas waktu O(n²).
Selain kompleksitas waktu, Selection Sort juga memiliki
kompleksitas ruang (space complexity), yang menunjukkan
penggunaan memori tambahan selama eksekusi. Karena algoritma
ini merupakan in-place sorting, proses pengurutan dilakukan
langsung pada array tanpa memerlukan array tambahan. Hanya
beberapa variabel sementara yang digunakan untuk menyimpan
indeks dan nilai selama pertukaran elemen. Oleh sebab itu,
kompleksitas ruangnya adalah O(1), yang berarti penggunaan
memori tetap konstan meskipun ukuran data bertambah.
Dengan demikian, Selection Sort memiliki kompleksitas O(n²)
pada best-case (data sudah terurut), average-case (data acak), dan
worst-case (data terbalik urutannya), serta kompleksitas ruang O(1).
Tabel 4. 5 Kompleksitas waktu dan ruang Selection Sort
Jenis Kompleksitas Nilai Penjelasan
Waktu (Best-Case) O(n²) Meskipun data sudah terurut,
algoritma tetap melakukan
perbandingan sebanyak n².
Waktu (Worst-Case) O(n²) Dalam kondisi acak, algoritma
23
tetap mencari elemen terkecil
di setiap iterasi.
Waktu (Average-Case) O(n²) Jika data dalam urutan terbalik,
jumlah perbandingan dan
pertukaran tetap n².
Ruang (Space
Complexity)
O(1) Sorting dilakukan secara in-
place tanpa menggunakan
array tambahan.
e)Analisa Selection Sort
Selection Sort merupakan algoritma pengurutan sederhana yang
mudah dipahami dan diimplementasikan. Algoritma ini bekerja
dengan cara menemukan elemen terkecil dalam daftar dan
menempatkannya di posisi yang sesuai. Proses ini dilakukan secara
berulang untuk setiap elemen hingga seluruh daftar terurut.
Meskipun algoritma ini memiliki keunggulan berupa jumlah
pertukaran elemen yang lebih sedikit dibandingkan dengan Bubble
Sort, kompleksitas waktu dalam kasus umum tetap O(n²), sehingga
kurang efisien untuk dataset berukuran besar. Bahkan dalam kasus
terbaik, ketika data sudah terurut, algoritma tetap memerlukan O(n²)
operasi perbandingan karena semua elemen harus diperiksa.
Dengan menggunakan data berukuran antara 100 hingga 1.000
elemen dan pengulangan proses hingga 100 kali untuk mendapatkan
rata-rata waktu eksekusi, performa Selection Sort dapat dianalisis
dengan lebih akurat. Waktu eksekusi diukur dalam satuan milidetik
(ms) untuk menilai efisiensi algoritma dalam mengolah berbagai
ukuran data.
Tabel 4. 6 Waktu eksekusi algoritma Quick Sort
Jumlah Elemen ArrayWaktu (ms)
100 0.302
250 0.643
500 1.221
750 1.501
1.000 2.692
24
di setiap iterasi.
Waktu (Average-Case) O(n²) Jika data dalam urutan terbalik,
jumlah perbandingan dan
pertukaran tetap n².
Ruang (Space
Complexity)
O(1) Sorting dilakukan secara in-
place tanpa menggunakan
array tambahan.
e)Analisa Selection Sort
Selection Sort merupakan algoritma pengurutan sederhana yang
mudah dipahami dan diimplementasikan. Algoritma ini bekerja
dengan cara menemukan elemen terkecil dalam daftar dan
menempatkannya di posisi yang sesuai. Proses ini dilakukan secara
berulang untuk setiap elemen hingga seluruh daftar terurut.
Meskipun algoritma ini memiliki keunggulan berupa jumlah
pertukaran elemen yang lebih sedikit dibandingkan dengan Bubble
Sort, kompleksitas waktu dalam kasus umum tetap O(n²), sehingga
kurang efisien untuk dataset berukuran besar. Bahkan dalam kasus
terbaik, ketika data sudah terurut, algoritma tetap memerlukan O(n²)
operasi perbandingan karena semua elemen harus diperiksa.
Dengan menggunakan data berukuran antara 100 hingga 1.000
elemen dan pengulangan proses hingga 100 kali untuk mendapatkan
rata-rata waktu eksekusi, performa Selection Sort dapat dianalisis
dengan lebih akurat. Waktu eksekusi diukur dalam satuan milidetik
(ms) untuk menilai efisiensi algoritma dalam mengolah berbagai
ukuran data.
Tabel 4. 6 Waktu eksekusi algoritma Quick Sort
Jumlah Elemen ArrayWaktu (ms)
100 0.302
250 0.643
500 1.221
750 1.501
1.000 2.692
24
Gambar 4. 9 Grafik perbandingan waktu eksekusi algoritma selection sort
IV.2 Algoritma Searching
IV.2.1 Linear Search
a)Flowchart Linear Search
25
IV.2 Algoritma Searching
IV.2.1 Linear Search
a)Flowchart Linear Search
25
Gambar 4. 10 Flowchart Linear Search
b)Pseudocode Linear Search
LINEAR_SEARCH(array, n, target)
26
b)Pseudocode Linear Search
LINEAR_SEARCH(array, n, target)
26
for i from 0 to n-1 do
if array[i] = target then
return “key found”
end for
return “key not found”
END
c)Implementasi Linear Search
Gambar 4. 11 Implementasi Linear Search di Javascript
27
if array[i] = target then
return “key found”
end for
return “key not found”
END
c)Implementasi Linear Search
Gambar 4. 11 Implementasi Linear Search di Javascript
27
d)Kompleksitas Linear Search
Analisis kompleksitas Linear Search dapat dilakukan dengan
mempertimbangkan tiga kondisi utama: kasus terbaik (best-case),
kasus rata-rata (average-case), dan kasus terburuk (worst-case).
Pada kasus terbaik, elemen yang dicari terletak di posisi
pertama dalam array. Dalam situasi ini, Linear Search hanya
memerlukan satu perbandingan, sehingga kompleksitasnya
menjadi O(1), karena algoritma langsung menemukan elemen
tanpa perlu memeriksa elemen lainnya.
Sebaliknya, pada kasus terburuk, elemen yang dicari berada di
posisi terakhir dalam array atau tidak ada sama sekali. Dalam hal
ini, algoritma harus memeriksa setiap elemen satu per satu
hingga mencapai akhir array. Dengan total perbandingan yang
dilakukan sebanyak n kali, kompleksitasnya adalah O(n).
Untuk kasus rata-rata, elemen yang dicari biasanya berada di
sekitar tengah array. Secara umum, algoritma akan memeriksa
sekitar setengah dari elemen sebelum menemukannya, sehingga
rata-rata langkah yang diperlukan adalah n/2. Namun, dalam
analisis Big-O, konstanta seperti 1/2 diabaikan, sehingga
kompleksitasnya tetap O(n).
Selain itu, Linear Search juga memiliki kompleksitas ruang
(Space Complexity), yang menunjukkan jumlah memori tambahan
yang diperlukan selama proses eksekusi. Karena algoritma ini
bekerja langsung pada array tanpa menyimpan data tambahan,
hanya menggunakan beberapa variabel sementara untuk iterasi
dan pemeriksaan elemen, kompleksitas ruangnya adalah O(1)
(konstan). Ini berarti jumlah memori yang digunakan tidak
meningkat seiring dengan bertambahnya ukuran data (n).
Dengan demikian, kompleksitas Linear Search adalah O(1)
dalam best-case (jika elemen ditemukan di awal), O(n) dalam
average-case (jika elemen berada di posisi acak dalam array), O(n)
dalam worst-case (jika elemen berada di akhir atau tidak ada
dalam array), dan O(1) dalam hal kompleksitas ruang.
28
Analisis kompleksitas Linear Search dapat dilakukan dengan
mempertimbangkan tiga kondisi utama: kasus terbaik (best-case),
kasus rata-rata (average-case), dan kasus terburuk (worst-case).
Pada kasus terbaik, elemen yang dicari terletak di posisi
pertama dalam array. Dalam situasi ini, Linear Search hanya
memerlukan satu perbandingan, sehingga kompleksitasnya
menjadi O(1), karena algoritma langsung menemukan elemen
tanpa perlu memeriksa elemen lainnya.
Sebaliknya, pada kasus terburuk, elemen yang dicari berada di
posisi terakhir dalam array atau tidak ada sama sekali. Dalam hal
ini, algoritma harus memeriksa setiap elemen satu per satu
hingga mencapai akhir array. Dengan total perbandingan yang
dilakukan sebanyak n kali, kompleksitasnya adalah O(n).
Untuk kasus rata-rata, elemen yang dicari biasanya berada di
sekitar tengah array. Secara umum, algoritma akan memeriksa
sekitar setengah dari elemen sebelum menemukannya, sehingga
rata-rata langkah yang diperlukan adalah n/2. Namun, dalam
analisis Big-O, konstanta seperti 1/2 diabaikan, sehingga
kompleksitasnya tetap O(n).
Selain itu, Linear Search juga memiliki kompleksitas ruang
(Space Complexity), yang menunjukkan jumlah memori tambahan
yang diperlukan selama proses eksekusi. Karena algoritma ini
bekerja langsung pada array tanpa menyimpan data tambahan,
hanya menggunakan beberapa variabel sementara untuk iterasi
dan pemeriksaan elemen, kompleksitas ruangnya adalah O(1)
(konstan). Ini berarti jumlah memori yang digunakan tidak
meningkat seiring dengan bertambahnya ukuran data (n).
Dengan demikian, kompleksitas Linear Search adalah O(1)
dalam best-case (jika elemen ditemukan di awal), O(n) dalam
average-case (jika elemen berada di posisi acak dalam array), O(n)
dalam worst-case (jika elemen berada di akhir atau tidak ada
dalam array), dan O(1) dalam hal kompleksitas ruang.
28
Tabel 4. 7 Kompleksitas waktu dan ruang Linear Search
Jenis Kompleksitas Nilai Penjelasan
Waktu (Best-Case) O(1) Jika elemen yang dicari berada
di indeks pertama.
Waktu (Worst-Case) O(n) Jika elemen yang dicari berada
di indeks terakhir atau tidak
ada dalam array.
Waktu (Average-Case) O(n) Jika elemen yang dicari berada
di posisi acak dalam array, rata-
rata memeriksa setengah
elemen.
Ruang (Space
Complexity)
O(1) Pencarian dilakukan langsung
pada array tanpa
menggunakan struktur data
tambahan.
e)Analisa Linear Search
Linear Search merupakan metode pencarian yang paling dasar,
yang berfungsi dengan memeriksa setiap elemen dalam daftar
secara berurutan hingga menemukan elemen yang dicari atau
sampai mencapai akhir daftar. Algoritma ini tidak memerlukan data
yang terurut, sehingga sangat sesuai untuk pencarian dalam dataset
kecil atau yang tidak terstruktur. Linear Search memiliki kompleksitas
waktu O(n) di semua kasus, karena dalam skenario terburuk, elemen
yang dicari bisa saja berada di akhir daftar atau bahkan tidak
ditemukan sama sekali.
Dengan rentang data antara 100 hingga 1.000 elemen dan
melakukan pengulangan proses hingga 100 kali untuk mendapatkan
rata-rata waktu eksekusi, kinerja Linear Search dapat dianalisis
dengan lebih tepat. Waktu eksekusi diukur dalam satuan Milidetik
(ms) untuk menunjukkan seberapa efisien algoritma ini dalam
menangani berbagai ukuran data.
Tabel 4. 8 Waktu eksekusi algoritma Linear Search
Jumlah Elemen ArrayWaktu (ms)
29
Jenis Kompleksitas Nilai Penjelasan
Waktu (Best-Case) O(1) Jika elemen yang dicari berada
di indeks pertama.
Waktu (Worst-Case) O(n) Jika elemen yang dicari berada
di indeks terakhir atau tidak
ada dalam array.
Waktu (Average-Case) O(n) Jika elemen yang dicari berada
di posisi acak dalam array, rata-
rata memeriksa setengah
elemen.
Ruang (Space
Complexity)
O(1) Pencarian dilakukan langsung
pada array tanpa
menggunakan struktur data
tambahan.
e)Analisa Linear Search
Linear Search merupakan metode pencarian yang paling dasar,
yang berfungsi dengan memeriksa setiap elemen dalam daftar
secara berurutan hingga menemukan elemen yang dicari atau
sampai mencapai akhir daftar. Algoritma ini tidak memerlukan data
yang terurut, sehingga sangat sesuai untuk pencarian dalam dataset
kecil atau yang tidak terstruktur. Linear Search memiliki kompleksitas
waktu O(n) di semua kasus, karena dalam skenario terburuk, elemen
yang dicari bisa saja berada di akhir daftar atau bahkan tidak
ditemukan sama sekali.
Dengan rentang data antara 100 hingga 1.000 elemen dan
melakukan pengulangan proses hingga 100 kali untuk mendapatkan
rata-rata waktu eksekusi, kinerja Linear Search dapat dianalisis
dengan lebih tepat. Waktu eksekusi diukur dalam satuan Milidetik
(ms) untuk menunjukkan seberapa efisien algoritma ini dalam
menangani berbagai ukuran data.
Tabel 4. 8 Waktu eksekusi algoritma Linear Search
Jumlah Elemen ArrayWaktu (ms)
29
100 0.087
250 0.095
500 0.114
750 0.146
1.000 0.216
Gambar 4. 12 Grafik perbandingan waktu eksekusi algoritma linear search
30
250 0.095
500 0.114
750 0.146
1.000 0.216
Gambar 4. 12 Grafik perbandingan waktu eksekusi algoritma linear search
30
IV.2.2 Binary Search
a)Flowchart Binary Search
31
a)Flowchart Binary Search
31
Gambar 4. 13 Flowchart Binary Search
b)Pseudocode Binary Search
32
b)Pseudocode Binary Search
32
BINARY_SEARCH(array, target, low, high)
while low high do
≤
mid ← (low + high) / 2
if array[mid] = target then
return “elemen ditemukan”
else if array[mid] < target then
low ← mid + 1
else
high ← mid - 1
end while
return “elemen tidak ditemukan”
END
c)Implementasi Binary Search
33
while low high do
≤
mid ← (low + high) / 2
if array[mid] = target then
return “elemen ditemukan”
else if array[mid] < target then
low ← mid + 1
else
high ← mid - 1
end while
return “elemen tidak ditemukan”
END
c)Implementasi Binary Search
33
Gambar 4. 14 Implementasi Binary Search di Javascript
d)Kompleksitas Binary Search
Kompleksitas algoritma Binary Search dapat dianalisis
berdasarkan tiga kondisi utama, yaitu kasus terbaik, kasus rata-
rata, dan kasus terburuk. Pada kasus terbaik, elemen yang dicari
berada tepat di tengah array pada langkah pertama, sehingga
algoritma hanya memerlukan satu perbandingan untuk
menemukan elemen tersebut. Dalam kondisi ini, kompleksitasnya
menjadi O(1) karena pencarian selesai tanpa langkah tambahan.
34
d)Kompleksitas Binary Search
Kompleksitas algoritma Binary Search dapat dianalisis
berdasarkan tiga kondisi utama, yaitu kasus terbaik, kasus rata-
rata, dan kasus terburuk. Pada kasus terbaik, elemen yang dicari
berada tepat di tengah array pada langkah pertama, sehingga
algoritma hanya memerlukan satu perbandingan untuk
menemukan elemen tersebut. Dalam kondisi ini, kompleksitasnya
menjadi O(1) karena pencarian selesai tanpa langkah tambahan.
34
Sebaliknya, pada kasus terburuk, elemen yang dicari berada di
ujung array atau tidak ada dalam array sama sekali. Dalam situasi
tersebut, Binary Search akan terus membagi array menjadi dua
bagian hingga tersisa satu elemen terakhir yang diperiksa. Karena
setiap langkah membagi ukuran array menjadi setengah, jumlah
total langkah yang diperlukan dapat dinyatakan sebagai log₂(n),
sehingga kompleksitasnya adalah O(log n).
Sementara itu, pada kasus rata-rata, elemen yang dicari dapat
berada di posisi mana saja dalam array. Secara umum, algoritma
tetap melakukan pembagian array secara logaritmik, sehingga
jumlah rata-rata langkah yang diperlukan juga O(log n), sama
seperti pada kasus terburuk.
Selain kompleksitas waktu, Binary Search juga memiliki
kompleksitas ruang yang menunjukkan seberapa banyak memori
tambahan yang dibutuhkan selama proses eksekusi. Karena
algoritma ini dilakukan langsung pada array yang sudah terurut,
ia hanya membutuhkan beberapa variabel tambahan untuk
menyimpan nilai batas low, high, dan mid selama pencarian. Oleh
karena itu, kompleksitas ruangnya adalah O(1) dalam
implementasi iteratif. Namun, jika menggunakan pendekatan
rekursif, setiap pemanggilan fungsi akan menyimpan status
dalam stack, sehingga kompleksitas ruangnya menjadi O(log n)
karena terdapat log n tingkat rekursi.
Dengan demikian, Binary Search memiliki kompleksitas O(1)
dalam kasus terbaik (jika elemen ditemukan langsung di tengah),
O(log n) dalam kasus rata-rata (jika elemen berada di posisi acak
dalam array), O(log n) dalam kasus terburuk (jika elemen berada
di ujung atau tidak ada dalam array), O(1) dalam kompleksitas
ruang dengan implementasi iteratif, dan O(log n) dalam
kompleksitas ruang dengan implementasi rekursif.
Tabel 4. 9 Kompleksitas Waktu dan Ruang Binary Search
Jenis Kompleksitas Nilai Penjelasan
Waktu (Best-Case) O(1) Jika elemen yang dicari berada
di tengah array pada langkah
pertama.
Waktu (Worst-Case) O(log n) Jika elemen berada di ujung
35
ujung array atau tidak ada dalam array sama sekali. Dalam situasi
tersebut, Binary Search akan terus membagi array menjadi dua
bagian hingga tersisa satu elemen terakhir yang diperiksa. Karena
setiap langkah membagi ukuran array menjadi setengah, jumlah
total langkah yang diperlukan dapat dinyatakan sebagai log₂(n),
sehingga kompleksitasnya adalah O(log n).
Sementara itu, pada kasus rata-rata, elemen yang dicari dapat
berada di posisi mana saja dalam array. Secara umum, algoritma
tetap melakukan pembagian array secara logaritmik, sehingga
jumlah rata-rata langkah yang diperlukan juga O(log n), sama
seperti pada kasus terburuk.
Selain kompleksitas waktu, Binary Search juga memiliki
kompleksitas ruang yang menunjukkan seberapa banyak memori
tambahan yang dibutuhkan selama proses eksekusi. Karena
algoritma ini dilakukan langsung pada array yang sudah terurut,
ia hanya membutuhkan beberapa variabel tambahan untuk
menyimpan nilai batas low, high, dan mid selama pencarian. Oleh
karena itu, kompleksitas ruangnya adalah O(1) dalam
implementasi iteratif. Namun, jika menggunakan pendekatan
rekursif, setiap pemanggilan fungsi akan menyimpan status
dalam stack, sehingga kompleksitas ruangnya menjadi O(log n)
karena terdapat log n tingkat rekursi.
Dengan demikian, Binary Search memiliki kompleksitas O(1)
dalam kasus terbaik (jika elemen ditemukan langsung di tengah),
O(log n) dalam kasus rata-rata (jika elemen berada di posisi acak
dalam array), O(log n) dalam kasus terburuk (jika elemen berada
di ujung atau tidak ada dalam array), O(1) dalam kompleksitas
ruang dengan implementasi iteratif, dan O(log n) dalam
kompleksitas ruang dengan implementasi rekursif.
Tabel 4. 9 Kompleksitas Waktu dan Ruang Binary Search
Jenis Kompleksitas Nilai Penjelasan
Waktu (Best-Case) O(1) Jika elemen yang dicari berada
di tengah array pada langkah
pertama.
Waktu (Worst-Case) O(log n) Jika elemen berada di ujung
35
array atau tidak ada, algoritma
terus membagi array hingga
tersisa satu elemen.
Waktu (Average-Case) O(log n)Setiap iterasi membagi jumlah
elemen menjadi setengah
hingga elemen ditemukan atau
tidak ada.
Ruang (Space
Complexity)
O(1)
(iteratif)
Hanya menggunakan variabel
tambahan untuk batas
pencarian (low, high, mid).
Ruang (Space
Complexity)
O(log n)
(rekursif)
Jika menggunakan rekursi,
memori tambahan digunakan
untuk menyimpan state rekursi.
e)Analisa Binary Search
Binary Search adalah algoritma pencarian yang jauh lebih cepat
dibandingkan dengan Linear Search, tetapi penggunaannya terbatas
pada data yang sudah terurut. Algoritma ini beroperasi dengan cara
membagi daftar menjadi dua bagian pada setiap langkah.
Selanjutnya, elemen tengah dibandingkan dengan nilai yang dicari
untuk menentukan apakah pencarian harus dilanjutkan ke bagian kiri
atau kanan. Dengan strategi ini, jumlah elemen yang perlu diperiksa
berkurang secara eksponensial, sehingga Binary Search memiliki
kompleksitas waktu O(log n), yang jauh lebih efisien dibandingkan
dengan O(n) pada Linear Search.
Namun, salah satu keterbatasan utama dari Binary Search adalah
bahwa data harus terurut terlebih dahulu. Proses pengurutan ini
mungkin memerlukan waktu tambahan jika data masih dalam
keadaan acak. Untuk menganalisis performa Binary Search secara
lebih akurat, dapat dilakukan pengujian dengan interval data antara
100 hingga 1.000 elemen dan mengulangi proses tersebut hingga
100 kali untuk mendapatkan rata-rata waktu eksekusi.
Waktu eksekusi tersebut dihitung dalam satuan milisecond (ms)
untuk menunjukkan efisiensi algoritma dalam menangani berbagai
ukuran data. Dengan pendekatan ini, kita dapat memperoleh
gambaran yang lebih jelas mengenai seberapa baik Binary Search
bekerja dalam situasi yang berbeda.
Tabel 4. 10 Waktu eksekusi algoritma Binary Search
Jumlah Elemen ArrayWaktu (ms)
100 0.08
36
terus membagi array hingga
tersisa satu elemen.
Waktu (Average-Case) O(log n)Setiap iterasi membagi jumlah
elemen menjadi setengah
hingga elemen ditemukan atau
tidak ada.
Ruang (Space
Complexity)
O(1)
(iteratif)
Hanya menggunakan variabel
tambahan untuk batas
pencarian (low, high, mid).
Ruang (Space
Complexity)
O(log n)
(rekursif)
Jika menggunakan rekursi,
memori tambahan digunakan
untuk menyimpan state rekursi.
e)Analisa Binary Search
Binary Search adalah algoritma pencarian yang jauh lebih cepat
dibandingkan dengan Linear Search, tetapi penggunaannya terbatas
pada data yang sudah terurut. Algoritma ini beroperasi dengan cara
membagi daftar menjadi dua bagian pada setiap langkah.
Selanjutnya, elemen tengah dibandingkan dengan nilai yang dicari
untuk menentukan apakah pencarian harus dilanjutkan ke bagian kiri
atau kanan. Dengan strategi ini, jumlah elemen yang perlu diperiksa
berkurang secara eksponensial, sehingga Binary Search memiliki
kompleksitas waktu O(log n), yang jauh lebih efisien dibandingkan
dengan O(n) pada Linear Search.
Namun, salah satu keterbatasan utama dari Binary Search adalah
bahwa data harus terurut terlebih dahulu. Proses pengurutan ini
mungkin memerlukan waktu tambahan jika data masih dalam
keadaan acak. Untuk menganalisis performa Binary Search secara
lebih akurat, dapat dilakukan pengujian dengan interval data antara
100 hingga 1.000 elemen dan mengulangi proses tersebut hingga
100 kali untuk mendapatkan rata-rata waktu eksekusi.
Waktu eksekusi tersebut dihitung dalam satuan milisecond (ms)
untuk menunjukkan efisiensi algoritma dalam menangani berbagai
ukuran data. Dengan pendekatan ini, kita dapat memperoleh
gambaran yang lebih jelas mengenai seberapa baik Binary Search
bekerja dalam situasi yang berbeda.
Tabel 4. 10 Waktu eksekusi algoritma Binary Search
Jumlah Elemen ArrayWaktu (ms)
100 0.08
36
250 0.087
500 0.106
750 0.091
1.000 0.102
Gambar 4. 15 Grafik perbandingan waktu eksekusi algoritma binary search
37
500 0.106
750 0.091
1.000 0.102
Gambar 4. 15 Grafik perbandingan waktu eksekusi algoritma binary search
37
IV.2.3 Hash Search
a)Flowchart Hash Search
38
a)Flowchart Hash Search
38
Gambar 4. 16 Flowchart Hash Search
b)Pseudocode Hash Search
39
b)Pseudocode Hash Search
39
HASH_SEARCH(hashTable, key)
index
if hashTable[index] contains key then
return “Elemen ditemukan”
else
return “Elemen tidak ditemukan”
END
c)Implementasi Hash Search
Gambar 4. 17 Implementasi Hash Search di Javascript
40
index
if hashTable[index] contains key then
return “Elemen ditemukan”
else
return “Elemen tidak ditemukan”
END
c)Implementasi Hash Search
Gambar 4. 17 Implementasi Hash Search di Javascript
40
d)Kompleksitas Hash Search
Kompleksitas algoritma Hash Search dapat dianalisis
berdasarkan tiga kondisi utama, yaitu kasus terbaik, kasus rata-
rata, dan kasus terburuk. Pada kasus terbaik, elemen yang dicari
memiliki hash index yang langsung menunjuk ke lokasi yang
benar dalam satu kali pencarian. Dalam situasi ini, algoritma
hanya perlu melakukan satu operasi akses ke hash table,
sehingga kompleksitasnya menjadi O(1). Hal ini terjadi jika fungsi
hash berfungsi secara optimal tanpa adanya tabrakan (collision).
Sebaliknya, pada kasus terburuk, sering terjadi banyak
tabrakan, di mana beberapa elemen memiliki hash index yang
sama dan harus disimpan dalam linked list atau metode
penanganan tabrakan lainnya, seperti chaining atau open
addressing. Dalam kondisi ini, pencarian tidak dapat dilakukan
dalam satu langkah saja; pencarian harus melewati beberapa
elemen dalam bucket yang sama. Jika semua elemen bertabrakan
ke indeks yang sama, proses pencarian akan berjalan mirip
dengan Linear Search, sehingga kompleksitasnya menjadi O(n).
Sementara itu, pada kasus rata-rata, fungsi hash biasanya
berfungsi dengan baik sehingga tabrakan jarang terjadi. Dalam
keadaan ini, elemen yang dicari dapat ditemukan dalam beberapa
langkah saja. Secara umum, waktu pencarian rata-rata tetap O(1)
karena hanya sedikit perbandingan yang diperlukan dalam bucket
jika terjadi tabrakan.
Selain kompleksitas waktu, algoritma Hash Search juga
memiliki kompleksitas ruang (Space Complexity), yang
menunjukkan seberapa banyak memori tambahan yang
dibutuhkan selama proses eksekusi. Berbeda dengan Linear
Search dan Binary Search, Hash Search menggunakan struktur
data tambahan berupa hash table, yang memerlukan ruang
memori ekstra untuk menyimpan elemen dalam tabel. Dalam
kondisi ideal tanpa tabrakan, kompleksitas ruangnya adalah O(n)
karena setiap elemen membutuhkan slot dalam hash table.
Dengan demikian, Hash Search memiliki trade-off antara
kecepatan akses O(1) dan penggunaan memori tambahan
sebesar O(n).
Secara keseluruhan, Hash Search memiliki kompleksitas O(1)
dalam kasus terbaik (jika tidak ada tabrakan), O(1) dalam kasus
41
Kompleksitas algoritma Hash Search dapat dianalisis
berdasarkan tiga kondisi utama, yaitu kasus terbaik, kasus rata-
rata, dan kasus terburuk. Pada kasus terbaik, elemen yang dicari
memiliki hash index yang langsung menunjuk ke lokasi yang
benar dalam satu kali pencarian. Dalam situasi ini, algoritma
hanya perlu melakukan satu operasi akses ke hash table,
sehingga kompleksitasnya menjadi O(1). Hal ini terjadi jika fungsi
hash berfungsi secara optimal tanpa adanya tabrakan (collision).
Sebaliknya, pada kasus terburuk, sering terjadi banyak
tabrakan, di mana beberapa elemen memiliki hash index yang
sama dan harus disimpan dalam linked list atau metode
penanganan tabrakan lainnya, seperti chaining atau open
addressing. Dalam kondisi ini, pencarian tidak dapat dilakukan
dalam satu langkah saja; pencarian harus melewati beberapa
elemen dalam bucket yang sama. Jika semua elemen bertabrakan
ke indeks yang sama, proses pencarian akan berjalan mirip
dengan Linear Search, sehingga kompleksitasnya menjadi O(n).
Sementara itu, pada kasus rata-rata, fungsi hash biasanya
berfungsi dengan baik sehingga tabrakan jarang terjadi. Dalam
keadaan ini, elemen yang dicari dapat ditemukan dalam beberapa
langkah saja. Secara umum, waktu pencarian rata-rata tetap O(1)
karena hanya sedikit perbandingan yang diperlukan dalam bucket
jika terjadi tabrakan.
Selain kompleksitas waktu, algoritma Hash Search juga
memiliki kompleksitas ruang (Space Complexity), yang
menunjukkan seberapa banyak memori tambahan yang
dibutuhkan selama proses eksekusi. Berbeda dengan Linear
Search dan Binary Search, Hash Search menggunakan struktur
data tambahan berupa hash table, yang memerlukan ruang
memori ekstra untuk menyimpan elemen dalam tabel. Dalam
kondisi ideal tanpa tabrakan, kompleksitas ruangnya adalah O(n)
karena setiap elemen membutuhkan slot dalam hash table.
Dengan demikian, Hash Search memiliki trade-off antara
kecepatan akses O(1) dan penggunaan memori tambahan
sebesar O(n).
Secara keseluruhan, Hash Search memiliki kompleksitas O(1)
dalam kasus terbaik (jika tidak ada tabrakan), O(1) dalam kasus
41
rata-rata (jika tabrakan minimal), O(n) dalam kasus terburuk (jika
banyak tabrakan terjadi sehingga pencarian menjadi linear), dan
O(n) dalam hal kompleksitas ruang.
Tabel 4. 11 Kompleksitas waktu dan ruang Hash Search
Jenis Kompleksitas Nilai Penjelasan
Waktu (Best-Case) O(1) Jika fungsi hash bekerja
optimal, elemen langsung
ditemukan dalam satu langkah.
Waktu (Worst-Case) O(n) Jika terjadi banyak tabrakan
(collision), pencarian berubah
menjadi linear dalam bucket
yang sama.
Waktu (Average-Case) O(1) Jika tabrakan minimal,
pencarian tetap O(1) karena
langsung menuju indeks hash.
Ruang (Space
Complexity)
O(n) Menggunakan struktur data
tambahan berupa hash table
untuk menyimpan elemen.
e)Analisa Hash Search
Hash Search merupakan metode pencarian yang paling cepat
dalam kondisi ideal, karena dapat menemukan elemen yang dicari
dalam satu langkah dengan kompleksitas O(1) menggunakan
struktur data hash table. Algoritma ini beroperasi dengan
memanfaatkan fungsi hash untuk menghitung indeks penyimpanan
elemen. Dengan cara ini, pencarian dapat dilakukan melalui akses
langsung ke indeks tersebut tanpa perlu membandingkan elemen
satu per satu.
Keunggulan utama dari Hash Search terletak pada kecepatan
pencariannya yang sangat tinggi jika dibandingkan dengan Linear
Search dan Binary Search. Namun, algoritma ini juga memiliki
beberapa kelemahan. Salah satunya adalah kebutuhan akan memori
tambahan untuk menyimpan hash table, yang memiliki kompleksitas
ruang O(n). Selain itu, terdapat risiko terjadinya tabrakan (collision),
42
banyak tabrakan terjadi sehingga pencarian menjadi linear), dan
O(n) dalam hal kompleksitas ruang.
Tabel 4. 11 Kompleksitas waktu dan ruang Hash Search
Jenis Kompleksitas Nilai Penjelasan
Waktu (Best-Case) O(1) Jika fungsi hash bekerja
optimal, elemen langsung
ditemukan dalam satu langkah.
Waktu (Worst-Case) O(n) Jika terjadi banyak tabrakan
(collision), pencarian berubah
menjadi linear dalam bucket
yang sama.
Waktu (Average-Case) O(1) Jika tabrakan minimal,
pencarian tetap O(1) karena
langsung menuju indeks hash.
Ruang (Space
Complexity)
O(n) Menggunakan struktur data
tambahan berupa hash table
untuk menyimpan elemen.
e)Analisa Hash Search
Hash Search merupakan metode pencarian yang paling cepat
dalam kondisi ideal, karena dapat menemukan elemen yang dicari
dalam satu langkah dengan kompleksitas O(1) menggunakan
struktur data hash table. Algoritma ini beroperasi dengan
memanfaatkan fungsi hash untuk menghitung indeks penyimpanan
elemen. Dengan cara ini, pencarian dapat dilakukan melalui akses
langsung ke indeks tersebut tanpa perlu membandingkan elemen
satu per satu.
Keunggulan utama dari Hash Search terletak pada kecepatan
pencariannya yang sangat tinggi jika dibandingkan dengan Linear
Search dan Binary Search. Namun, algoritma ini juga memiliki
beberapa kelemahan. Salah satunya adalah kebutuhan akan memori
tambahan untuk menyimpan hash table, yang memiliki kompleksitas
ruang O(n). Selain itu, terdapat risiko terjadinya tabrakan (collision),
42
di mana beberapa elemen memiliki indeks hash yang sama, sehingga
dapat memperlambat proses pencarian.
Untuk menganalisis performa Hash Search secara lebih akurat,
dapat dilakukan pengujian dengan interval data antara 100 hingga
1.000 elemen dan mengulangi proses tersebut hingga 100 kali untuk
mendapatkan rata-rata waktu eksekusi. Waktu eksekusi ini dihitung
dalam satuan milisecond (ms) untuk menunjukkan efisiensi algoritma
dalam menangani berbagai ukuran data. Dengan pendekatan ini, kita
dapat memperoleh gambaran yang lebih jelas mengenai kinerja
Hash Search dalam berbagai situasi.
Tabel 4. 12 Waktu eksekusi algoritma Hash Search
Jumlah Elemen ArrayWaktu (ms)
100 0.074
250 0.075
500 0.076
750 0.078
1.000 0.08
43
dapat memperlambat proses pencarian.
Untuk menganalisis performa Hash Search secara lebih akurat,
dapat dilakukan pengujian dengan interval data antara 100 hingga
1.000 elemen dan mengulangi proses tersebut hingga 100 kali untuk
mendapatkan rata-rata waktu eksekusi. Waktu eksekusi ini dihitung
dalam satuan milisecond (ms) untuk menunjukkan efisiensi algoritma
dalam menangani berbagai ukuran data. Dengan pendekatan ini, kita
dapat memperoleh gambaran yang lebih jelas mengenai kinerja
Hash Search dalam berbagai situasi.
Tabel 4. 12 Waktu eksekusi algoritma Hash Search
Jumlah Elemen ArrayWaktu (ms)
100 0.074
250 0.075
500 0.076
750 0.078
1.000 0.08
43
Gambar 4. 18 Grafik perbandingan waktu eksekusi algoritma hash search
IV.3 Perbandingan Efisiensi Algoritma
IV.3.1 Algoritma Sorting
Tabel 4. 13 Hasil perbandingan waktu eksekusi algoritma pengurutan
Jumlah Array Bubble Sort
(ms)
Quick Sort (ms)Selection Sort (ms)
100 0.658 0.173 0.302
250 3.788 0.467 0.643
500 8.581 0.603 1.221
750 9.629 1.296 1.501
1.000 11.561 1.384 2.692
Berdasarkan hasil eksekusi program yang ditampilkan pada gambar,
terlihat adanya perbedaan waktu yang cukup signifikan di antara algoritma-
algoritma pengurutan. Algoritma quicksort menunjukkan kinerja yang lebih
cepat dibandingkan dengan algoritma lainnya, menjadikannya salah satu
metode yang unggul dalam hal kecepatan pengurutan data.
Namun, setiap algoritma pengurutan memiliki karakteristik masing-
masing yang perlu diperhatikan sebelum digunakan. Kelebihan dan
kekurangan dari setiap algoritma menjadi faktor penting yang harus
dipertimbangkan agar pengguna dapat memilih metode yang paling sesuai
dengan kebutuhan.
Beberapa aspek utama dalam pemilihan algoritma pengurutan
meliputi kecepatan proses, efisiensi penggunaan memori, kemampuan
algoritma untuk menangani data yang sudah sebagian terurut, serta tingkat
kompleksitas implementasinya. Dengan mempertimbangkan faktor-faktor
tersebut, pengguna dapat menentukan algoritma yang optimal untuk
situasi tertentu.
Tabel 4. 14 Kelebihan dan kekurangan algoritma sorting
Algoritma Kelebihan Kekurangan
Bubble Sort- mudah diimplementasikan
dan dipahami.
- cocok untuk dataset kecil
atau hampir terurut.
- tidak membutuhkan
banyak memori tambahan
- sangat lambat untuk
dataset besar (O(n²)).
- banyak melakukan
pertukaran elemen yang
tidak perlu.
- tidak efisien dibandingkan
44
IV.3 Perbandingan Efisiensi Algoritma
IV.3.1 Algoritma Sorting
Tabel 4. 13 Hasil perbandingan waktu eksekusi algoritma pengurutan
Jumlah Array Bubble Sort
(ms)
Quick Sort (ms)Selection Sort (ms)
100 0.658 0.173 0.302
250 3.788 0.467 0.643
500 8.581 0.603 1.221
750 9.629 1.296 1.501
1.000 11.561 1.384 2.692
Berdasarkan hasil eksekusi program yang ditampilkan pada gambar,
terlihat adanya perbedaan waktu yang cukup signifikan di antara algoritma-
algoritma pengurutan. Algoritma quicksort menunjukkan kinerja yang lebih
cepat dibandingkan dengan algoritma lainnya, menjadikannya salah satu
metode yang unggul dalam hal kecepatan pengurutan data.
Namun, setiap algoritma pengurutan memiliki karakteristik masing-
masing yang perlu diperhatikan sebelum digunakan. Kelebihan dan
kekurangan dari setiap algoritma menjadi faktor penting yang harus
dipertimbangkan agar pengguna dapat memilih metode yang paling sesuai
dengan kebutuhan.
Beberapa aspek utama dalam pemilihan algoritma pengurutan
meliputi kecepatan proses, efisiensi penggunaan memori, kemampuan
algoritma untuk menangani data yang sudah sebagian terurut, serta tingkat
kompleksitas implementasinya. Dengan mempertimbangkan faktor-faktor
tersebut, pengguna dapat menentukan algoritma yang optimal untuk
situasi tertentu.
Tabel 4. 14 Kelebihan dan kekurangan algoritma sorting
Algoritma Kelebihan Kekurangan
Bubble Sort- mudah diimplementasikan
dan dipahami.
- cocok untuk dataset kecil
atau hampir terurut.
- tidak membutuhkan
banyak memori tambahan
- sangat lambat untuk
dataset besar (O(n²)).
- banyak melakukan
pertukaran elemen yang
tidak perlu.
- tidak efisien dibandingkan
44
(O(1)). metode lain seperti Quick
Sort.
Quick Sort- jauh lebih cepat
dibandingkan dengan
Bubble dan Selection Sort
(O(n log n) dalam best dan
average case).
- cocok untuk dataset besar.
- bekerja secara in-place
dengan memori tambahan
minimal (O(log n)).
- kasus terburuk bisa
mencapai O(n²) jika pivot
dipilih buruk.
- implementasinya lebih
kompleks dibanding Bubble
dan Selection Sort.
Selection
Sort
- lebih sedikit melakukan
pertukaran elemen
dibandingkan dengan
Bubble Sort.
- cocok untuk kasus di mana
pertukaran data harus
diminimalkan.
- tidak membutuhkan
banyak memori tambahan
(O(1)).
- masih memiliki
kompleksitas O(n²), sehingga
tidak efisien untuk dataset
besar.
- tetap melakukan
perbandingan sebanyak
Bubble Sort, meskipun
dengan lebih sedikit
pertukaran.
- tidak secepat Quick Sort
untuk dataset besar.
IV.3.2 Algoritma Searching
Tabel 4. 15 Hasil perbandingan waktu eksekusi algoritma searching
Jumlah
Array
Linear Search
(ms)
Binary Search
(ms)
Hash Search (ms)
100 1.55 0.59 0.48
250 2.20 1.14 0.72
500 2.56 1.50 0.88
45
Sort.
Quick Sort- jauh lebih cepat
dibandingkan dengan
Bubble dan Selection Sort
(O(n log n) dalam best dan
average case).
- cocok untuk dataset besar.
- bekerja secara in-place
dengan memori tambahan
minimal (O(log n)).
- kasus terburuk bisa
mencapai O(n²) jika pivot
dipilih buruk.
- implementasinya lebih
kompleks dibanding Bubble
dan Selection Sort.
Selection
Sort
- lebih sedikit melakukan
pertukaran elemen
dibandingkan dengan
Bubble Sort.
- cocok untuk kasus di mana
pertukaran data harus
diminimalkan.
- tidak membutuhkan
banyak memori tambahan
(O(1)).
- masih memiliki
kompleksitas O(n²), sehingga
tidak efisien untuk dataset
besar.
- tetap melakukan
perbandingan sebanyak
Bubble Sort, meskipun
dengan lebih sedikit
pertukaran.
- tidak secepat Quick Sort
untuk dataset besar.
IV.3.2 Algoritma Searching
Tabel 4. 15 Hasil perbandingan waktu eksekusi algoritma searching
Jumlah
Array
Linear Search
(ms)
Binary Search
(ms)
Hash Search (ms)
100 1.55 0.59 0.48
250 2.20 1.14 0.72
500 2.56 1.50 0.88
45
750 2.84 1.62 0.59
1.000 2.79 2.07 0.82
Hasil eksekusi program menunjukkan adanya perbedaan yang
signifikan dalam waktu pencarian antara berbagai algoritma yang diuji.
Metode Hash Search terbukti jauh lebih cepat dibandingkan dengan Linear
Search dan Binary Search, terutama ketika jumlah data yang dicari semakin
besar. Ini mengindikasikan bahwa Hash Search merupakan pilihan terbaik
untuk pencarian yang cepat, meskipun ada trade-off berupa penggunaan
memori tambahan untuk menyimpan hash table.
Namun, penting untuk diingat bahwa setiap algoritma pencarian
memiliki kelebihan dan kekurangan masing-masing yang perlu
dipertimbangkan sebelum digunakan. Beberapa faktor utama yang harus
diperhatikan dalam memilih metode pencarian meliputi kecepatan
pencarian, efisiensi penggunaan memori, serta kompatibilitas dengan data
yang terurut maupun tidak terurut. Selain itu, kompleksitas implementasi
juga menjadi pertimbangan penting.
Untuk memberikan gambaran yang lebih jelas, berikut adalah tabel
perbandingan kelebihan dan kekurangan dari masing-masing algoritma
pencarian. Tabel ini dapat membantu pengguna dalam menentukan metode
pencarian yang paling sesuai dengan kebutuhan spesifik mereka.
Tabel 4. 16 Kelebihan dan kekurangan algoritma searching
Algoritma Kelebihan Kekurangan
Linear
Search
- mudah diimplementasikan
dan dipahami.
- tidak membutuhkan data
yang sudah terurut.
- cocok untuk dataset kecil
- lambat untuk dataset besar
(O(n) waktu pencarian).
- harus memeriksa setiap
elemen satu per satu.
- tidak efisien dibanding
metode lain seperti Binary
atau Hash Search.
Binary
Search
- jauh lebih cepat
dibandingkan Linear Search
(O(log n)).
- efisien untuk dataset besar
jika sudah terurut.
- menggunakan sedikit
memori tambahan (O(1)
iteratif atau O(log n)
- hanya bisa digunakan pada
data yang sudah terurut.
- tidak cocok untuk struktur
data yang dinamis.
- implementasi sedikit lebih
kompleks dibanding Linear
Search.
46
1.000 2.79 2.07 0.82
Hasil eksekusi program menunjukkan adanya perbedaan yang
signifikan dalam waktu pencarian antara berbagai algoritma yang diuji.
Metode Hash Search terbukti jauh lebih cepat dibandingkan dengan Linear
Search dan Binary Search, terutama ketika jumlah data yang dicari semakin
besar. Ini mengindikasikan bahwa Hash Search merupakan pilihan terbaik
untuk pencarian yang cepat, meskipun ada trade-off berupa penggunaan
memori tambahan untuk menyimpan hash table.
Namun, penting untuk diingat bahwa setiap algoritma pencarian
memiliki kelebihan dan kekurangan masing-masing yang perlu
dipertimbangkan sebelum digunakan. Beberapa faktor utama yang harus
diperhatikan dalam memilih metode pencarian meliputi kecepatan
pencarian, efisiensi penggunaan memori, serta kompatibilitas dengan data
yang terurut maupun tidak terurut. Selain itu, kompleksitas implementasi
juga menjadi pertimbangan penting.
Untuk memberikan gambaran yang lebih jelas, berikut adalah tabel
perbandingan kelebihan dan kekurangan dari masing-masing algoritma
pencarian. Tabel ini dapat membantu pengguna dalam menentukan metode
pencarian yang paling sesuai dengan kebutuhan spesifik mereka.
Tabel 4. 16 Kelebihan dan kekurangan algoritma searching
Algoritma Kelebihan Kekurangan
Linear
Search
- mudah diimplementasikan
dan dipahami.
- tidak membutuhkan data
yang sudah terurut.
- cocok untuk dataset kecil
- lambat untuk dataset besar
(O(n) waktu pencarian).
- harus memeriksa setiap
elemen satu per satu.
- tidak efisien dibanding
metode lain seperti Binary
atau Hash Search.
Binary
Search
- jauh lebih cepat
dibandingkan Linear Search
(O(log n)).
- efisien untuk dataset besar
jika sudah terurut.
- menggunakan sedikit
memori tambahan (O(1)
iteratif atau O(log n)
- hanya bisa digunakan pada
data yang sudah terurut.
- tidak cocok untuk struktur
data yang dinamis.
- implementasi sedikit lebih
kompleks dibanding Linear
Search.
46
rekursif).
Hash
Search
- paling cepat (O(1) dalam
kondisi ideal).
- tidak perlu
membandingkan banyak
elemen.
- cocok untuk pencarian
dalam jumlah data yang
sangat besar.
- tidak membutuhkan data
yang sudah terurut
- membutuhkan memori
tambahan (O(n)) untuk
menyimpan hash table.
- bisa terjadi collision yang
menyebabkan pencarian
lebih lambat.
- bergantung pada kualitas
fungsi hash yang digunakan.
47
Hash
Search
- paling cepat (O(1) dalam
kondisi ideal).
- tidak perlu
membandingkan banyak
elemen.
- cocok untuk pencarian
dalam jumlah data yang
sangat besar.
- tidak membutuhkan data
yang sudah terurut
- membutuhkan memori
tambahan (O(n)) untuk
menyimpan hash table.
- bisa terjadi collision yang
menyebabkan pencarian
lebih lambat.
- bergantung pada kualitas
fungsi hash yang digunakan.
47
BAB V
KESIMPULAN DAN SARAN
V.1 Kesimpulan
Berdasarkan analisis efisiensi algoritma sorting dan searching yang
dilakukan dengan mempertimbangkan kompleksitas waktu dan ruang,
dapat disimpulkan bahwa pemilihan algoritma yang tepat sangat
dipengaruhi oleh jumlah data, kondisi awal data, serta kebutuhan akan
efisiensi waktu dan memori.
Dalam konteks algoritma sorting, Bubble Sort dan Selection Sort
memiliki kompleksitas waktu O(n²), yang membuat kedua algoritma ini
kurang efisien ketika diterapkan pada dataset besar. Meskipun Bubble Sort
dikenal karena kemudahan implementasinya, jumlah pertukaran elemen
yang tinggi membuat proses pengurutannya menjadi sangat lambat. Di sisi
lain, Selection Sort lebih efisien dalam hal pertukaran elemen, namun tetap
tidak dapat bersaing dengan Quick Sort, yang memiliki kompleksitas O(n log
n) dalam kondisi terbaik dan rata-rata. Hal ini menjadikan Quick Sort jauh
lebih cepat untuk pengolahan dataset besar.
Pada algoritma searching, Linear Search memiliki kompleksitas O(n),
sehingga tidak efisien untuk dataset besar, kecuali dalam situasi di mana
data tidak terurut atau jumlah elemen yang dicari sangat kecil. Sebaliknya,
Binary Search menawarkan kecepatan yang lebih baik dengan kompleksitas
O(log n), tetapi hanya dapat diterapkan jika data sudah terurut. Sementara
itu, Hash Search memberikan kecepatan terbaik dengan kompleksitas O(1)
dalam kondisi ideal. Namun, metode ini memerlukan memori tambahan
(O(n)) untuk menyimpan hash table, sehingga tidak selalu menjadi pilihan
paling efisien dalam hal penggunaan memori.
Dari hasil analisis dan pengujian yang dilakukan, terlihat bahwa Quick
Sort merupakan pilihan terbaik untuk algoritma sorting karena
kecepatannya yang superior dibandingkan dengan algoritma lainnya. Di sisi
lain, Hash Search muncul sebagai metode pencarian paling efisien dalam hal
waktu pencarian, asalkan tersedia cukup memori untuk menampung hash
table.
V.2 Saran
Untuk memilih algoritma yang paling sesuai dalam berbagai situasi,
berikut beberapa rekomendasi yang dapat penulis sampaikan:
48
KESIMPULAN DAN SARAN
V.1 Kesimpulan
Berdasarkan analisis efisiensi algoritma sorting dan searching yang
dilakukan dengan mempertimbangkan kompleksitas waktu dan ruang,
dapat disimpulkan bahwa pemilihan algoritma yang tepat sangat
dipengaruhi oleh jumlah data, kondisi awal data, serta kebutuhan akan
efisiensi waktu dan memori.
Dalam konteks algoritma sorting, Bubble Sort dan Selection Sort
memiliki kompleksitas waktu O(n²), yang membuat kedua algoritma ini
kurang efisien ketika diterapkan pada dataset besar. Meskipun Bubble Sort
dikenal karena kemudahan implementasinya, jumlah pertukaran elemen
yang tinggi membuat proses pengurutannya menjadi sangat lambat. Di sisi
lain, Selection Sort lebih efisien dalam hal pertukaran elemen, namun tetap
tidak dapat bersaing dengan Quick Sort, yang memiliki kompleksitas O(n log
n) dalam kondisi terbaik dan rata-rata. Hal ini menjadikan Quick Sort jauh
lebih cepat untuk pengolahan dataset besar.
Pada algoritma searching, Linear Search memiliki kompleksitas O(n),
sehingga tidak efisien untuk dataset besar, kecuali dalam situasi di mana
data tidak terurut atau jumlah elemen yang dicari sangat kecil. Sebaliknya,
Binary Search menawarkan kecepatan yang lebih baik dengan kompleksitas
O(log n), tetapi hanya dapat diterapkan jika data sudah terurut. Sementara
itu, Hash Search memberikan kecepatan terbaik dengan kompleksitas O(1)
dalam kondisi ideal. Namun, metode ini memerlukan memori tambahan
(O(n)) untuk menyimpan hash table, sehingga tidak selalu menjadi pilihan
paling efisien dalam hal penggunaan memori.
Dari hasil analisis dan pengujian yang dilakukan, terlihat bahwa Quick
Sort merupakan pilihan terbaik untuk algoritma sorting karena
kecepatannya yang superior dibandingkan dengan algoritma lainnya. Di sisi
lain, Hash Search muncul sebagai metode pencarian paling efisien dalam hal
waktu pencarian, asalkan tersedia cukup memori untuk menampung hash
table.
V.2 Saran
Untuk memilih algoritma yang paling sesuai dalam berbagai situasi,
berikut beberapa rekomendasi yang dapat penulis sampaikan:
48
a.Jika jumlah data kecil atau hampir terurut, Bubble Sort atau Selection
Sort masih dapat digunakan. Namun, untuk dataset yang lebih besar,
Quick Sort lebih dianjurkan karena efisiensinya yang lebih baik.
b.Apabila data tidak terurut dan jumlah elemennya kecil, Linear Search
bisa diterapkan. Namun, untuk data yang lebih besar, Binary Search
adalah pilihan yang lebih baik asalkan data tersebut telah diurutkan
sebelumnya.
c.Jika kecepatan pencarian menjadi prioritas utama dan tersedia memori
tambahan yang cukup, Hash Search merupakan pilihan terbaik karena
menawarkan waktu pencarian O(1) dalam kondisi ideal.
d.Saat menggunakan Binary Search, pastikan data telah diurutkan terlebih
dahulu, karena proses pengurutan dapat memengaruhi efisiensi
pencarian.
e.Dalam implementasi Quick Sort, penting untuk memperhatikan
pemilihan pivot yang tepat guna menghindari skenario terburuk dengan
kompleksitas O(n²). Jika diperlukan, strategi pemilihan pivot seperti
median-of-three atau randomized pivot selection dapat digunakan untuk
meningkatkan efisiensi.
Dengan memahami kelebihan dan kekurangan dari masing-masing
algoritma berdasarkan kompleksitas waktu dan ruang, diharapkan
pemilihan algoritma sorting dan searching dapat dilakukan secara lebih
optimal sesuai dengan kebutuhan dan kondisi data yang dihadapi.
49
Sort masih dapat digunakan. Namun, untuk dataset yang lebih besar,
Quick Sort lebih dianjurkan karena efisiensinya yang lebih baik.
b.Apabila data tidak terurut dan jumlah elemennya kecil, Linear Search
bisa diterapkan. Namun, untuk data yang lebih besar, Binary Search
adalah pilihan yang lebih baik asalkan data tersebut telah diurutkan
sebelumnya.
c.Jika kecepatan pencarian menjadi prioritas utama dan tersedia memori
tambahan yang cukup, Hash Search merupakan pilihan terbaik karena
menawarkan waktu pencarian O(1) dalam kondisi ideal.
d.Saat menggunakan Binary Search, pastikan data telah diurutkan terlebih
dahulu, karena proses pengurutan dapat memengaruhi efisiensi
pencarian.
e.Dalam implementasi Quick Sort, penting untuk memperhatikan
pemilihan pivot yang tepat guna menghindari skenario terburuk dengan
kompleksitas O(n²). Jika diperlukan, strategi pemilihan pivot seperti
median-of-three atau randomized pivot selection dapat digunakan untuk
meningkatkan efisiensi.
Dengan memahami kelebihan dan kekurangan dari masing-masing
algoritma berdasarkan kompleksitas waktu dan ruang, diharapkan
pemilihan algoritma sorting dan searching dapat dilakukan secara lebih
optimal sesuai dengan kebutuhan dan kondisi data yang dihadapi.
49
Tags
Categories
TechnologyDownload
Download Slideshow Get the original presentation fileQuick Actions
Statistics
- Views 156
- Slides 57
- Age 241 days
Related Slideshows
11
8-top-ai-courses-for-customer-support-representatives-in-2025.pptx
JeroenErne2
48 views
10
7-essential-ai-courses-for-call-center-supervisors-in-2025.pptx
JeroenErne2
47 views
13
25-essential-ai-courses-for-user-support-specialists-in-2025.pptx
JeroenErne2
37 views
11
8-essential-ai-courses-for-insurance-customer-service-representatives-in-2025.pptx
JeroenErne2
34 views
21
Know for Certain
DaveSinNM
22 views
17
PPT OPD LES 3ertt4t4tqqqe23e3e3rq2qq232.pptx
novasedanayoga46
26 views