Malas baca? download materi kuliah
sorting di bahasa C
Pengurutan data (sorting) didefinisikan sebagai suatu proses untuk menyusun kembali humpunan obyek menggunakan aturan tertentu. Mnurut
Microsoft Book-shelf, definisi algoritma pengurutan adalah algoritma untuk meletakkan kumpulan elemen data ke dalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen.
Ada dua macam urutan yang biasa digunakan dalam proses pengurutan yaitu
- urut naik (ascending) yaitu dari data yang mempunyai nilai paling kecil sampai paling besar
- urut turun (descending) yaitu data yang mempunyai nilai paling besar sampai paling kecil.
Contoh : data bilangan 5, 2, 6 dan 4 dapat diurutkan naik menjadi 2, 4, 5, 6 atau diurutkan turun menjadi 6, 5, 4, 2. Pada data yang bertipe char, nilai data dikatakan lebih kecil atau lebih besar dari yang lain didasarkan pada urutan relatif (
collating sequence) seperti dinyatakan dalam tabel ASCII (Lampiran)
Keuntungan dari data yang sudah dalam keadaan terurutkan antara lain :
- data mudah dicari (misalnya dalam buku telepon atau kamus bahasa), mudah untuk dibetulkan, dihapus, disisipi atau digabungkan. Dalam keadaan terurutkan, kita mudah melakukan pengeekan apakah ada data yang hilang
- melakukan komppilasi program komputer jika tabel-tabel simbol harus dibentuk
- mempercepat proses pencarian data yang harus dilakukan berulang kali
Data yang diurutkan sangat bervariasi, dalam hal jumlah data maupun jenis data yang akan diurutkan. Tidak ada algoritma terbaik untuk setiap situasi yang kita hadapi, bahkan cukup sulit untuk menentukan algoritma mana yang paling baik untuk situasi tertentu karena ada beberapa faktor yang mempengaruhi efektifitas algoritma pengurutan. Beberapa faktor yang berpengaruh pada efektifitas suatu algoritma pengurutan antara lain:
- banyak data yang diurutkan
- kapasitas pengingat apakah mampu menyimpan semua data yang kita miliki
- tempat penyimpanan data, misalnya piringan, pita atau kartu, atau media penyimpan yang lain.
Pemilihan algoritma sangat ditentukan oleh struktur data yang digunakan. Metode pengurutan yang digunakan dapat diklasifikasikan menjadi dua katagori yaitu :
- pengurutan internal, yaitu pengurutan dengan menggunakan larik (array). Larik tersimpan dalam memori utama komputer
- pengurutan eksternal, yaitu pengurutan dengan menggunakan berkas (sequential access file). Berkas tersimpan dalam pengingat luar, misalnya cakram atau pita magnetis.
Untuk menggambarkan pengurutan dengan larik, bisa kita bayangkan semua kartu terletak di hadapan kita sehingga semua kartu terlihat dengan jelas nomornya. Pada penyusunan kartu sebagai sebuah berkas, kita bayangkan semua kartu kita tumpuk sehingga hanya kartu bagian atas saja yang bisa kita lihat nomornya.
Pada bab ini akan dijelaskan beberapa metode pengurutan beserta analisanya.
Metode Penyisipan Langsung (Straight Insertion Sort)
Proses pengurutan dengan
metode penyisipan langsung dapat dijelaskan sebagai berikut :
Data dicek satu per satu mulai dari yang kedua sampai dengan yang terakhir. Apabila ditemukan data yang lebih kecil daripada data sebelumnya, maka data tersebut disisipkan pada posisi yang sesuai. Akan lebih mudah apabila membayangkan pengurutan kartu. Pertama-tama anda meletakkan kartu-kartu tersebut di atas meja, kemudian melihatnya dari kiri ke kanan. Apabila kartu di sebelah kanan lebih kecil daripada kartu di sebelah kiri, maka ambil kartu tersebut dan sisipkan di tempat yang sesuai. Algoritma penyisipan langsung dapat dituliskan sebagai berikut :
Metode Penyisipan Biner (Binary Insertion Sort)
Metode ini merupakan pengembangan dari
metode penyisipan langsung. Dengan cara penyisipan langsung, perbandingan selalu dimulai dari elemen pertama (data ke-0), sehingga untuk menyisipkan elemen ke i kita harus melakukan perbandingan sebanyak i – 1 kali. Ide dari metode ini didasarkan pada kenyataan bahwa pada saat menggeser data ke-i, data ke 0 s/d i-1 sebenarnya sudah dalam keadaan terurut. Sebagai contoh pada tabel 6.1 diatas, pada saat i=4, data ke 0 s/d 3 sudah dalam keadaan urut : 3, 9, 12, 35.
Dengan demikian posisi dari data ke-i sebenarnya dapat ditentukan dengan pencarian biner.
Metode Seleksi (Selection Sort)
Metode seleksi melakukan pengurutan dengan cara mencari data yang terkecil kemudian menukarkannya dengan data yang digunakan sebagai acuan atau sering dinamakan pivot.
Proses pengurutan dengan metode seleksi dapat dijelaskan sebagai berikut : langkah pertama dicari data terkecil dari data pertama sampai data terakhir. Kemudian data terkecil ditukar dengan data pertama. Dengan demikian, data pertama sekarang mempunyai nilai paling kecil dibanding data yang lain. Langkah kedua, data terkecil kita cari mulai dari data kedua sampai terakhir. Data terkecil yang kita peroleh ditukar dengan data kedua dan demikian seterusnya sampai semua elemen dalam keadaan terurutkan.
Metode Gelembung (Bubble sort)
Metode gelembung (bubble sort) sering juga disebut dengan
metode penukaran (exchange sort) adalah metode yang mengurutkan data dengan cara membandingkan masing-masing elemen, kemudian melakukan penukaran bila perlu. Metode ini mudah dipahami dan diprogram, tetapi bila dibandingkan dengan metode lain yang kita pelajari, metode ini merupakan metode yang paling tidak efisien.
Proses pengurutan metode gelembung ini menggunakan dua kalang. Kalang pertama melakukan pengulangan dari elemen ke 2 sampai dengan elemen ke N-1 (misalnya variable i), sedangkan kalang kedua melakukan pengulangan menurun dari elemen ke N sampai elemen ke i (misalnya variable j). Pada setiap pengulangan, elemen ke j-1 dibandingkan dengan elemen ke j. Apabila data ke j-1 lebih besar daripada data ke j, dilakukan penukaran.
Metode Shell (Shell Sort)
Metode ini disebut juga dengan
metode pertambahan menurun (diminishing increment). Metode ini dikembangkan oleh
Donald L. Shell pada tahun 1959, sehingga sering disebut dengan Metode Shell Sort. Metode ini mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu, kemudian dilakukan penukaran bila diperlukan.
Proses pengurutan dengan metode Shell dapat dijelaskan sebagai berikut :
Pertama-tama adalah menentukan jarak mula-mula dari data yang akan dibandingkan, yaitu N / 2. Data pertama dibandingkan dengan data dengan jarak N / 2. Apabila data pertama lebih besar dari data ke N / 2 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 2. Demikian seterusnya sampai seluruh data dibandingkan sehingga semua data ke-j selalu lebih kecil daripada data ke-(j + N / 2).
Pada proses berikutnya, digunakan jarak (N / 2) / 2 atau N / 4. Data pertama dibandingkan dengan data dengan jarak N / 4. Apabila data pertama lebih besar dari data ke N / 4 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 4. Demikian seterusnya sampai seluruh data dibandingkan sehingga semua data ke-j lebih kecil daripada data ke-(j + N / 4).
Pada proses berikutnya, digunakan jarak (N / 4) / 2 atau N / 8. Demikian seterusnya sampai jarak yang digunakan adalah 1.
Metode Quick (Quick Sort)
Metode Quick sering disebut juga
metode partisi (partition exchange sort). Metode ini diperkenalkan pertama kali oleh
C.A.R. Hoare pada tahun 1962. Untuk mempertinggi efektifitas dari metode ini, digunakan teknik menukarkan dua elemen dengan jarak yang cukup besar.
Proses penukaran dengan metode quick dapat dijelaskan sebagai berikut.: mula - mula dipilih data tertentu yang disebut pivot, misalnya x. Pivot dipilih untuk mengatur data di sebelah kiri agar lebih kecil daripada pivot dan data di sebelah kanan agar lebih besar daripada pivot. Pivot ini diletakkan pada posisi ke j sedemikian sehingga data antara 1 sampai dengan j-1 lebih kecil daripada x. Sedangkan data pada posisi ke j+1 sampai N lebih besar daripada x. Caranya dengan menukarkan data diantara posisi 1 sampai dengan j-1 yang lebih besar daripada x dengan data diantara posisi j+1 sampai dengan N yang lebih kecil daripada x.
Metode Penggabungan (Merge Sort)
Metode penggabungan biasanya digunakan pada pengurutan berkas. Prinsip dari metode penggabungan sebagai berikut : mula-mula diberikan dua kumpulan data yang sudah dalam keadaan urut. Kedua kumpulan data tersebut harus dijadikan satu table sehingga dalam keadaan urut.
Misalnya kumpulan data pertama (T1) adalah sebagai berikut :
3 11 12 23 31
Sedangkan kumpulan data kedua (T2) adalah sebagai berikut :
9 15 17 20 35
Proses penggabungan ini dapat dijelaskan sebagai berikut : mula-mula diambil data pertama dari T1 yaitu 3 dan data pertama dari T2 yaitu 9. Data ini dibandingkan, kemudian yang lebih kecil diletakkan sebagai data pertama dari hasil pengurutan, misalnya T3. Jadi T3 akan memiliki satu data yaitu 3. Data yang lebih besar yaitu 9 kemudian dibandingkan dengan data kedua dari T1, yaitu 11. Ternyata 9 lebih kecil dari 11, sehingga 9 diletakkan sebagai data kedua dari T3. Demikian seterusnya sehingga didapat hasil sebagai berikut :
3 9 11 12 15 17 20 23 31 35
Itu semua penjelasan singkat yang saya kutip dari buku.
berikut adalah contoh program yang telah saya buat. program berisikan hampir semua tipe sorting dan di urutkan secara ascending dan descending.
#include
#include
#include
#define MAX 100
int data[MAX],a[MAX],n,hasil[MAX];
void copy();
void random();
void tampil();
void insertionsort(int);
void selectionsort(int);
void bubblesort(int);
void shellsort(int);
void merge(int,int,int,int);
void mergesort(int,int,int);
void quicksort(int,int,int);
void tukar(int*,int*);
main(){
int pilih,sort;
char lagi;
printf("masukkan jumlah data = ");
scanf("%d",&n);
random();
do{
copy();
printf("\n===MENU SHORTING===\n");
printf("1.Insertionsort.\n2.Selectionsort.\n3.Bubblesort\n4.Shellsort\n5.Mergesort\n6.Quicksort\n\nPilih menu = ");
scanf("%d",&pilih);
printf("\n1.Ascending\n2.Descending\n\npilih = ");
scanf("%d",&sort);
printf("\nSebelum dilakukan sorting.\n");
tampil(a);
printf("\nSesudah dilakukan sorting.\n");
if(pilih==1)
insertionsort(sort);
else if(pilih==2)
selectionsort(sort);
else if(pilih==3)
bubblesort(sort);
else if(pilih==4)
shellsort(sort);
else if(pilih==5)
mergesort(0,n-1,sort);
else
quicksort(0,n-1,sort);
fflush(stdin);
printf("\nCoba lagi(y/t) = ");
scanf("%c",&lagi);
}while(lagi=='y'||lagi=='Y');
}
void random(){ // memasukkan nilai random 1-100 ke setiap data[array]
int i;
for(i=0;i
srand(time(NULL)*(i+1));
data[i]=rand()%100;
}
}
void copy(){ // menyalin data supaya proses shorting dapat di lakukan lagi
int i;
for(i=0;i
a[i]=data[i];
}
void tampil(){ // menampilkan data setelah di urutkan
int i;
for(i=0;i
printf("%d ",a[i]);
printf("\n");
}
void insertionsort(int sort){ // fungsi sorting dengan cara insertion
int i,temp,j;
for(i=1;i
temp=a[i];
j=i-1;
if(sort==1)
while(j>=0&&a[j]>temp){
a[j+1]=a[j];
j--;
}
else
while(j>=0&&a[j]
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
tampil();
}
}
void selectionsort(int sort){ // fungsi sorting dengan cara selection
int i,j,min;
for(i=0;i
min=i;
j=i+1;
while(j
if(sort==1){
if(a[j]
min=j;
}
else{
if(a[j]>a[min])
min=j;
}
j++;
}
tukar(&a[i],&a[min]);
tampil();
}
}
void bubblesort(int sort){ // fungsi sorting dengan cara bubble
int post_akhir,index;
post_akhir=n-2;
while(post_akhir>=0){
index=0;
while(index<=post_akhir){
if(sort==1){
if(a[index]>a[index+1]){
tukar(&a[index],&a[index+1]);
}
}
else{
if(a[index]
tukar(&a[index],&a[index+1]);
}
}
index++;
}
tampil();
post_akhir--;
}
}
void shellsort(int sort){ // fungsi sorting dengan cara shell
int j,jarak,did_swap;
jarak=n;
while(jarak>1){
jarak=jarak/2;
did_swap=1;
while(did_swap==1){
did_swap=0;
j=0;
while(j<(n-jarak)){
if(sort==1){
if(a[j]>a[j+jarak]){
tukar(&a[j],&a[j+jarak]);
did_swap=1;
}
}
else{
if(a[j]
tukar(&a[j],&a[j+jarak]);
did_swap=1;
}
}
j++;
}
}
tampil();
}
}
void merge(int l, int med, int r,int sort){ // fungsi sorting dengan cara merge
int i,j,kanan1,kanan2,kiri1,kiri2;
kiri1=l;
kanan1=med;
kiri2=med+1;
kanan2=r;
i=l;
while(kiri1<=kanan1 && kiri2<=kanan2){
if(sort==1){
if(a[kiri1]<=a[kiri2]){
hasil[i]=a[kiri1];
kiri1++;
}
else{
hasil[i]=a[kiri2];
kiri2++;
}
}
else{
if(a[kiri1]>=a[kiri2]){
hasil[i]=a[kiri1];
kiri1++;
}
else{
hasil[i]=a[kiri2];
kiri2++;
}
}
i++;
}
while(kiri1<=kanan1){
hasil[i]=a[kiri1];
kiri1++;
i++;
}
while(kiri2<=kanan2){
hasil[i]=a[kiri2];
kiri2++;
i++;
}
j=l;
while(j<=r){
a[j]=hasil[j];
j++;
}
tampil();
}
void mergesort(int l,int r,int sort){
int med;
if(l
med = (l+r)/2;
mergesort(l,med,sort);
mergesort(med+1,r,sort);
merge(l,med,r,sort);
}
}
void quicksort(int p, int r,int sort){ // fungsi sorting dengan cara quick
int x,j,i;
x=a[p];
i=p;
j=r;
while(i<=j){
if(sort==1){
while(a[i]
i++;
while(a[j]>x)
j--;
}else{
while(a[i]>x)
i++;
while(a[j]
j--;
}
if(i<=j)
{
tukar(&a[i],&a[j]);
i++;
j--;
}
}
if(p
quicksort(p,j,sort);
if(i
quicksort(i,r,sort);
tampil();
}
void tukar(int *a,int *b){ // fungsi tukar terhadapat nilai kecil kepada nilai yang lebih besar
int temp;
temp = *a;
*a = *b;
*b = temp;
}
lumayan panjang. silahkan download materi-nya
di sini
#include
#include
#include
#define MAX 100
int data[MAX],a[MAX],n,hasil[MAX];
void copy();
void random();
void tampil();
void insertionsort(int);
void selectionsort(int);
void bubblesort(int);
void shellsort(int);
void merge(int,int,int,int);
void mergesort(int,int,int);
void quicksort(int,int,int);
void tukar(int*,int*); main(){
int pilih,sort;
char lagi;
printf("masukkan jumlah data = ");
scanf("%d",&n);
random();
do{
copy();
printf("\n===MENU SHORTING===\n");
printf("1.Insertionsort.\n2.Selectionsort.\n3.Bubblesort\n4.Shellsort\n5.Mergesort\n6.Quicksort\n\nPilih menu = ");
scanf("%d",&pilih);
printf("\n1.Ascending\n2.Descending\n\npilih = ");
scanf("%d",&sort);
printf("\nSebelum dilakukan sorting.\n");
tampil(a);
printf("\nSesudah dilakukan sorting.\n");
if(pilih==1)
insertionsort(sort);
else if(pilih==2)
selectionsort(sort);
else if(pilih==3)
bubblesort(sort);
else if(pilih==4)
shellsort(sort);
else if(pilih==5)
mergesort(0,n-1,sort);
else
quicksort(0,n-1,sort);
fflush(stdin);
printf("\nCoba lagi(y/t) = ");
scanf("%c",&lagi);
}while(lagi=='y'||lagi=='Y');
}
void random(){ // memasukkan nilai random 1-100 ke setiap data[array]
int i;
for(i=0;i
srand(time(NULL)*(i+1));
data[i]=rand()%100;
}
}
void copy(){ // menyalin data supaya proses shorting dapat di lakukan lagi
int i;
for(i=0;i
a[i]=data[i];
}
void tampil(){ // menampilkan data setelah di urutkan
int i;
for(i=0;i
printf("%d ",a[i]);
printf("\n");
}
void insertionsort(int sort){ // fungsi sorting dengan cara insertion
int i,temp,j;
for(i=1;i
temp=a[i];
j=i-1;
if(sort==1)
while(j>=0&&a[j]>temp){
a[j+1]=a[j];
j--;
}
else
while(j>=0&&a[j]
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
tampil();
}
}
void selectionsort(int sort){ // fungsi sorting dengan cara selection
int i,j,min;
for(i=0;i
min=i;
j=i+1;
while(j
if(sort==1){
if(a[j]
min=j;
}
else{
if(a[j]>a[min])
min=j;
}
j++;
}
tukar(&a[i],&a[min]);
tampil();
}
}
void bubblesort(int sort){ // fungsi sorting dengan cara bubble
int post_akhir,index;
post_akhir=n-2;
while(post_akhir>=0){
index=0;
while(index<=post_akhir){
if(sort==1){
if(a[index]>a[index+1]){
tukar(&a[index],&a[index+1]);
}
}
else{
if(a[index]
tukar(&a[index],&a[index+1]);
}
}
index++;
}
tampil();
post_akhir--;
}
}
void shellsort(int sort){ // fungsi sorting dengan cara shell
int j,jarak,did_swap;
jarak=n;
while(jarak>1){
jarak=jarak/2;
did_swap=1;
while(did_swap==1){
did_swap=0;
j=0;
while(j<(n-jarak)){
if(sort==1){
if(a[j]>a[j+jarak]){
tukar(&a[j],&a[j+jarak]);
did_swap=1;
}
}
else{
if(a[j]
tukar(&a[j],&a[j+jarak]);
did_swap=1;
}
}
j++;
}
}
tampil();
}
}
void merge(int l, int med, int r,int sort){ // fungsi sorting dengan cara merge
int i,j,kanan1,kanan2,kiri1,kiri2;
kiri1=l;
kanan1=med;
kiri2=med+1;
kanan2=r;
i=l;
while(kiri1<=kanan1 && kiri2<=kanan2){
if(sort==1){
if(a[kiri1]<=a[kiri2]){
hasil[i]=a[kiri1];
kiri1++;
}
else{
hasil[i]=a[kiri2];
kiri2++;
}
}
else{
if(a[kiri1]>=a[kiri2]){
hasil[i]=a[kiri1];
kiri1++;
}
else{
hasil[i]=a[kiri2];
kiri2++;
}
}
i++;
}
while(kiri1<=kanan1){
hasil[i]=a[kiri1];
kiri1++;
i++;
}
while(kiri2<=kanan2){
hasil[i]=a[kiri2];
kiri2++;
i++;
}
j=l;
while(j<=r){
a[j]=hasil[j];
j++;
}
tampil();
}
void mergesort(int l,int r,int sort){
int med;
if(l
med = (l+r)/2;
mergesort(l,med,sort);
mergesort(med+1,r,sort);
merge(l,med,r,sort);
}
}
void quicksort(int p, int r,int sort){ // fungsi sorting dengan cara quick
int x,j,i;
x=a[p];
i=p;
j=r;
while(i<=j){
if(sort==1){
while(a[i]
i++;
while(a[j]>x)
j--;
}else{
while(a[i]>x)
i++;
while(a[j]
j--;
}
if(i<=j)
{
tukar(&a[i],&a[j]);
i++;
j--;
}
}
if(p
quicksort(p,j,sort);
if(i
quicksort(i,r,sort);
tampil();
}
void tukar(int *a,int *b){ // fungsi tukar terhadapat nilai kecil kepada nilai yang lebih besar
int temp;
temp = *a;
*a = *b;
*b = temp;
}
seperti saat 
Bagi anda yang ingin upgrade atau 
