Beberapa bahasa pemrograman menyediakan function untuk pengurutan di dalam library atau headernya, termasuk bahasa C dan C++. Walaupun begitu, saat kalian menggunakan bahasa Pascal, C, atau C++; kalian sebaiknya mengetik function untuk pengurutan yang kalian butuhkan tanpa mengandalkan function yang tersedia di library tertentu.
Algoritma untuk pengurutan ada cukup banyak. Tapi, ada beberapa algoritma pengurutan yang cukup populer karena kelebihan atau keunikannya. Beberapa algoritma pengurutan yang cukup sering digunakan bisa kalian lihat di bawah ini.
- Bubble sort
- Selection sort
- Merge sort
- Quick sort
- Insertion Sort
Bubble Sort
Pengurutan yang pertama dipelajari saat belajar pemrograman biasanya adalah bubble sort. Bubble sort termasuk pengurutan yang sederhana.
Bubble sort mengurutkan data dengan mencari angka yang tepat untuk setiap posisi mulai dari indeks pertama. Bubble sort menggunakan pemeriksaan yang mengerucut untuk mengurutkan data. Karena itu, bubble sort akan cukup lambat jika digunakan untuk mengurutkan terlalu banyak data.
//Bubble Sort
void urutkan(int a[25], int awal, int akhir){
int i, j, temp;
for(i=awal;i<=akhir;i++){
for(j=awal;j<akhir-i;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}Selection Sort
Selection hampir sama dengan Bubble sort. Bedanya ada di tempat pertukarannya. Selection hanya menyimpan indeks data terkecil atau terbesar di loop bagian dalam. Itu berbeda dengan buble sort yang melakukan pertukaran berkali-kali.
//Selection Sort
void urutkan(int a[25], int awal, int akhir){
int i, j, temp, min;
for(i=awal;i<=akhir;i++){
min=i;
for(j=i+1;j<=akhir;j++){
if(a[min]>a[j]){
min=j;
}
}
temp=a[min];
a[min]=a[i];
a[i]=temp;
}
}Quick Sort
Pengurutan yang lebih cepat dibandingkan dengan bubble sort dan selection sort adalah Quicksort. Quick sort mengurutkan data dengan menggunakan rekursi. Berikut ini adalah contoh penerapan Quick sort dalam bahasa C atau C++.//Quick Sort
void urutkan(int angka[25], int awal, int akhir){
int i, j, pivot, temp;
if(awal<akhir){
pivot=awal;
i=awal;
j=akhir;
while(i<j){
while(angka[i]<=angka[pivot]&&i<akhir)i++;
while(angka[j]>angka[pivot])j--;
if(i<j){
temp=angka[i];
angka[i]=angka[j];
angka[j]=temp;
}
}
temp=angka[pivot];
angka[pivot]=angka[j];
angka[j]=temp;
urutkan(angka, awal, j-1);
urutkan(angka, j+1, akhir);
}
}Merge Sort
Selain Bubble Sort dan Quick Sort, satu algoritma pengurutan lain yang cukup banyak digunakan adalah mergesort. Merge sort mengurutkan data dengan membagi data menjadi dua bagian. Penerapan merge sort dalam bentuk function bisa kalian lihat pada contoh di bawah ini.
void gabungkan(int a[], int l, int m, int r){
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = a[l + i];
for (j = 0; j < n2; j++)
R[j] = a[m + 1+ j];
i = 0; // awal sub array pertama
j = 0; // awal sub array kedua
k = l; // awal dari array gabungan
while (i < n1 && j < n2){
if (L[i] <= R[j]){
a[k] = L[i];
i++;
}else{
a[k] = R[j];
j++;
}
k++;
}
/* Salin elemen array L yang tersisa */
while (i < n1){
a[k] = L[i];
i++;
k++;
}
/* Salin elemen array R yang tersisa */
while (j < n2){
a[k] = R[j];
j++;
k++;
}
}
/*Urutkan dengan merge sort*/
void urutkan(int a[], int l, int r){
if (l < r){
//Ambil titik tengah
int m = l+(r-l)/2;
// Urutkan bagian pertama
urutkan(a, l, m);
// Urutkan bagian kedua
urutkan(a, m+1, r);
gabungkan(a, l, m, r);
}
}Sesuai namanya, insertion sort adalah function yang melakukan pengurutan dengan memindahkan dan menyelipkan data di posisi yang seharusnya. Ini tentu saja berbeda dengan algoritma pengurutan lain yang umumnya mengunakan pertukaran. Insertion sort mengurutkan data yang sudah terurut dengan cukup cepat, terutama untuk linked list. Insertion sort akan menjadi sangat lambat jika data urutannya terbalik.
void urutkan(int a[25], int awal, int akhir){
int i, j, k, temp;
i=awal+1;
while(i<=akhir){
if(a[i]<a[i-1]){
//geser
j=i-1;
temp=a[i];
while(j>=0 && a[j]>temp){
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}
i++;
}
}Function main diperlukan untuk menggunakan function-function pengurutan di atas. Contoh function main yang bisa kalian gunakan adalah seperti di bawah ini.
int main(){
int i, jdata;
int angka[100];
printf("Banyaknya data : ");
scanf("%d",&jdata);
printf("Masukkan data!\n");
for(i=0;i<jdata;i++)
scanf("%d",&angka[i]);
urutkan(angka,0,jdata-1);
printf("Data yang sudah terurut: ");
for(i=0;i<jdata;i++)
printf(" %d",angka[i]);
return 0;
}Banyaknya data : 5 Masukkan data! 65 54 45 33 23 Data yang sudah terurut: 23 33 45 54 65
Contoh-contoh algoritma pengurutan yang saya berikan adalah algoritma dalam bentuk urutan ascending. Untuk algoritma pengurutan secara descending, kalian perlu sedikit mengubah tanda perbandingannya.