Sorting

Dalam algoritma pemrograman dikenal juga istilah sorting atau pengurutan. Ada beberapa pengurutan yang umum digunakan, antara lain sebagai berikut :

1. Bubble Sort

Pengurutan ini menggunakan pengulangan bersarang untuk mengurutkan. Kompleksitasnya O(N^2). Kalau anda baru mempelajari sort, sebaiknya anda mempelajari ini terlebih dahulu.

Kode :

#include <iostream>
using namespace std;
//membuat method bernama bubblesort dengan 3 parameter
//yaitu array,indeks posisi terkiri,dan indeks posisi terkanan
void bubblesort(int data[],int kiri,int kanan) {
int tmp;
//perulangan bersarang,untuk mengurutkan
for (int i=kiri;i<=kanan;i++) {
for (int j=kiri;j<=kanan;j++) {
if (data[i]<data[j]) {
//pertukaran data
tmp=data[i];
data[i]=data[j];
data[j]=tmp;
}
}
}
}
//program utama
int main() {
int n;
cin >> n;
int data[n-1];
for (int i=0;i<n;i++) cin >> data[i];
bubblesort(data,0,n-1);
for (int i=0;i<n;i++) cout << data[i] << endl;
}

Jika ingin mengurutkan secara descending (besar ke kecil), cukup ubah kalimat if (data[i]<data[j]) menjadi if (data[i]>data[j])

2. Quick Sort

Sorting yang menggunakan prinsip rekursif dalam algoritmanya. Lebih cepat daripada Bubble Sort. Kompleksitasnya (O N log N).

Kode :

#include <iostream>
using namespace std;
//method bernama quickosort,dengan 3 parameter seperti
//contoh sebelumnya di source code bubble sort
void quicksort(int data[],int kiri,int kanan) {
int i=kiri;
int j=kanan;
int temp;
int pivot=data[(kiri+kanan)/2];
while (i<=j) {
while (data[i]<pivot) i++;
while (data[j]>pivot) j--;
if (i<=j) {
//pertukaran data
temp=data[i];
data[i]=data[j];
data[j]=temp;
i++;
j--;
}
//fungsi rekursif untuk memecah sorting
if (kiri<j) quicksort(data,kiri,j);
if (i<kanan) quicksort(data,i,kanan);
}
}
int main() {
int n;
cin >> n;
int data[n-1];
for (int i=0;i<n;i++) {
cin >> data[i];
}
quicksort(data,0,n-1);
for (int i=0;i<n;i++) cout << data[i] << endl;
}

Jika ingin mengurutkan secara descending (dari besar ke kecil), cukup ganti tanda pembanding dari while (data[i]<pivot) i++; menjadi while (data[i]>pivot) i++; dan ubah juga while (data[j]>pivot) j–; menjadi while (data[j]<pivot) j–;

3. Menggunakan sort() di C++

Kalau anda menggunakan C++, sebenarnya sudah ada satu perintah untuk sorting, dengan mengimport library <algorithm>. Untuk lebih jelasnya bisa dibaca disini.

Kode :

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int data[n-1];
for (int i=0;i<n;i++) {
cin >> data[i];
}
//memanggil fungsi sort() dengan parameter array,array+jumlah_data
sort(data,data+n);
for (int i=0;i<n;i++) cout << data[i] << endl;
}

Kode diatas mengurutkan secara ascending (kecil -> besar), bagaimana jika mau mengurutkan dari besar ke kecil? Dibawah baris sort(data,data+n); cukup tambahkan perintah reverse(data,data+n); untuk membalikkan data.

~~~

Sekian dari sesi sorting ini, jika ada yang mau ditanyakan atau dikritik, silahkan🙂

Referensi :

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s