Sorting

Pengimplementasian metode Sorting (Algoritma & Struktur data) pada bahasa C

Sorting / pengurutan biasanya dilakukan untuk tujuan mempermudah pencarian. Pengurutan data baik dari segi ascending (dari nilai terkecil ke terbesar) atau descending (dari nilai terbesar ke terkeci).Ketika akan melakukan sortir di computer , maka hal-hal yang akan dipertimbangkan ,meliputi :
1. Perlu tidaknya data disortir
2. Besarnya atau banyaknya data yang akan disortir
3. Kemampuan atau kapasitas computer atau media penyimpanan data
4. Metode sortir
Pada garis besarnya, ada tiga teknik sortir :
1. Insertion sort (sortir penyisipan)
2. Selection sort (sortit pemilihan)
3. Exchange short (sortir penukaran)
Teknik sortir sangat erat kaitannya dengan proses perbandingan dan penukaran tempat antarelemen data. Kita tidak dapat menentukan dengan pasti , mana dari ketiga teknik sortir tersebut yang merupakan teknik terbaik (melakukan perbandingan dan penukaran tempat antarelemen dan yang paling sedikit). Banyaknya proses perbandingan dan penukaran tempat antar elemen data tersebut juga terkait dengan susunan elemen – elemen datanya.
Sehingga , kecepatan dalam melakukan sortir juga ditentukan atas tiga kondisi susunan elemen-elemen datanya. Waktu terbaik akan diperoleh ketika susunan elemen datanya sudah sama dengan susunan yang diinginkan melalui sortirnya. Waktu terburuk akan didapatkan ketika susunan elemen – elemen datanya terbalik dari susunan yang dikehendaki sortirnya. Waktu rata-rata diperoleh dengan memperhitungkan berbagai susunan bentuk elemen-elemen datanya.
1. Insertion sort
Teknik ini adalah dengan membandingkan elemen ke n (n mulai dari 2 hingga elemen terakhir) dengan elemen – elemen sebelumnya. Bila elemen yang dibandingkan bernilai lebih kecil , maka tukar posisinya.
Contoh : 8,3,7,4
Pada langkah pertama, elemen kedua akan dibandingkan dengan elemen pertama, 3 dibandingkan dengan 8 , karena 3 lebih kecil dari 8, maka kedua elemen tersebut saling ditukar tempatnya yang menghasilkan urutan 3,8,7,4 (dua elemen pertama sudah diurut). Pada langkah kedua , elemen ketiga akan dibandingkan dengan 8 , terjadi penukaran tempat yang menghasilkan urutan 3,7,8,4. Selanjutnya 7 tersebut dibandingkan dengan elemen pertama, yaitu 3. Tidak terjadi penukaran tempat (3 elemen pertama sudah diurut).
Pada langkah ketiga , elemen keempat yaitu 4 dibandingkan dengan elemen ketiga. Angka 4 lebih kecil dari 8, terjadi penukaran tempat, hasil sementara adalah 3,7,4,8. Angka 4 tadi dibandingkan dengan elemen kedua,4 lebih kecil dari 7, terjadi penukaran tempat, hasil sementara adalah 3,4,7,8. Selanjutnya angka 4 tadi dibandingkan dengan elemen pertama, yaitu 3. Karena 4 lebih besar dari 3, maka tidak terjadi penukaran tempat lagi (empat elemen pertama sudah urut=hasil akhir).
Sub-sub langkahnya ketiganya : 3,7,8,4 (awal) -> 4 dibandingkan 8, ditukar
hasilnya : 3,7,4,8 -> 4 banding 7, tukar,
hasilnya : 3,4,7,8 -> 4 banding 3,tetap
hasilnya : 3,4,7,8 (akhir)
Sintak Implementasi insertion sort dalam bhs C adalah sbb:
void insertionsort(int arr[]) {
int i,j;
for (i = 1; i <>
int temp = arr[i];
int pos = i;
for (j = i; j > 0; j--) {
if (temp <>
arr[j] = arr[j-1];
pos--;
}
}
arr[pos]=temp;
}
}
void insertion_sort()
{
int temp, i, j;
for (i=1; i
{
temp = data[i];
j = i-1;
while (data[j] > temp && j>=0)
{
data[j+1] = data[j];
j--;
}
data[j+1] = temp;
}
cout<<"insertion sort selesai!"< } 2. Selection sort Teknik ini adalah mencari nilai elemen terkecil kemudian letakkan dan tukar dengan posisi n (n mulai dari 1 hingga elemen terakhir -1). Contoh : 8,3,7,4 Pada langkah pertama, hasil sortirnya 3, 8,7,4 (mulai dari elemen pertama, elemen terkecil = 3, letakkan dan tukarkan dengan elemen pertama). Pada langkah kedua , hasil sortirnya 3,4,7,8 (mulai dari elemen kedua, elemen terkecil = 4, letakkan dan tukarkan dengan elemen kedua). Pada langkah ketiga , hasil sortirnya 3,4,7,8 (mulai dari elemen ketiga, elemen terkecil =7, letakkan dan tukarkan dengan elemen ketiga, hasilnya ternyata tetap). Sintak Implementasi selection sort dalam bhs C adalah sbb: void selection_sort() { int pos, i, j; for (i=0; i { pos = i; for (j=i+1; j { if (data[j] < pos =" j; } if (pos != i) tukar(pos,i); } cout<<" i =" 0;">
int min = arr[i];
int pos = i;
for (j = i; j <>
/* Cari nilai yang terkecil */
if (arr[j] <>
min = arr[j];
pos = j;
}
}
/* Tukar nilai terkecil ke arr[i] jika pos tdk sama i */
if(i!=pos) {
int temp = arr[i];
arr[i] = arr[pos];
arr[pos] = temp;
}
}
}

3. Exchange sort
Contoh sortir umum yang menggambarkan exchange sort adalah bubble sort. Algoritma dari teknik ini adalah dengan melakukan proses perbandingan sebanyaknya n elemen dimulai dari n=1 (selanjutnya disebut mulai=1). Bandingkan seluruh elemen diawali dari elemen sebelah kanan hingga ke n. Bila elemen tersebut < 1="n." i="0;" j="(i+1);"> data[j]) tukar(i,j);
}
}
cout<<"Exchange sort selesai!"< } Exchange sort->Bubble sort pada bahasa C :
void bubble_sort()
{
For (int i=1;i=i;j–)
{
If (data[j] < temp =" data[a];">
data[j-1]) //data descending

Tinjauan Materi :
1. Struktur Data 2, Author: Taufik Fuadi Abidin, M.Tech Ph.D
2. Bambang,Wahyudi,2003,PengantarStrukturDataDan Algoritma,Andi,Yogyakarta.
3. http://genduet.wordpress.com/2009/03/19/bubble-sort/