Anak Males – Kita akan memahami konsep sorting di dalam C++. Seperti yang kita tau ada berbagai macam sorting jadi kita bahas satu persatu.
Sorting adalah proses pengurutan data dari yang terkecil hingga yang terbesar atau sebaliknya. Proses ini sangat penting dalam pemrograman komputer karena dapat mempermudah dalam mencari data atau melakukan analisis.
Dalam tutorial ini, kita akan membahas algoritma sorting yang populer dan cara implementasinya di C++. Tutorial ini ditujukan untuk pemula yang ingin belajar tentang sorting dan implementasinya di C++.
Prasyarat yang diperlukan adalah dasar-dasar pemrograman C++ dan pemahaman tentang array.
Tutorial ini akan membahas lima algoritma sorting yang populer, yaitu bubble sort, selection sort, insertion sort, merge sort, dan quick sort.
Kita akan membahas teori dari masing-masing algoritma dan cara implementasinya di C++. Selain itu, kita juga akan membandingkan kinerja dari masing-masing algoritma dan menentukan algoritma mana yang paling cocok untuk digunakan dalam situasi tertentu.
Tutorial ini akan membantu Anda untuk memahami dasar-dasar sorting dan membuat Anda lebih yakin dalam menentukan algoritma yang cocok untuk digunakan dalam proyek pemrograman Anda.
Setelah menyelesaikan tutorial ini, Anda akan dapat menentukan algoritma sorting yang paling cocok untuk digunakan dalam situasi tertentu dan mengimplementasikannya dengan baik di C++.
Macam Macam Algoritma Sorting di C++
Didalam pemrograman C++ ada beberapa macam algoritma sorting yang bisa dipelajari yaitu sebagai berikut ini :
- Bubble sort
- Selection sort
- Insertion sort
- Merge sort
- Quick sort
Mari kita bahas satu persatu.
Algoritma Sorting C++ “Bubble Sort”
Bubble Sort adalah salah satu algoritma sorting yang paling sederhana dan paling mudah dipahami. Algoritma ini mengiterasi melalui data yang akan diurutkan, membandingkan dua elemen berdekatan dan menukar posisi elemen jika diperlukan, hingga tidak ada lagi perubahan yang diperlukan.
Proses ini diulangi hingga semua elemen diurutkan.
Implementasi dari bubble sort di C++ dapat dilakukan dengan menggunakan perulangan for. Berikut adalah contoh implementasi bubble sort untuk mengurutkan sebuah array integer:
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
// menukar posisi elemen jika diperlukan
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
Dalam contoh di atas, fungsi bubbleSort menerima dua parameter: array yang akan diurutkan dan jumlah elemen dalam array tersebut.
Fungsi ini menggunakan dua perulangan for, yang pertama untuk iterasi melalui semua elemen dari array dan yang kedua untuk membandingkan dua elemen berdekatan.
Jika elemen kiri lebih besar dari elemen kanan, maka kedua elemen tersebut ditukar posisi. Proses ini diulangi hingga tidak ada lagi perubahan yang diperlukan.
Kekurangan dari bubble sort adalah kinerjanya yang buruk ketika datanya besar, karena ia harus melakukan perbandingan dan pertukaran berkali-kali.
Namun, bubble sort masih dapat digunakan untuk data yang sangat kecil atau data yang sudah hampir terurut.
Algoritma Sorting C++ “Selection sort”
Selection Sort adalah algoritma sorting yang mencari elemen terkecil dalam data yang belum diurutkan dan menempatkannya di posisi pertama dari data yang diurutkan.
Proses ini diulangi hingga semua elemen diurutkan. Algoritma ini juga mudah dipahami dan digunakan, tetapi lebih efisien dibandingkan dengan bubble sort.
Implementasi dari selection sort di C++ dapat dilakukan dengan menggunakan perulangan for. Berikut adalah contoh implementasi selection sort untuk mengurutkan sebuah array integer:
void selectionSort(int arr[], int n) {
int min_idx;
for (int i = 0; i < n-1; i++) {
min_idx = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// menukar posisi elemen yang terkecil dengan elemen pertama
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
Dalam contoh di atas, fungsi selectionSort menerima dua parameter: array yang akan diurutkan dan jumlah elemen dalam array tersebut.
Fungsi ini menggunakan dua perulangan for, yang pertama untuk iterasi melalui semua elemen dari array yang belum diurutkan dan yang kedua untuk mencari elemen terkecil dalam data yang belum diurutkan.
Jika elemen kiri lebih besar dari elemen kanan, maka kedua elemen tersebut ditukar posisi. Proses ini diulangi hingga semua elemen diurutkan.
Selection sort lebih efisien dibandingkan dengan bubble sort karena ia hanya melakukan pertukaran satu kali untuk setiap iterasi, sementara bubble sort melakukan pertukaran berkali-kali dalam setiap iterasi.
Namun, selection sort memerlukan perbandingan yang lebih banyak dibandingkan dengan bubble sort.
Algoritma Sorting C++ “Insertion sort”
Insertion Sort adalah algoritma sorting yang mencoba untuk menyusun data dengan cara seolah-olah menyusun kartu.
Algoritma ini memperlakukan data yang belum diurutkan sebagai satu kartu dan mencoba untuk menyusunnya dengan menyisipkan data tersebut ke dalam data yang sudah diurutkan. Algoritma ini sangat efisien untuk data yang sudah hampir diurutkan dan juga mudah diimplementasikan.
Implementasi dari insertion sort di C++ dapat dilakukan dengan menggunakan perulangan for. Berikut adalah contoh implementasi insertion sort untuk mengurutkan sebuah array integer:
void insertionSort(int arr[], int n) {
int key, j;
for (int i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
/* Pindahkan elemen yang lebih besar dari key,
satu posisi ke kanan dari j */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
Dalam contoh di atas, fungsi insertionSort menerima dua parameter: array yang akan diurutkan dan jumlah elemen dalam array tersebut.
Fungsi ini menggunakan perulangan for untuk iterasi melalui semua elemen dari array yang belum diurutkan. Dalam setiap iterasi, elemen yang akan diurutkan disimpan dalam variabel “key” dan dibandingkan dengan elemen sebelumnya.
Jika elemen sebelumnya lebih besar dari key, maka elemen tersebut dipindah satu posisi ke kanan dan proses terus dilakukan hingga elemen sebelumnya lebih kecil atau sama dengan key. Proses ini diulangi hingga semua elemen diurutkan.
Insertion sort sangat efisien untuk data yang sudah hampir terurut karena dia hanya memerlukan perbandingan dan pertukaran yang minimal. Namun, jika data tidak terurut, ia akan memerlukan waktu yang cukup lama untuk mengurutkannya.
Algoritma Sorting C++ “Merge Sort”
Merge Sort adalah algoritma sorting yang berdasarkan pada prinsip pembagian dan penaklukan (divide and conquer).
Algoritma ini membagi data menjadi dua bagian yang lebih kecil, masing-masing diurutkan secara terpisah, kemudian dua bagian tersebut digabungkan kembali menjadi satu data yang terurut. Algoritma ini sangat efisien dalam mengurutkan data yang besar karena ia membagi data menjadi bagian yang lebih kecil sebelum mengurutkannya.
Implementasi dari merge sort di C++ dapat dilakukan dengan menggunakan rekursi. Berikut adalah contoh implementasi merge sort untuk mengurutkan sebuah array integer:
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
// buat array sementara
int L[n1], R[n2];
// salin data ke array sementara
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// gabungkan array sementara kembali ke array utama
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// salin sisa data jika ada
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
Dalam contoh di atas, fungsi mergeSort menerima tiga parameter: array yang akan diurutkan, indeks awal dari array, dan indeks akhir dari array.
Fungsi ini menggunakan rekursi untuk membagi data menjadi bagian yang lebih kecil, kemudian mengurutkan masing-masing bagian dengan memanggil fungsi mergeSort secara rekursif.
Setelah masing-masing bagian diurutkan, fungsi merge digunakan untuk menggabungkan kembali masing-masing bagian menjadi satu data yang terurut.
Fungsi merge menerima empat parameter: array yang akan diurutkan, indeks awal dari array, indeks tengah dari array, dan indeks akhir dari array.
Fungsi ini membuat dua array sementara, yaitu L dan R, untuk menyimpan data dari bagian kiri dan kanan dari array yang akan diurutkan. Kemudian, data dari dua array sementara ini digabungkan kembali menjadi satu array yang terurut.
Merge sort sangat efisien dalam mengurutkan data yang besar karena ia membagi data menjadi bagian yang lebih kecil sebelum mengurutkannya.
Algoritma ini juga stabil, yaitu tidak merubah urutan dari elemen yang memiliki nilai yang sama. Namun, merge sort memerlukan ruang tambahan untuk menyimpan data sementara dan memerlukan beberapa operasi penyalinan data yang cukup banyak.
Algoritma Sorting C++ “Quick Sort”
Quick Sort adalah algoritma sorting yang berdasarkan pada prinsip pembagian dan penaklukan (divide and conquer) seperti merge sort.
Algoritma ini memilih satu elemen sebagai pivot, kemudian mengurutkan elemen lainnya dengan membandingkan elemen tersebut dengan pivot dan memindahkan elemen yang lebih kecil dari pivot ke satu sisi dan elemen yang lebih besar dari pivot ke sisi lainnya.
Proses ini diulangi untuk setiap bagian dari data yang dihasilkan hingga semua elemen diurutkan.
Implementasi dari quick sort di C++ dapat dilakukan dengan menggunakan rekursi. Berikut adalah contoh implementasi quick sort untuk mengurutkan sebuah array integer:
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high- 1; j++) {
if (arr[j] <= pivot) {
i++; // increment index of smaller element
//swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//swap arr[i + 1] and arr[high]
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i + 1);
}
void quickSort(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);
}
}
Dalam contoh di atas, fungsi quickSort menerima tiga parameter: array yang akan diurutkan, indeks awal dari array, dan indeks akhir dari array.
Fungsi ini menggunakan rekursi untuk membagi data menjadi bagian yang lebih kecil, kemudian mengurutkan masing-masing bagian dengan memanggil fungsi quickSort secara rekursif.
Setelah masing-masing bagian diurutkan, fungsi partition digunakan untuk memilih pivot dan mengurutkan elemen lainnya dengan membandingkan elemen tersebut dengan pivot.
Quick sort sangat efisien dalam mengurutkan data yang besar karena ia membagi data menjadi bagian yang lebih kecil sebelum mengurutkannya.
Algoritma ini juga sangat cepat dalam mengurutkan data acak. Namun, quick sort memiliki kelemahan yaitu jika pivot yang dipilih tidak baik maka dapat menyebabkan performa yang buruk.
Penutup
Baiklah, mungkin kita cukupkan untuk tutorial C++ kali ini, sampai jumpa di tutorial C++ lainnya.