Latihan kode program C++ kali ini akan membahas cara mengurutkan angka menggunakan algoritma quick sort. Algoritma sorting banyak dipakai dalam pembahasan materi algoritma dasar di kampus-kampus IT.
Soal Mengurutkan Angka dengan Algoritma Quick Sort
Buatlah kode program C++ untuk mengurutkan angka menggunakan algoritma quick sort. Program meminta 1 nilai input untuk menentukan jumlah angka yang akan diurutkan, kemudian user memasukkan angka tersebut satu per satu. Setelah itu program menampilkan hasil urutan dari nilai terkecil ke terbesar (ascending).
Berikut contoh tampilan akhir yang diinginkan (1):
## Program C++ Mengurutkan Angka (Quick Sort) ## ================================================= Input jumlah element array: 4 Input 4 angka (dipisah dengan enter): Angka ke-1: 12 Angka ke-2: 78 Angka ke-3: 66 Angka ke-4: 90 Array setelah diurutkan: 12 66 78 90
Berikut contoh tampilan akhir yang diinginkan (2):
## Program C++ Mengurutkan Angka (Quick Sort) ## ================================================= Input jumlah element array: 8 Input 8 angka (dipisah dengan enter): Angka ke-1: 23 Angka ke-2: 56 Angka ke-3: 34 Angka ke-4: 88 Angka ke-5: 11 Angka ke-6: 98 Angka ke-7: 51 Angka ke-8: 29 Array setelah diurutkan: 11 23 29 34 51 56 88 98
Silahkan coba sebentar membuat kode program ini.
Tips Membuat Kode Program Mengurutkan Angka
Soal ini melatih pemahaman terkait array dan algoritma sorting. Berikut tutorial pendahuluan yang bisa diikuti:
- Pengertian Variabel dalam Bahasa C++
- Tipe Data Array Bahasa C++
- Perulangan FOR Bahasa C++
- Perulangan WHILE Bahasa C++
Setiap angka yang akan diurutkan perlu di simpan ke dalam sebuah array. Array inilah yang akan kita proses menggunakan algoritma quick sort.
# Pengertian Algoritma Quick Sort
Quick sort adalah algoritma pengurutan yang menggunakan pendekatan divide and conquer. Algoritma ini ditemukan oleh Tony Hoare pada tahun 1960.
Algoritma quick sort bekerja dengan memilih sebuah element pivot dari array dan mempartisi atau membagi array menjadi dua bagian, yaitu bagian kiri yang berisi element-element yang lebih kecil dari pivot, dan bagian kanan yang berisi element-element yang lebih besar dari pivot. Kemudian, algoritma ini secara rekursif mengurutkan kedua bagian tersebut hingga seluruh array terurut.
Algoritma quick sort memiliki langkah-langkah sebagai berikut:
- Pilih sebuah element pivot dari array. Element pivot bisa dipilih secara acak, atau bisa juga dipilih dari element terakhir.
- Potong array menjadi dua bagian berdasarkan pivot. Bagian kiri berisi element-element yang lebih kecil dari pivot, sedangkan bagian kanan berisi element-element yang lebih besar dari pivot. Pada langkah ini, element-element yang lebih kecil ditempatkan di sebelah kiri pivot, dan element-element yang lebih besar ditempatkan di sebelah kanan pivot. Pivot sendiri akan berada di posisi yang tepat setelah partisi.
- Secara rekursif, lakukan langkah 1 dan 2 pada kedua bagian array yang sudah dipartisi. Terus lakukan rekursi hingga kedua bagian array hanya memiliki satu element, yang berarti bagian tersebut sudah terurut.
- Setelah kedua bagian array terurut, gabung kembali kedua bagian tersebut untuk mendapatkan array yang sudah terurut secara keseluruhan.
Ilustrasi cara kerja algoritma quick sort
Kelebihan algoritma quick sort:
- Quick sort memiliki kompleksitas waktu O(n log n) dalam kasus terbaik dan terburuk, sehingga algoritma ini efisien untuk mengurutkan array berukuran besar.
- Quick sort adalah algoritma yang stabil, yang berarti urutan element yang sama akan tetap sama setelah diurutkan.
Kekurangan algoritma quick sort:
- Algoritma quick sort cukup kompleks dan agak susah dipahami.
- Quick sort butuh ruang tambahan untuk menyimpan array sementara.
Secara umum, algoritma quick sort cocok digunakan untuk mengurutkan array berukuran besar.
Kode Program C++ Mengurutkan Angka dengan Algoritma Quick Sort
Berikut salah satu solusi dari soal mengurutkan angka array dengan algoritma quick sort menggunakan bahasa pemrograman C++:
#include <iostream>
using namespace std;
// Buat function dengan algoritma quick sort
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high) {
// Pilih element pivot
int pivot = arr[high];
// Indeks element pertama yang lebih besar dari pivot
int i = (low - 1);
// Perulangan untuk membandingkan element dengan pivot
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
// Swap pivot dengan element ke-i
swap(&arr[i + 1], &arr[high]);
// Return indeks pivot
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
// Jika array hanya memiliki satu elemen, maka array itu sudah terurut
if (low >= high) {
return;
}
// Pilih pivot
int pi = partition(arr, low, high);
// Urutkan bagian kiri dari pivot
quickSort(arr, low, pi - 1);
// Urutkan bagian kanan dari pivot
quickSort(arr, pi + 1, high);
}
int main() {
cout << "## Program C++ Mengurutkan Angka (Quick Sort) ##" << endl;
cout << "=================================================" << endl;
cout << endl;
int i, n;
// Baca angka input dari user
cout << "Input jumlah element array: ";
cin >> n;
cout << endl;
int arr[n];
cout << "Input "<< n << " angka (dipisah dengan enter): ";
cout << endl;
for(i = 0; i < n; i++){
cout << "Angka ke-" << i+1 <<": ";
cin >> arr[i];
}
// Urutkan array dengan algoritma merge sort
quickSort(arr, 0, n - 1);
// Tampilan hasil pengurutan
cout << endl;
cout << "Array setelah diurutkan: ";
for (i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
Pada awal kode program di baris 5-9 terdapat deklarasi fungsi swap(). Fungsi ini menerima dua pointer ke element array (a dan b) dan dipakai untuk menukar nilai antara dua element tersebut.
Selanjutnya di ikuti dengan pendefinisian fungsi partition() di baris 11-31. Fungsi ini menerima tiga parameter, yaitu array yang akan diurutkan (arr), indeks awal (low), dan indeks akhir (high).
Fungsi partition() dipakai untuk melakukan partisi pada array dengan memilih element pivot dan membagi array menjadi dua bagian, yaitu bagian kiri yang berisi element-element yang lebih kecil dari pivot, dan bagian kanan yang berisi element-element yang lebih besar dari pivot.
Fungsi ini menggunakan variabel i untuk melacak indeks element pertama yang lebih besar dari pivot. Pada setiap iterasi, bandingkan element saat ini dengan pivot. Jika element itu lebih kecil atau sama dengan pivot, maka element tersebut ditukar dengan element di posisi i, dan i diperbarui.
Setelah selesai melakukan perulangan, pivot ditukar dengan element di posisi i + 1, sehingga pivot berada di posisi yang tepat di dalam array. Fungsi ini mengembalikan indeks pivot.
Di baris 33-47 terdapat fungsi quickSort() yang bisa menerima tiga parameter, yaitu array yang akan diurutkan (arr), indeks awal (low), dan indeks akhir (high).
Fungsi quickSort() ini merupakan implementasi rekursif dari algoritma Quick Sort. Di awal, lakukan pengecekan apakah indeks awal lebih besar atau sama dengan indeks akhir. Jika iya, maka array tersebut sudah terurut dan fungsi berhenti. Jika tidak, fungsi ini memanggil fungsi partition() untuk memperoleh indeks pivot.
Setelah itu, fungsi quickSort() dipanggil secara rekursif untuk mengurutkan bagian kiri dan bagian kanan array. Dengan melakukan rekursi, fungsi ini mengurutkan seluruh array secara keseluruhan.
Masuk ke dalam kode program utama, di baris 57-58 user diminta untuk menginput jumlah angka yang ingin diurutkan. Angka ini akan disimpan ke dalam variabel n.
Kode program lalu membuat array sejumlah n dengan perintah int arr[n] di baris 61. Perulangan for dipakai untuk membaca setiap data dan disimpan ke dalam variabel arr.
Algoritma quick sort dijalankan dengan memanggil fungsi quickSort(arr, 0, n - 1).
Hasilnya, variabel arr akan berisi array yang sudah terurut, untuk selanjutnya ditampilkan dengan perulangan for di baris 76-78.
Itulah bahasan kita tentang implementasi algoritma sorting quick sort dalam bahasa pemrograman C++. Algoritma ini memang lebih kompleks jika dibandingkan algoritma sorting lain seperti bubble sort dan selection sort.
Semoga latihan soal ini bisa bermanfaat.