Algoritma Pencarian dan Sorting dalam C++: Panduan Lengkap dengan Contoh Praktis
Pernah nggak sih kamu punya daftar kontak HP yang berantakan dan pengin nyari nomor temen tapi malah muter-muter scroll sana-sini? Atau mungkin kamu pengin urutin data nilai mahasiswa dari yang tertinggi ke terendah? Nah, di sinilah algoritma pencarian dan sorting jadi pahlawan! Dan ketika diimplementasikan dalam C++, mereka bekerja dengan kecepatan yang luar biasa.
Bayangkan algoritma pencarian dan sorting seperti taktik bermain game. Ketika inventory-mu berantakan, kamu butuh strategi sorting yang tepat untuk mengatur item-itemmu. Dan ketika mau cari senjata tertentu di tas yang penuh, kamu butuh teknik pencarian yang efisien. Tutorial ini bakal ngebongkar semua rahasia algoritma-algoritma ini dengan contoh kode C++ yang siap pakai. Kita akan bahas dari yang paling dasar sampai yang paling efisien, plus kapan harus pilih yang mana. Siap untuk upgrade skill programming-mu?
Mengapa Algoritma Pencarian dan Sorting itu Sangat Penting?
Sebelum masuk ke teknis, mari pahami dulu kenapa dua jenis algoritma ini fundamental dalam programming.
- Efisiensi: Dengan data yang terurut, pencarian jadi jauh lebih cepat. Bayangkan bedanya nyari kata dalam kamus yang urut abjad vs kamus acak-acakan.
- User Experience: Aplikasi yang menampilkan data terurut (harga produk dari termurah, artikel dari terbaru) lebih nyaman digunakan.
- Fundamental untuk Algoritma Lain: Banyak algoritma kompleks (seperti binary search) hanya bekerja pada data yang sudah terurut.
- Wawancara Kerja: Pertanyaan tentang algoritma ini sangat sering muncul dalam technical interview!
Algoritma Pencarian: Cara Cepat Menemukan Jarum di Tumpukan Jerami
Mari mulai dengan algoritma pencarian—cara menemukan elemen tertentu dalam kumpulan data.
1. Linear Search: Pencarian Sederhana yang Selalu Bekerja
Konsep: Memeriksa setiap elemen satu per satu secara berurutan sampai target ditemukan.
Analogi: Seperti mencari kunci di dalam tas—kamu mengeluarkan semua isinya satu per satu sampai ketemu.
Kompleksitas Waktu: O(n) – worst case harus periksa semua elemen.
Kelebihan: Sederhana, selalu bekerja (bahkan pada data tidak terurut).
Kekurangan: Lambat untuk data besar.
#include <iostream>
#include <vector>
using namespace std;
int linearSearch(const vector<int>& arr, int target) {
for(int i = 0; i < arr.size(); i++) {
if(arr[i] == target) {
return i; // Kembalikan index jika ditemukan
}
}
return -1; // Return -1 jika tidak ditemukan
}
int main() {
vector<int> numbers = {10, 25, 30, 45, 50, 65, 70};
int target = 45;
int result = linearSearch(numbers, target);
if(result != -1) {
cout << "Elemen " << target << " ditemukan pada index: " << result << endl;
} else {
cout << "Elemen " << target << " tidak ditemukan" << endl;
}
return 0;
}
2. Binary Search: Pencarian Super Cepat untuk Data Terurut
Konsep: Membagi area pencarian menjadi dua bagian di setiap langkah. Hanya bekerja pada data yang sudah terurut.
Analogi: Seperti mencari kata dalam kamus—langsung buka tengah, tentukan mau ke kiri atau kanan, lalu bagi lagi.
Kompleksitas Waktu: O(log n) – sangat efisien!
Kelebihan: Sangat cepat untuk data besar.
Kekurangan: Hanya bekerja pada data terurut.
#include <iostream>
#include <vector>
#include <algorithm> // untuk std::sort
using namespace std;
int binarySearch(const vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
while(left <= right) {
int mid = left + (right - left) / 2; // Hindari overflow
if(arr[mid] == target) {
return mid; // Elemen ditemukan
} else if(arr[mid] < target) {
left = mid + 1; // Cari di bagian kanan
} else {
right = mid - 1; // Cari di bagian kiri
}
}
return -1; // Elemen tidak ditemukan
}
int main() {
vector<int> numbers = {50, 25, 70, 10, 65, 30, 45};
// Data harus diurutkan dulu untuk binary search
sort(numbers.begin(), numbers.end());
// numbers sekarang: {10, 25, 30, 45, 50, 65, 70}
int target = 45;
int result = binarySearch(numbers, target);
if(result != -1) {
cout << "Elemen " << target << " ditemukan pada index: " << result << endl;
} else {
cout << "Elemen " << target << " tidak ditemukan" << endl;
}
return 0;
}
Algoritma Sorting: Seni Mengatur Kekacauan
Sekarang mari beralih ke algoritma sorting—cara mengurutkan data dari tidak teratur menjadi teratur.
1. Bubble Sort: Sorting Paling Sederhana
Konsep: Membandingkan dua elemen berdekatan dan menukarnya jika urutannya salah. Proses diulang hingga tidak ada lagi pertukaran.
Analogi: Seperti gelembung udara yang naik ke permukaan—elemen terbesar “menggelembung” ke posisi terakhir.
Kompleksitas Waktu: O(n²) – lambat untuk data besar.
Kelebihan: Sederhana, mudah dipahami.
Kekurangan: Sangat tidak efisien.
#include <iostream>
#include <vector>
using namespace std;
void bubbleSort(vector<int>& arr) {
int n = arr.size();
for(int i = 0; i < n-1; i++) {
// Flag untuk optimasi - jika tidak ada pertukaran, array sudah terurut
bool swapped = false;
for(int j = 0; j < n-i-1; j++) {
if(arr[j] > arr[j+1]) {
// Tukar elemen
swap(arr[j], arr[j+1]);
swapped = true;
}
}
// Jika tidak ada pertukaran dalam pass ini, array sudah terurut
if(!swapped) break;
}
}
int main() {
vector<int> numbers = {64, 34, 25, 12, 22, 11, 90};
cout << "Array sebelum sorting: ";
for(int num : numbers) {
cout << num << " ";
}
cout << endl;
bubbleSort(numbers);
cout << "Array setelah sorting: ";
for(int num : numbers) {
cout << num << " ";
}
cout << endl;
return 0;
}
2. Selection Sort: Memilih yang Terbaik
Konsep: Mencari elemen terkecil dan menukarnya dengan elemen pertama, lalu mencari elemen terkecil berikutnya dari sisa array, dst.
Kompleksitas Waktu: O(n²).
Kelebihan: Lebih sedikit pertukaran daripada bubble sort.
Kekurangan: Masih lambat untuk data besar.
#include <iostream>
#include <vector>
using namespace std;
void selectionSort(vector<int>& arr) {
int n = arr.size();
for(int i = 0; i < n-1; i++) {
// Cari elemen terkecil dalam sisa array
int minIndex = i;
for(int j = i+1; j < n; j++) {
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Tukar elemen terkecil dengan elemen pertama di sisa array
swap(arr[i], arr[minIndex]);
}
}
int main() {
vector<int> numbers = {64, 25, 12, 22, 11};
cout << "Sebelum: ";
for(int num : numbers) cout << num << " ";
cout << endl;
selectionSort(numbers);
cout << "Sesudah: ";
for(int num : numbers) cout << num << " ";
cout << endl;
return 0;
}
3. Insertion Sort: Seperti Mengurutkan Kartu
Konsep: Membangun array terurut satu per satu dengan mengambil elemen dari bagian tidak terurut dan memasukkannya ke posisi yang tepat di bagian terurut.
Analogi: Seperti mengurutkan kartu di tangan—ambil kartu baru dan sisipkan di posisi yang tepat.
Kompleksitas Waktu: O(n²) worst case, tapi O(n) best case (untuk data hampir terurut).
Kelebihan: Efisien untuk data kecil atau hampir terurut.
Kekurangan: Lambat untuk data besar yang acak.
#include <iostream>
#include <vector>
using namespace std;
void insertionSort(vector<int>& arr) {
int n = arr.size();
for(int i = 1; i < n; i++) {
int key = arr[i]; // Elemen yang akan disisipkan
int j = i - 1;
// Geser elemen yang lebih besar dari key ke kanan
while(j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key; // Sisipkan key di posisi yang tepat
}
}
int main() {
vector<int> numbers = {12, 11, 13, 5, 6};
cout << "Sebelum: ";
for(int num : numbers) cout << num << " ";
cout << endl;
insertionSort(numbers);
cout << "Sesudah: ";
for(int num : numbers) cout << num << " ";
cout << endl;
return 0;
}
Algoritma Sorting C++ Built-in: std::sort()
Dalam praktiknya, kamu biasanya akan menggunakan fungsi sorting bawaan C++ yang sudah sangat dioptimalkan.
#include <iostream>
#include <vector>
#include <algorithm> // untuk std::sort
using namespace std;
int main() {
vector<int> numbers = {64, 34, 25, 12, 22, 11, 90};
// Sorting ascending (default)
sort(numbers.begin(), numbers.end());
cout << "Ascending: ";
for(int num : numbers) cout << num << " ";
cout << endl;
// Sorting descending
sort(numbers.begin(), numbers.end(), greater<int>());
cout << "Descending: ";
for(int num : numbers) cout << num << " ";
cout << endl;
// Sorting dengan custom comparator
vector<string> names = {"Alice", "Bob", "Charlie", "David"};
sort(names.begin(), names.end(), [](const string& a, const string& b) {
return a.length() < b.length(); // Urutkan berdasarkan panjang string
});
cout << "Sorted by length: ";
for(const string& name : names) cout << name << " ";
cout << endl;
return 0;
}
Perbandingan Kompleksitas Algoritma
| Algoritma | Best Case | Average Case | Worst Case | Rekomendasi Penggunaan |
|---|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) | Data kecil/tidak terurut |
| Binary Search | O(1) | O(log n) | O(log n) | Data besar yang terurut |
| Bubble Sort | O(n) | O(n²) | O(n²) | Data sangat kecil, educational |
| Selection Sort | O(n²) | O(n²) | O(n²) | Data kecil, minim pertukaran |
| Insertion Sort | O(n) | O(n²) | O(n²) | Data kecil/hampir terurut |
| std::sort() | O(n log n) | O(n log n) | O(n log n) | Hampir semua kasus |
Studi Kasus: Aplikasi Manajemen Nilai Siswa
Mari terapkan pengetahuan kita dengan membuat sistem manajemen nilai sederhana.
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
struct Student {
string name;
int score;
};
// Fungsi untuk menampilkan daftar siswa
void displayStudents(const vector<Student>& students) {
cout << "\n--- DAFTAR NILAI SISWA ---" << endl;
for(const auto& student : students) {
cout << student.name << ": " << student.score << endl;
}
}
// Binary search untuk mencari siswa berdasarkan nama
int searchStudent(const vector<Student>& students, const string& targetName) {
int left = 0;
int right = students.size() - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(students[mid].name == targetName) {
return mid;
} else if(students[mid].name < targetName) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int main() {
vector<Student> students = {
{"Budi", 85},
{"Andi", 92},
{"Citra", 78},
{"Dewi", 95},
{"Eko", 88}
};
// Urutkan berdasarkan nama
sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
return a.name < b.name;
});
displayStudents(students);
// Cari siswa
string searchName = "Citra";
int index = searchStudent(students, searchName);
if(index != -1) {
cout << "\n" << searchName << " ditemukan! Nilai: " << students[index].score << endl;
} else {
cout << "\n" << searchName << " tidak ditemukan." << endl;
}
// Urutkan berdasarkan nilai (descending)
sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
return a.score > b.score;
});
cout << "\n--- RANKING BERDASARKAN NILAI ---" << endl;
for(int i = 0; i < students.size(); i++) {
cout << i+1 << ". " << students[i].name << ": " << students[i].score << endl;
}
return 0;
}
Kesimpulan: Pilih Alat yang Tepat untuk Pekerjaan yang Tepat
Menguasai algoritma pencarian dan sorting dalam C++ memberi kamu toolbox yang lengkap untuk menangani data dengan efisien. Kunci suksesnya adalah mengetahui kapan menggunakan algoritma yang tepat:
- Gunakan linear search untuk data kecil atau tidak terurut
- Gunakan binary search untuk data besar yang terurut
- Untuk sorting, dalam praktiknya std::sort() hampir selalu menjadi pilihan terbaik
- Pahami algoritma dasar untuk wawancara kerja dan memahami konsep
Ingat, programming yang baik bukan tentang menulis kode yang paling kompleks, tapi tentang memilih solusi yang paling efisien dan tepat untuk masalah yang dihadapi. Selamat berlatih!