Sorting adalah proses pengurutan elemen data dalam urutan tertentu (ascending atau descending). Berikut adalah implementasi dasar Bubble Sort, Merge Sort, dan Quick Sort di C++.
1. Bubble Sort
Bubble Sort adalah algoritma sorting sederhana di mana elemen-elemen bertukar posisi secara berurutan hingga array tersortir.
Kompleksitas:
- Waktu: O(n2) (rata-rata dan terburuk).
- Ruang: O(1) (in-place).
Implementasi:
#include <iostream>
#include <vector>
using namespace std;
void bubbleSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) break; // Optimisasi jika array sudah tersortir
}
}
void printArray(const vector<int>& arr) {
for (int num : arr) {
cout << num << " ";
}
cout << endl;
}
int main() {
vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
cout << "Original array: ";
printArray(arr);
bubbleSort(arr);
cout << "Sorted array: ";
printArray(arr);
return 0;
}2. Merge Sort
Merge Sort adalah algoritma berbasis divide-and-conquer yang membagi array menjadi dua bagian, mengurutkan masing-masing bagian, dan kemudian menggabungkannya.
Kompleksitas:
- Waktu: O(nlog n) (rata-rata, terbaik, dan terburuk).
- Ruang: O(n)O(n) (tidak in-place).
Implementasi:
#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
vector<int> L(n1), R(n2);
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1) {
arr[k++] = L[i++];
}
while (j < n2) {
arr[k++] = R[j++];
}
}
void mergeSort(vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
void printArray(const vector<int>& arr) {
for (int num : arr) {
cout << num << " ";
}
cout << endl;
}
int main() {
vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
cout << "Original array: ";
printArray(arr);
mergeSort(arr, 0, arr.size() - 1);
cout << "Sorted array: ";
printArray(arr);
return 0;
}3. Quick Sort
Quick Sort adalah algoritma berbasis divide-and-conquer yang memilih pivot, kemudian mempartisi array sehingga elemen yang lebih kecil dari pivot ada di kiri dan yang lebih besar di kanan.
Kompleksitas:
- Waktu: O(nlog n) (rata-rata), O(n2) (terburuk jika pivot dipilih buruk).
- Ruang: O(log n) (rekursi).
Implementasi:
#include <iostream>
#include <vector>
using namespace std;
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void printArray(const vector<int>& arr) {
for (int num : arr) {
cout << num << " ";
}
cout << endl;
}
int main() {
vector<int> arr = {10, 7, 8, 9, 1, 5};
cout << "Original array: ";
printArray(arr);
quickSort(arr, 0, arr.size() - 1);
cout << "Sorted array: ";
printArray(arr);
return 0;
}Perbandingan Ketiga Algoritma
| Kriteria | Bubble Sort | Merge Sort | Quick Sort |
|---|---|---|---|
| Kompleksitas Waktu | O(n2) | O(n log n) | O(nlogn) (avg), O(n2) (worst) |
| Kompleksitas Ruang | O(1) (in-place) | O(n) (tidak in-place) | O(logn) (rekursif) |
| Stabilitas | Stabil | Stabil | Tidak stabil |
| Kesederhanaan | Sederhana | Kompleks | Kompleks |
Jika Anda ingin menjelajahi algoritma lain atau memahami detail tambahan, beri tahu saya! 😊
Leave a Reply