Mempelajari Algoritma dan Struktur Data
Bagaimana sebuah program menyelesaikan masalah dan mengelola informasi? Pelajari hubungan antara algoritma, struktur data, efisiensi, dan penerapannya menggunakan C++.
Bayangkan kita diminta membuat sebuah program untuk mengelola nilai murid dalam satu kelas. Program tersebut harus mampu menyimpan banyak nilai, mencari nilai tertentu, mengurutkan nilai dari yang tertinggi, dan menghitung rata-rata kelas.
Sekilas, tugas tersebut terlihat seperti pekerjaan menulis beberapa baris kode. Namun, sebelum menulis kode, ada dua pertanyaan penting yang perlu dijawab:
1. Bagaimana program menyelesaikan masalah tersebut?
Apakah nilai diperiksa satu per satu? Apakah perlu diurutkan terlebih dahulu? Bagaimana langkah-langkah penyelesaiannya?
2. Bagaimana data nilai disimpan dan diatur?
Apakah setiap nilai disimpan dalam variabel terpisah? Apakah lebih baik menggunakan array atau struktur data lainnya?
Pertanyaan pertama berkaitan dengan algoritma, sedangkan pertanyaan kedua berkaitan dengan struktur data. Keduanya merupakan konsep penting dalam pemrograman karena program yang baik bukan hanya harus menghasilkan jawaban yang benar, tetapi juga perlu mengelola data dan menyelesaikan masalah secara efektif.
1. Memahami Apa Itu Algoritma
Sebelum mengenal struktur data, kita perlu memahami terlebih dahulu bagaimana sebuah program dapat menyelesaikan masalah.
Misalnya, kamu ingin mengetahui apakah nilai ujian seorang murid sudah mencapai batas ketuntasan. Jika batas ketuntasan adalah 75, tentu kamu dapat membandingkan nilai murid dengan angka tersebut.
Jika nilainya 85, hasilnya adalah tuntas. Jika nilainya 65, hasilnya belum tuntas.
Manusia dapat menyelesaikan persoalan sederhana tersebut secara spontan. Namun, komputer membutuhkan instruksi yang jelas dan tersusun agar dapat melakukan hal yang sama.
Pengertian Algoritma
Algoritma adalah urutan langkah-langkah logis dan sistematis yang dirancang untuk menyelesaikan suatu masalah atau mencapai tujuan tertentu.
Dalam pemrograman, algoritma menjadi rancangan penyelesaian masalah yang nantinya dapat diterjemahkan ke dalam bahasa pemrograman seperti C++.
Perhatikan contoh algoritma untuk menentukan kelulusan berdasarkan nilai:
Urutan tersebut merupakan algoritma sederhana. Ada masukan berupa nilai, proses perbandingan, kemudian keluaran berupa informasi ketuntasan.
Perhatikan bahwa algoritma belum tentu ditulis menggunakan bahasa pemrograman. Kita dapat menyusun algoritma menggunakan bahasa sehari-hari, pseudocode, atau flowchart terlebih dahulu.
2. Algoritma Bukan Sekadar Kode Program
Salah satu hal yang sering membingungkan pemula adalah menganggap algoritma sama dengan kode program. Padahal, keduanya memiliki peran yang berbeda.
Algoritma menjelaskan bagaimana suatu masalah diselesaikan, sedangkan kode program merupakan bentuk instruksi yang ditulis menggunakan bahasa pemrograman agar dapat dijalankan oleh komputer.
Misalnya, kita ingin menghitung rata-rata tiga nilai. Algoritmanya dapat ditulis seperti berikut:
Algoritma menghitung rata-rata
Setelah algoritma dipahami, kita dapat menerjemahkannya ke dalam C++.
#include <iostream>
using namespace std;
int main() {
double nilai1, nilai2, nilai3;
double rataRata;
cout << "Masukkan nilai pertama: ";
cin >> nilai1;
cout << "Masukkan nilai kedua: ";
cin >> nilai2;
cout << "Masukkan nilai ketiga: ";
cin >> nilai3;
rataRata = (nilai1 + nilai2 + nilai3) / 3;
cout << "Rata-rata: " << rataRata;
return 0;
}Program tersebut merupakan salah satu penerapan algoritma menghitung rata-rata. Algoritma yang sama juga dapat diterapkan menggunakan bahasa pemrograman lain, misalnya Python, Java, atau JavaScript.
Bahasa pemrograman dapat berbeda, tetapi algoritma penyelesaian masalahnya bisa tetap sama. Karena itu, belajar algoritma membantu kita memahami cara berpikir komputasional, bukan sekadar menghafalkan sintaks bahasa pemrograman.
3. Mengapa Algoritma Perlu Efisien?
Bayangkan kita memiliki daftar berisi 10 nama murid dan ingin mencari nama seseorang. Kita dapat memeriksa nama dari urutan pertama sampai menemukan nama yang dicari.
Bagaimana jika jumlahnya bukan 10, melainkan 10.000 atau bahkan 1.000.000 data?
Jika cara yang digunakan tetap sama, program mungkin harus memeriksa banyak data sebelum menemukan hasilnya. Inilah alasan mengapa efisiensi algoritma perlu diperhatikan.
Contoh: mencari sebuah angka dalam kumpulan data
Misalnya, kita memiliki kumpulan angka berikut:
Angka yang ingin dicari: 42
Cara pertama adalah memeriksa angka satu per satu dari awal. Cara ini disebut Linear Search.
Linear Search (Pencarian Linear)
Linear Search merupakan algoritma pencarian dengan cara memeriksa setiap elemen secara berurutan hingga data yang dicari ditemukan atau seluruh data selesai diperiksa.
Untuk contoh di atas, program memeriksa 12, kemudian 25, 37, dan akhirnya menemukan 42. Artinya, diperlukan empat kali pemeriksaan.
Cara kedua adalah menggunakan Binary Search. Namun, metode ini memiliki syarat: data harus sudah terurut.
Binary Search (Pencarian Biner)
Binary Search mencari data dengan membagi area pencarian menjadi dua bagian secara berulang. Program membandingkan data yang dicari dengan elemen tengah, lalu menentukan bagian mana yang masih perlu diperiksa.
Jika data lebih kecil dari elemen tengah, pencarian dilanjutkan ke bagian kiri. Jika lebih besar, pencarian dilanjutkan ke bagian kanan.
Perbedaan cara kerja kedua algoritma tersebut dapat menjadi sangat penting ketika jumlah data semakin besar.
Bagaimana Binary Search bekerja?
Misalnya, kita mencari angka 42 pada data terurut berikut:
1. Tentukan elemen tengah, yaitu 37.
2. Bandingkan 42 dengan 37. Karena 42 lebih besar, bagian kiri tidak perlu diperiksa lagi.
3. Periksa bagian kanan yang tersisa. Pada contoh ini, angka 42 ditemukan.
Semakin besar jumlah data terurut, semakin terasa keuntungan metode pembagian area pencarian ini.
4. Mengenal Kompleksitas Algoritma
Ketika membandingkan algoritma, kita tidak cukup hanya melihat berapa banyak baris kode yang ditulis. Kita juga perlu memperkirakan bagaimana kebutuhan waktu dan sumber daya program berubah ketika jumlah data bertambah.
Salah satu cara untuk menggambarkan pertumbuhan tersebut adalah menggunakan konsep kompleksitas algoritma. Dalam pembahasan dasar, kita sering mengenal istilah Big O Notation.
Apa itu Big O?
Big O merupakan notasi untuk menggambarkan bagaimana kebutuhan komputasi suatu algoritma bertumbuh terhadap ukuran input, terutama ketika ukuran data semakin besar.
Big O bukan angka pasti durasi eksekusi dalam detik. Notasi ini membantu kita membandingkan pola pertumbuhan algoritma.
Berikut beberapa kompleksitas yang sering dijumpai:
| Kompleksitas | Nama | Gambaran sederhana |
|---|---|---|
| O(1) | Konstan | Jumlah langkah relatif tetap. |
| O(log n) | Logaritmik | Jumlah langkah bertambah secara lambat saat data membesar. |
| O(n) | Linear | Jumlah langkah bertumbuh sebanding dengan jumlah data. |
| O(n log n) | Linear-logaritmik | Sering ditemukan pada algoritma pengurutan yang efisien. |
| O(n²) | Kuadratik | Jumlah langkah dapat bertumbuh jauh lebih cepat. |
Misalnya, sebuah algoritma O(n) memeriksa setiap data satu kali. Jika jumlah data bertambah sepuluh kali lipat, jumlah pemeriksaan juga kira-kira bertambah sepuluh kali lipat.
Sementara itu, algoritma O(n²) memiliki pertumbuhan yang lebih cepat. Jika jumlah data menjadi sepuluh kali lipat, skala operasinya dapat bertambah sekitar seratus kali lipat.
Kompleksitas bukan satu-satunya penentu kecepatan program. Perangkat keras, implementasi, jenis data, dan kondisi input juga berpengaruh. Namun, Big O membantu kita memahami karakteristik pertumbuhan algoritma secara lebih umum.
Contoh sederhana kompleksitas O(1), O(n), dan O(n²)
O(1): mengambil satu elemen array berdasarkan indeks.
int angka[5] = {10, 20, 30, 40, 50};
cout << angka[2];O(n): memeriksa seluruh elemen dalam array.
for (int i = 0; i < 5; i++) {
cout << angka[i] << endl;
}O(n²): menggunakan dua perulangan bersarang yang masing-masing berjalan mengikuti jumlah data.
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
cout << angka[i] << " ";
}
}Contoh terakhir menjalankan operasi di bagian dalam sebanyak 25 kali untuk ukuran data 5. Dalam kasus umum, pola dua perulangan penuh seperti ini memiliki kompleksitas O(n²).
5. Beralih ke Struktur Data: Bagaimana Informasi Disimpan?
Sekarang kita kembali ke persoalan awal: mengelola nilai murid dalam satu kelas.
Jika hanya ada satu nilai, kita bisa menyimpannya dalam satu variabel. Namun, jika terdapat 30, 100, atau 1.000 nilai, membuat variabel satu per satu tentu tidak praktis.
Kita membutuhkan cara untuk menyimpan dan mengatur sekumpulan data agar mudah diakses, diubah, dicari, atau diolah.
Pengertian Struktur Data
Struktur data adalah cara mengorganisasi dan menyimpan data di dalam komputer agar data tersebut dapat digunakan dan diolah secara efektif.
Setiap struktur data memiliki karakteristik dan cara penggunaan yang berbeda. Pemilihan struktur data akan memengaruhi bagaimana program mengakses, menambah, menghapus, dan mencari informasi.
Dalam C++, terdapat beberapa struktur data yang umum digunakan. Kita akan mulai dari yang paling sederhana.
A. Array: Menyimpan Banyak Data dengan Tipe yang Sama
Array memungkinkan kita menyimpan beberapa nilai dalam satu nama variabel. Setiap elemen memiliki indeks yang digunakan untuk mengakses posisinya.
Misalnya, kita ingin menyimpan lima nilai ujian:
Lima elemen dalam satu array
#include <iostream>
using namespace std;
int main() {
int nilai[5] = {80, 75, 90, 85, 88};
cout << "Nilai murid ketiga: " << nilai[2];
return 0;
}Perhatikan bahwa indeks array dimulai dari 0, bukan 1. Oleh karena itu, elemen ketiga berada pada indeks 2.
Array cocok digunakan ketika kita membutuhkan sekumpulan data dengan tipe yang sama dan jumlah elemennya sudah ditentukan.
B. Vector: Array yang Lebih Fleksibel
Array biasa memiliki ukuran yang ditentukan ketika dideklarasikan. Bagaimana jika jumlah data belum diketahui sejak awal?
Contohnya, program pendaftaran peserta lomba. Hari ini ada 10 pendaftar, tetapi besok jumlahnya mungkin bertambah menjadi 20 atau 100 orang.
Untuk situasi seperti ini, kita dapat menggunakan vector dari pustaka standar C++.
Apa itu Vector?
Vector adalah struktur data dalam C++ yang dapat menyimpan kumpulan elemen secara berurutan dan memungkinkan ukurannya bertambah atau berkurang selama program berjalan.
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> nilai;
nilai.push_back(80);
nilai.push_back(75);
nilai.push_back(90);
for (int i = 0; i < nilai.size(); i++) {
cout << nilai[i] << endl;
}
return 0;
}Perhatikan beberapa bagian penting:
(- ) #include <vector> digunakan untuk mengakses fasilitas vector.
(- ) vector<int> nilai; membuat vector bernama nilai yang menyimpan bilangan bulat.
(- ) push_back() menambahkan elemen baru di bagian akhir.
(- ) size() memberikan informasi jumlah elemen yang tersimpan.
Berbeda dengan array biasa yang ukurannya ditentukan sejak awal, vector dapat menyesuaikan jumlah elemennya sesuai kebutuhan program.
Beberapa operasi penting pada vector
| Operasi | Kegunaan |
|---|---|
push_back(x) | Menambahkan elemen x di akhir. |
pop_back() | Menghapus elemen terakhir. |
size() | Mengambil jumlah elemen. |
empty() | Memeriksa apakah vector kosong. |
clear() | Menghapus seluruh elemen. |
at(i) | Mengakses elemen dengan pemeriksaan batas indeks. |
C. Linked List: Data yang Terhubung
Array dan vector menyimpan elemen dalam urutan tertentu dan mendukung akses berdasarkan indeks. Namun, ada pendekatan lain dalam mengorganisasi data, yaitu menghubungkan setiap elemen dengan elemen berikutnya.
Pendekatan ini dikenal sebagai Linked List.
Apa itu Linked List?
Linked List adalah struktur data yang terdiri dari sejumlah elemen atau node. Setiap node menyimpan data dan informasi yang menghubungkannya dengan node lain.
Node 1
Node 2
Node 3
Ilustrasi sederhana Single Linked List
Berbeda dengan array, kita tidak mengakses elemen Linked List secara langsung menggunakan indeks. Kita perlu mengikuti hubungan dari satu node ke node berikutnya.
Linked List dapat memudahkan penyisipan atau penghapusan elemen pada posisi tertentu setelah node yang bersangkutan ditemukan. Namun, pencarian berdasarkan posisi umumnya perlu menelusuri node satu per satu.
Contoh bentuk node dalam C++
Untuk membuat Linked List sederhana, kita dapat menggunakan struct dan pointer.
struct Node {
int data;
Node* next;
};data menyimpan nilai, sedangkan next menyimpan alamat node berikutnya.
Konsep ini berkaitan erat dengan materi pointer dan reference dalam C++.
D. Stack: Data dengan Prinsip Terakhir Masuk, Pertama Keluar
Bayangkan kamu menumpuk beberapa buku di atas meja. Buku pertama diletakkan di bawah, buku kedua di atasnya, kemudian buku ketiga diletakkan paling atas.
Jika ingin mengambil buku tanpa merusak tumpukan, buku yang terakhir diletakkan harus diambil terlebih dahulu.
Prinsip tersebut dikenal sebagai Last In, First Out (LIFO).
Apa itu Stack?
Stack adalah struktur data yang menerapkan prinsip Last In, First Out. Elemen terakhir yang dimasukkan menjadi elemen pertama yang dikeluarkan.
Buku C berada paling atas sehingga diambil lebih dahulu.
Dalam C++, kita dapat menggunakan fasilitas stack dari pustaka standar.
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> data;
data.push(10);
data.push(20);
data.push(30);
cout << data.top() << endl;
data.pop();
cout << data.top() << endl;
return 0;
}Hasil program:
30
20Angka 30 ditampilkan terlebih dahulu karena berada di posisi paling atas. Setelah pop() dipanggil, angka 30 dikeluarkan dan angka 20 menjadi elemen teratas.
Stack dapat digunakan dalam berbagai kebutuhan, seperti fitur undo pada aplikasi, pengelolaan pemanggilan fungsi, dan evaluasi ekspresi matematika.
E. Queue: Data dengan Prinsip Pertama Masuk, Pertama Keluar
Sekarang bayangkan kamu sedang mengantre untuk membeli tiket. Orang yang datang lebih dahulu biasanya dilayani lebih dahulu.
Orang yang baru datang harus menunggu di belakang antrean. Prinsip ini dikenal sebagai First In, First Out (FIFO).
Apa itu Queue?
Queue adalah struktur data yang menerapkan prinsip First In, First Out. Elemen yang dimasukkan lebih dahulu akan dikeluarkan lebih dahulu.
Keluar dulu
Masuk terakhir
Urutan antrean dari depan ke belakang
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> antrean;
antrean.push(10);
antrean.push(20);
antrean.push(30);
cout << antrean.front() << endl;
antrean.pop();
cout << antrean.front() << endl;
return 0;
}Hasil program:
10
20Angka 10 keluar lebih dahulu karena dimasukkan pertama kali. Setelah itu, angka 20 menjadi elemen paling depan.
Queue dapat digunakan untuk mengatur antrean layanan, tugas pencetakan dokumen, dan proses yang perlu dijalankan berdasarkan urutan kedatangan.
F. Map: Menyimpan Data Berdasarkan Kunci
Bayangkan kita ingin menyimpan nilai murid berdasarkan nama. Kita ingin dapat mencari nilai seseorang dengan menggunakan namanya, bukan dengan mengingat posisi data di dalam array.
Untuk kebutuhan seperti ini, C++ menyediakan struktur data map.
Apa itu Map?
Map merupakan struktur data yang menyimpan pasangan antara kunci (key) dan nilai (value). Setiap kunci bersifat unik dalam satu map.
| Key (Nama) | Value (Nilai) |
|---|---|
| Andi | 85 |
| Siti | 92 |
| Budi | 78 |
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
map<string, int> nilai;
nilai["Andi"] = 85;
nilai["Siti"] = 92;
nilai["Budi"] = 78;
cout << "Nilai Siti: "
<< nilai["Siti"];
return 0;
}Program tersebut menyimpan nama sebagai kunci dan nilai ujian sebagai data yang terkait. Ketika kita membutuhkan nilai Siti, kita dapat mengaksesnya melalui nilai["Siti"].
Map berguna ketika kita membutuhkan pencarian berdasarkan identitas atau kunci tertentu, bukan sekadar posisi elemen.
Apa perbedaan map dan unordered_map?
C++ juga menyediakan unordered_map. Perbedaannya antara lain:
(- ) map menyimpan pasangan key-value dalam urutan berdasarkan kunci dan umumnya menggunakan struktur pohon seimbang.
(- ) unordered_map tidak menjamin urutan berdasarkan kunci dan umumnya menggunakan hash table.
Keduanya dapat digunakan untuk mencari data berdasarkan key, tetapi karakteristik dan kompleksitas operasinya berbeda.
G. Set: Menyimpan Data yang Unik
Misalnya, sebuah program ingin mencatat daftar kode peserta yang sudah mendaftar. Satu kode peserta tidak boleh tercatat lebih dari satu kali.
Kita dapat menggunakan struktur data set.
Apa itu Set?
Set adalah struktur data yang menyimpan kumpulan elemen unik. Jika kita mencoba memasukkan elemen yang sama lebih dari satu kali, set hanya menyimpan satu salinannya.
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> nomor;
nomor.insert(10);
nomor.insert(20);
nomor.insert(10);
nomor.insert(30);
for (int x : nomor) {
cout << x << endl;
}
return 0;
}Hasilnya:
10
20
30Angka 10 hanya muncul satu kali karena set tidak menyimpan duplikasi. Pada set biasa, elemen juga disajikan dalam urutan terurut berdasarkan aturan perbandingannya.
6. Memahami Perbedaan Berbagai Struktur Data
Setelah mengenal beberapa struktur data, mungkin muncul pertanyaan: mana yang paling baik digunakan?
Jawabannya bergantung pada kebutuhan program. Tidak ada satu struktur data yang selalu menjadi pilihan terbaik untuk semua masalah.
| Struktur Data | Karakteristik | Contoh Penggunaan |
|---|---|---|
| Array | Ukuran tetap, akses berdasarkan indeks. | Daftar nilai dengan jumlah tetap. |
| Vector | Urutan elemen dinamis, akses berdasarkan indeks. | Daftar peserta yang terus bertambah. |
| Linked List | Node saling terhubung. | Data yang sering disisipkan atau dihapus pada posisi tertentu. |
| Stack | LIFO. | Undo, riwayat pemanggilan fungsi. |
| Queue | FIFO. | Antrean layanan atau tugas. |
| Map | Pasangan key-value. | Pencarian nilai berdasarkan nama. |
| Set | Elemen unik. | Menyimpan kode tanpa duplikasi. |
Contohnya, jika kita ingin mengambil data berdasarkan posisi tertentu, vector dapat menjadi pilihan yang praktis. Jika kita ingin mengelola antrean, queue lebih sesuai. Jika kita membutuhkan data unik, set dapat membantu.
Memilih struktur data bukan sekadar memilih yang paling mudah ditulis. Kita perlu mempertimbangkan operasi yang paling sering dilakukan oleh program, seperti pencarian, penambahan, penghapusan, dan pengurutan.
7. Algoritma dan Struktur Data Saling Berkaitan
Sampai di sini, kita sudah mempelajari algoritma sebagai langkah penyelesaian masalah dan struktur data sebagai cara mengorganisasi informasi.
Keduanya sebenarnya tidak berdiri sendiri. Algoritma bekerja dengan memanfaatkan struktur data untuk mengolah informasi.
Mari kembali ke contoh pengelolaan nilai murid.
Misalnya, kita ingin membuat program yang dapat:
(- ) Menyimpan nilai seluruh murid.
(- ) Menampilkan seluruh nilai.
(- ) Menghitung rata-rata kelas.
(- ) Mencari nilai tertinggi.
(- ) Menentukan apakah suatu nilai tertentu terdapat dalam daftar.
Kita dapat menggunakan vector sebagai tempat penyimpanan data, kemudian menerapkan algoritma perulangan untuk menghitung rata-rata dan mencari nilai tertinggi.
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> nilai = {80, 75, 90, 85, 88};
int total = 0;
int tertinggi = nilai[0];
// Mengolah seluruh data
for (int i = 0; i < nilai.size(); i++) {
total += nilai[i];
if (nilai[i] > tertinggi) {
tertinggi = nilai[i];
}
}
double rataRata =
static_cast<double>(total) / nilai.size();
cout << "Jumlah murid: "
<< nilai.size() << endl;
cout << "Rata-rata: "
<< rataRata << endl;
cout << "Nilai tertinggi: "
<< tertinggi << endl;
return 0;
}Program tersebut menggunakan dua konsep sekaligus:
Struktur Data
vector<int> digunakan untuk menyimpan kumpulan nilai murid dalam satu wadah.
Algoritma
Perulangan for digunakan untuk memeriksa seluruh nilai. Di dalamnya terdapat proses penjumlahan dan perbandingan untuk menentukan nilai tertinggi.
Dengan demikian, struktur data menyediakan tempat untuk menyimpan informasi, sedangkan algoritma menentukan bagaimana informasi tersebut diproses untuk menghasilkan jawaban.
8. Mengenal Algoritma Pengurutan (Sorting)
Selain mencari dan menghitung data, program juga sering perlu mengurutkan informasi.
Misalnya, daftar nilai murid ingin ditampilkan dari nilai terkecil ke terbesar. Jika datanya hanya tiga atau empat, kita mungkin dapat mengurutkannya secara manual. Namun, bagaimana jika jumlahnya ratusan atau ribuan?
Komputer membutuhkan algoritma pengurutan atau sorting algorithm.
Apa itu Sorting?
Sorting adalah proses menyusun sekumpulan data berdasarkan aturan tertentu, misalnya dari nilai terkecil ke terbesar (ascending) atau dari terbesar ke terkecil (descending).
Ada berbagai algoritma pengurutan. Beberapa di antaranya adalah:
Bubble Sort
Membandingkan dua elemen yang berdekatan dan menukarnya jika urutannya tidak sesuai. Proses tersebut diulang sampai data tersusun.
Mudah dipahami O(n²) rata-rata dan terburukSelection Sort
Mencari elemen terkecil dari bagian data yang belum terurut, kemudian menempatkannya pada posisi yang tepat.
Konsep sederhana O(n²)Insertion Sort
Menyisipkan setiap elemen ke posisi yang tepat dalam bagian data yang sudah terurut. Metode ini dapat bekerja cukup baik pada kumpulan data kecil atau hampir terurut.
Cocok untuk data kecil O(n²) rata-rata dan terburukMerge Sort
Membagi data menjadi bagian-bagian lebih kecil, mengurutkan setiap bagian, kemudian menggabungkannya kembali dalam keadaan terurut.
Divide and Conquer O(n log n)Dalam C++, kita tidak selalu harus membuat algoritma pengurutan dari awal. Pustaka standar C++ menyediakan fungsi sort() yang dapat digunakan untuk mengurutkan data.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> nilai = {80, 75, 90, 85, 88};
sort(nilai.begin(), nilai.end());
for (int x : nilai) {
cout << x << " ";
}
return 0;
}Hasilnya:
75 80 85 88 90Untuk mengurutkan dari terbesar ke terkecil, kita dapat menggunakan greater<int>().
sort(nilai.begin(), nilai.end(), greater<int>());Fungsi sort() pada pustaka standar C++ umumnya memiliki kompleksitas O(n log n). Untuk mempelajari cara kerja setiap algoritma secara lebih mendalam, kita tetap perlu memahami proses di baliknya.
9. Bagaimana Memilih Algoritma dan Struktur Data?
Ketika membuat program, kita sering dihadapkan pada beberapa pilihan. Sebuah masalah mungkin dapat diselesaikan menggunakan lebih dari satu algoritma atau struktur data.
Untuk menentukan pilihan, kita perlu memahami karakteristik masalah yang akan diselesaikan.
Contoh 1: Menyimpan daftar nilai murid
Jika jumlah murid sudah diketahui dan tidak berubah, array dapat digunakan. Jika jumlah data dapat bertambah atau berkurang, vector lebih fleksibel.
Contoh 2: Mengelola antrean pendaftaran
Jika orang harus dilayani sesuai urutan kedatangan, queue merupakan struktur data yang sesuai karena menerapkan prinsip FIFO.
Contoh 3: Mencari data berdasarkan nama
Jika program sering mencari nilai berdasarkan nama murid, map dapat menjadi pilihan karena data disimpan sebagai pasangan key-value.
Contoh 4: Mencari angka dalam data yang sudah terurut
Jika data sudah terurut dan jumlahnya besar, Binary Search dapat menjadi pilihan yang lebih efisien dibandingkan Linear Search.
Secara umum, beberapa pertanyaan berikut dapat membantu menentukan pilihan:
(- ) Apakah data memiliki jumlah tetap atau dapat berubah?
(- ) Apakah data lebih sering dicari, ditambahkan, dihapus, atau diurutkan?
(- ) Apakah urutan data perlu dipertahankan?
(- ) Apakah data harus unik atau boleh memiliki nilai yang sama?
(- ) Seberapa besar jumlah data yang akan diproses?
Dengan mempertimbangkan hal tersebut, kita dapat membuat program yang lebih sesuai dengan kebutuhan, bukan sekadar program yang berhasil dijalankan.
10. Latihan Pemahaman
Setelah mempelajari algoritma dan struktur data, coba jawab beberapa pertanyaan berikut untuk menguji pemahamanmu.
A. Kumpulan perangkat keras komputer
B. Urutan langkah logis untuk menyelesaikan masalah
C. Tempat menyimpan seluruh data
D. Bahasa yang digunakan untuk membuat komputer
Lihat pembahasan
Jawaban: B. Algoritma merupakan urutan langkah logis dan sistematis untuk menyelesaikan suatu masalah.
A. Queue
B. Array
C. Stack
D. Map
Lihat pembahasan
Jawaban: C. Stack menggunakan prinsip LIFO, yaitu data yang terakhir dimasukkan akan dikeluarkan terlebih dahulu.
A. Map
B. Stack
C. Queue
D. Set
Lihat pembahasan
Jawaban: A. Map menyimpan data dalam bentuk pasangan key-value, misalnya nama sebagai key dan nilai sebagai value.
A. Agar komputer dapat menghapus data
B. Agar pencarian dapat menentukan bagian mana yang tidak perlu diperiksa
C. Agar semua data memiliki nilai sama
D. Agar jumlah data selalu tetap
Lihat pembahasan
Jawaban: B. Binary Search menggunakan perbandingan terhadap elemen tengah untuk mempersempit area pencarian. Proses ini hanya dapat dilakukan dengan benar jika data terurut.
A. Stack
B. Set
C. Queue
D. Map
Lihat pembahasan
Jawaban: C. Queue menerapkan prinsip FIFO sehingga peserta yang mendaftar lebih dahulu akan diproses lebih dahulu.
11. Tantangan Praktik: Membuat Program Pengelolaan Nilai
Sekarang saatnya menggabungkan konsep algoritma dan struktur data ke dalam sebuah program sederhana.
Buatlah program C++ untuk mengelola nilai beberapa murid menggunakan vector. Program tersebut harus memiliki kemampuan berikut:
Ketentuan program
(- ) Meminta pengguna memasukkan jumlah nilai yang akan disimpan.
(- ) Menerima nilai dari pengguna dan menyimpannya dalam vector.
(- ) Menampilkan seluruh nilai yang sudah dimasukkan.
(- ) Menghitung rata-rata nilai.
(- ) Menentukan nilai tertinggi dan terendah.
(- ) Mengurutkan nilai dari yang terkecil ke terbesar.
Petunjuk konsep yang dapat digunakan:
(- ) Gunakan vector<int> untuk menyimpan nilai.
(- ) Gunakan push_back() untuk menambahkan nilai.
(- ) Gunakan perulangan untuk memproses seluruh data.
(- ) Gunakan sort() dari pustaka <algorithm> untuk mengurutkan data.
Lihat petunjuk tambahan jika mengalami kesulitan
Untuk menghitung rata-rata, jumlahkan seluruh elemen kemudian bagi dengan jumlah data.
Untuk mencari nilai tertinggi dan terendah, kamu dapat membandingkan setiap elemen dengan nilai sementara.
Jangan lupa memeriksa jumlah data agar tidak membagi dengan nol ketika vector kosong.
Untuk mengurutkan nilai, pelajari penggunaan sort() pada bagian sebelumnya.
12. Kesimpulan: Program yang Baik Dimulai dari Cara Berpikir yang Tepat
Ketika seseorang mulai belajar pemrograman, perhatian biasanya tertuju pada sintaks dan cara menulis kode. Namun, semakin kompleks program yang dibuat, semakin penting kemampuan untuk merancang penyelesaian masalah dan mengelola data.
Algoritma membantu kita menentukan langkah-langkah untuk menyelesaikan masalah. Struktur data membantu kita menyimpan dan mengorganisasi informasi agar dapat diolah dengan tepat.
Keduanya saling melengkapi. Algoritma yang baik membutuhkan cara pengelolaan data yang sesuai, sementara pemilihan struktur data juga perlu mempertimbangkan operasi yang akan dilakukan oleh algoritma.
Hal utama yang perlu diingat
(- ) Algoritma adalah urutan langkah logis untuk menyelesaikan masalah.
(- ) Efisiensi algoritma berkaitan dengan pertumbuhan kebutuhan komputasi ketika jumlah data bertambah.
(- ) Struktur data adalah cara mengorganisasi dan menyimpan data.
(- ) Array, vector, Linked List, Stack, Queue, Map, dan Set memiliki karakteristik berbeda.
(- ) Algoritma dan struktur data bekerja bersama untuk membangun program yang efektif.
Dengan memahami kedua konsep ini, kita tidak lagi hanya belajar bagaimana menulis instruksi menggunakan C++, tetapi juga mulai belajar bagaimana merancang solusi komputasi yang lebih terstruktur dan efisien.
0 comments:
Posting Komentar