Pengertian Algoritma Sorting adalah kumpulan langkah sistematis atau secara berutan untuk memperoleh hasil yang diinginkan. Salah satu contoh dari algoritma untuk langkah ini adalah Sorting (pengurutan). Sorting dapat didefinisikan sebagai pengurutan sejumlah data berdasarkan nilai tertentu. Pengurutan dapat dilakukan dari nilai terkecil ke nilai terbesar (ascending) atau sebaliknya.
Sorting dapat dibedakan menjadi dua yaitu Comparasion Sort (Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort) dan Non-Comparasion Sort (Radix Sort, Counting Sort). Comparasion Sort / penggurutan dengan pembandingan adalah algoritma yang dalam proses pengurutannya melakukan pembandingan antar data. Non-Comparasion Sort / pengurutan tanpa pembandingan adalah algoritma pengurutan dimana dalam prosesnya tidak melakukan perbandingan antar data.
1. Pengurutan Bilangan Metode Bubble Sort.
Proses pengurutannya adalah untuk mengurutkan bilangan diperlukan variable array untuk menampung semua bilangan yang akan kita urutkan. Proses pengurutan dilakukan dengan membangkan semua bagian array satu per satu. Contoh dibawah ini berisi sederer bilangan yang belum diurutkan.
| 21 | 13 | 36 | 12 | 18 | 9 | 59 | 24 |
1 2 3 4 5 6 7 8
Indeks yang menunjukkan Posisi Elemen
Di metode Bubble Sort, proses pengurutan dimulai dengan membandingkan elemen pertama untuk mendapatkan angka yang paling besar. Lalu angka terbesar tersebut ditempatkan pada elemen terakhir. Sebagai langkah awal, isi elemen pertama dibandingkan dengan elemen ke-2. Jika isi elemen ke-2 lebih kecil dari elemen pertama, maka isi kedua elemen tersebut ditukar. Sehingga isi array akan berubah menjadi :
| 13 | 21 | 36 | 12 | 18 | 9 | 59 | 24 |
1 2 3 4 5 6 7 8
Elemen array telah ditukar
Lalu elemen ke-2 dibandingkan dengan elemen ke-3, jika isi element ke-3 lebih besar, maka isi kedua elemen tersebut tidak ditukar.
| 13 | 21 | 36 | 12 | 18 | 9 | 59 | 24 |
1 2 3 4 5 6 7 8
Isi elemen ke-3 lebih besar dari elemen ke-2
Perbandingan selanjutnya dilakukan terhadap elemen ke-3 dengan ke-4. Karena elemen ke-4 lebih kecil, maka isi kedua elemen tersebut ditukar. Sehingga arrat sebelumnya berubah menjadi:
| 13 | 21 | 12 | 36 | 18 | 9 | 59 |
1 2 3 4 5 6 7 8
Isi elemen setelah ditukar
Proses perbandingan seperti diatas dilakukan secara berulang sampai pada elemen terakhir. Sehingga pada akhirnya akan dihasilkan bilangan terbesar yang ditempatkan pada posisi elemen terakhir. Dibawah ini kondisi array setelah perbandingan elemen terakhir.
| 13 | 21 | 12 | 36 | 18 | 9 | 24 | 59 |
1 2 3 4 5 6 7 8
Isi elemen terakhir berisikan bilangan terbesar
Proses diatas hanya mencari bilangan terbesar pertama. Ulangi proses tersebut untuk mencari bilangan terbesar lainnya setelah bilangan terbesar pertama tadi. Namun proses perbandingan hanya dilakukan mulai dari elemen pertama sampai elemen ke-7.
Isi elemen pertama dibandingkan dengan elemen ke-2. Karena isi elemen ke-2 lebih besar, maka isi kedua elemen tersebut tidak ditukar.
Kemudian elemen ke-2, dibandingkan dengan elemen ke-3. Karena elemen ke-3 lebih kecil, maka isi kedua elemen tersebut ditukar sehingga isi array menjadi :
| 13 | 12 | 21 | 18 | 9 | 36 | 24 | 59 |
1 2 3 4 5 6 7 8
Isi elemen array yang sudah diurut
Lanjutkan proses diatas sampai pada elemen ke-7. Hasilnya isi array menjadi :
| 13 | 12 | 18 | 9 | 21 | 24 | 36 | 59 |
1 2 3 4 5 6 7 8
Isi elemen array yang sudah diurut
Kini isi elemen ke-7 dan ke-8 sudah urut berdasarkan bilangan kecil ke besar. Namun elemen lainnya belum terurut. Untuk itu ulangi proses diatas, namun elemen yang dibandingkan hanya sampai pada elemen ke-6 saja. Setelah itu, proses perbadingan diulangi lagi sampai elemen terakhir yang dibandingkan yaitu elemen ke-2. Hasil akhirnya menjadi :
| 9 | 12 | 13 | 18 | 21 | 24 | 36 | 59 |
1 2 3 4 5 6 7 8
Source Code pada Java
public class BubbleSort {
public static void main(String args[]){
int[] data={21,13,36,12,18,9,59,24};
int temp;
for (int i=1;i<data.length;i++){
for (int j=data.length-1;j>=i;j–){
if (data[j]<data[j-1]){
temp=data[j];
data[j]=data[j-1];
data[j-1]=temp;
}
}
}
for (int i=0;i<data.length;i++)
System.out.print(data[i]+” “);
}
}
2. Pengurutan Bilangan Metode Selection Sort.
Selection sort merupakan sebuah algoritma pengurutan yang secara berulang mencari item yang belum terurut dan mencari paling sedikit satu untuk dimasukkan ke dalam lokasi akhir. Selection sort salah satu agoritma pengurutan yang mudah untuk dipelajari. Dibandingkan dengan bubble short, frekuensi pertukaran data pada selection short lebih sedikit.
Metode ini memiliki konsep memilih data yang maksimum/minimum dari suatu kumpulan data larik L, lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data maksimum/minimum yang diperoleh, diasingkan ke tempat lain, dan tidak diikutsertakan pada proses pencarian data maksimum/minimum berikutnya. Ide utama dari selection short adalah memiliki elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-1. Nilai dari I dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.
Prinsip kerja dari Teknik Section sort ini adalah:
1. Pengecekan dimulai dari data 1 sampai dengan data ke n
2. Tentukan bilangan dengan Index terkecil dari data bilangn tersebut
3. Tukar bilangan dengan index terkecil tersebut dengan bilangan pertama (I=1) dari
data bilangan tersebut
4. Lakukan langkah 2 dan3 untuk bilangan berikutnya (I=I+1)sampai di dapatkan data yang optimal
Sintaks program fungsi Selection Sort
for ( i=0 ; i <= N-2 ; i++) { kecil = i; for ( k = i+1 ; k <= N-1 ; k++ ) { if (A[k] > A[j])
{
kecil = k;
}
}
temp = A[i];
A[i] = A[kecil];
A[kecil] = temp;
}
Contoh kasus:
Misalkan tabel A berisi elemen-elemen berikut:
15, 100, 136, 12, 18,19, 59, 24, 10, 191
Langkah-langkah pengurutan dengan Selection Sort:
Contoh Ilustrasi: Urutkan data berikut 15, 100, 136, 12, 18,19, 59, 24, 10, 191
Contoh program Java 1:
public class SelectionSort{
public static void main(String args[]){
int[] data={15, 100, 136, 12, 18,19, 59, 24, 10, 191};
int temp,pos;
for (int i=0;i<data.length-1;i++){
pos=i;
for (int j=i+1;j<data.length;j++){
if (data[j]<data[pos]){
pos=j;
}
}
if (pos!=i){
temp=data[i];
data[i]=data[pos];
data[pos]=temp;
}
}
for (int i=0;i<data.length;i++)
System.out.print(data[i]+” “);
}
}
Contoh program Java 2 :
public class SelectionSort {
public static void main(String[] args)
{ int[] x = {15, 100, 136, 12, 18,19, 59, 24, 10, 191};
int i, temp, j;
System.out.println(“Sebelum diurutkan :”);
for(i=0;i<x.length;i++)
System.out.print(x[i]+”\t”);
System.out.println(“\n”);
for(i=0;i<x.length-1;i++)
{ for(j=i+1;j<x.length;j++)
{ if(x[i]>x[j])
{ temp = x[i];
x[i] = x[j];
x[j] = temp;
}
}
for(int k=0;k<x.length;k++)
System.out.print(x[k]+”\t”);
System.out.println();
}
System.out.println(“Setelah diurutkan :”);
for(i=0;i<x.length;i++)
System.out.print(x[i]+”\t”);
}
}
Sumber : blog.trisakti.ac.id
Tidak ada komentar:
Posting Komentar