Materi Shorting
SORTING
Pengertian Sorting
Pengurutan (Sorting) merupakan proses pengurutan sekumpulan data dalam suatu urutan tertentu.
Sorting dipakai untuk:
1.Membantu proses pencarian (searching)
2.Menyelesaikan masalah-masalah kompleks seperti penjadwalan (scheduling), pengolahan basis data, riset operasi, dsb.
Jenis-Jenis Pengurutan:
1.Membantu proses pencarian (searching)
2.Menyelesaikan masalah-masalah kompleks seperti penjadwalan (scheduling), pengolahan basis data, riset operasi, dsb.
Jenis-Jenis Pengurutan:
1. BUBBLE SORT
Pengertian Bubble Sort
Pengertian Bubble Sort
Bubble Sort (metode gelembung) adalah metode pengurutan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.
· Kelebihan dan Kekurangan Bubble Sort
- Kelebihan :
1. Metode Bubble Sort merupakan yang paling simple
2. Metode Bubble Sort muda di pahami algoritmanya
- Kelemahan :
Meskipun simpel metode Bubble Sort merupakan metode pengurutan yang paling tidak efisien. Kelemahan BubbleSort adalah pada saat mengurutkan data yang sangat besar akan mengalami kelambatan luar biasa, atau dengan kata lain kinerja memburuk cukup signifikan ketika data yang diolah jika data cukup banyak. Kelemahan lain adalah jumlah pengulangan akan tetap sama jumlahnya walaupun data sesungguhnya sudah cukup terurut. Hal ini disebabkan setiap data dibandingkan dengan setiap data yang lain untuk menentukan posisinya.
· Algoritma dari Bubble Sort
• Membandingkan data ke-i dengan data ke-(i+1) (tepat bersebelahan). Jika tidak sesuai maka tukar (data ke-i = data ke-(i+1) dan data ke-(i+1) = data ke-i). Apa maksudnya tidak sesuai? Jika kita menginginkan algoritme menghasilkan data dengan urutan ascending (A-Z) kondisi tidak sesuai adalah data ke-i > data ke-i+1, dan sebaliknya untuk urutan descending (A-Z).
• Membandingkan data ke-(i+1) dengan data ke-(i+2). Kita melakukan pembandingan ini sampai data terakhir. Contoh: 1 dgn 2; 2 dgn 3; 3 dgn 4; 4 dgn 5 … ; n-1 dgn n.
• Selesai satu iterasi, adalah jika kita sudah selesai membandingkan antara (n-1) dgn n. Setelah selesai satu iterasi kita lanjutkan lagi iterasi berikutnya sesuai dengan aturan ke-1. mulai dari data ke-1 dgn data ke-2, dan seterusnya.
• Proses akan berhenti jika tidak ada pertukaran dalam satu iterasi
· Contoh Program Bubble Sort
#include <stdio.h>
#define N 20
int bubble(int n);
int i,j,A[N];
main()
{
int jml;
printf("\t METODE BUBBLE SORT \n\n");
printf("Masukkan jumlah bilangan: ");
scanf("%d",&jml);
printf("\n");
// input data
for (i=0;i<jml;i++)
{
printf("Bilangan ke %d : ",i+1);
scanf("%d",&A[i]);
}
printf("\n");
// mengurutkan data
bubble(jml);
// menampilkan data
printf("Data yang sudah terurut : \n");
for (i=0;i<jml;i++)
{
printf("%d\n",A[i]);
}
}
// fungsi bubble
int bubble(int n)
{
int temp;
for (i=1;i<=n-1;i++)
{
for (j=i;j<n;j++)
{
if (A[i-1]>A[j])
{
temp = A[i-1];
A[i-1] = A[j];
A[j] = temp;
}
}
}
}
Output :
2. Quick Sort Algoritma
Quick Sort adalah algoritma pengurutan yang sangat cepat dengan tipe penyelesaian divide and conquer. sehingga cocok untuk mengurutkan data dalam jumlah besar. Proses pengurutan Quick Sort adalah sebagai berikut:
Proses pengurutan berhenti bila pointer kiri overlap dengan pointer kanan (langkah 8 di gambar atas), sekaligus membagi (divide) 2 bagian yang akan diurutkan selanjutnya; yaitu partisi kiri dan kanan.
 |
| Gambar: Proses sorting tahap ke-2 |
Proses pengurutan dilakukan sama dengan langkah sebelumnya (rekursif) dan dilakukan pada partisi kiri dan kanan. Pembagian partisi berhenti bila tiap partisi hanya menyisakan satu elemen data saja (lihat warna hijau pada langkah 4 di atas).
 |
| Gambar: Proses sorting tahap ke-3 |
Ketika proses pengurutan dilakukan secara rekursif (berulang), maka menghasilkan partisi hanya satu elemen saja dan kemudian digabung kembali sehingga terlihat bahwa data telah berurutan. Untuk lebih jelasnya, anda bisa memahami proses sorting dengan membaca Algoritma Quick Sort di bawah ini:
 |
 |
| Gambar: Hasil running Quick Sort |
Kode Program: Bahasa C++
3. Merge Sort
Algoritma lain yang menggunakan Divide and Conquer dalam pengurutan adalah Merge Sort.
Secara konseptual, untuk sebuah array berukuran n,
Merge Sort bekerja sebagai berikut:
1. Jika bernilai 0 atau 1, maka array sudah terurut.
Merge Sort bekerja sebagai berikut:
1. Jika bernilai 0 atau 1, maka array sudah terurut.
2. Jika Array tidak terurut, bagi menjadi 2 sub-array dengan ukuran n/2
3. Urutkan setiap sub array. Jika sub array tidak cukup kecil lakukan langkah kedua dengan rekursif
4. Menggabungkan sub array menjadi satu array
Berikut ini implementasi sederhana dari Algoritma Merge Sort dengan C++ dan Tool yang digunakan Code Block 8.02
#include <iostream>using namespace std;void merge(int low, int mid, int up);void mergeSort(int low, int up);int a[50];int main(){int jumlahBil,i;cout<<"Masukkan Jumlah element Array"<< endl;cin>>jumlahBil;for(int i=0; i<jumlahBil;i++){cout<<"Bilangan ke-"<< i+1 << endl;cin>>a[i];}mergeSort(1,jumlahBil);for(i=1;i<=jumlahBil;i++)cout<<a[i]<<" ";cout<<endl;return 0;}void merge(int low, int mid, int up){int h, i,j,k;int b[50];h = low;i = low;j = mid+1;while((h<=mid)&&(j<=up)){if(a[h] < a[j]){b[i]=a[h];h++;}else{b[i]=a[j];j++;}i++;}if(h>mid){for(k=j;k<=up;k++){b[i]=a[k];i++;}}else{for(k=h;k<=mid;k++){b[i]=a[k];i++;}}for(k=low;k<=up;k++) a[k]=b[k];}void mergeSort(int low, int up){
int mid;
if(low<up)
{
mid=(low+up)/2;
mergeSort(low,mid);
mergeSort(mid+1,up);
merge(low,mid,up);
}
}
Komentar
Posting Komentar