Struktur Data – Sort & Bubble Sort
SORT ( PENGURUTAN )
Apa itu Sort ( Pengurutan ) ?
Sort atau pengurutan dalam pemprograman digunakan untuk mengurutkan (
baik secara ascending atau descending ) beberapa bilangan / karakter
yang sama tipenya. Sort dipergunakan agar user / pengguna atau
programmer dapat mengetahui nilai yang terkecil sampai dengan nilai
terbesar atau sebaliknya. Sort biasanya digunakan di dalam aplikasi –
aplikasi yang berhubungan dengan banyak data.
Apa ciri – ciri Sort ( Pengurutan ) ?
Pengurutan data dalam struktur data sangat penting untuk data yang bertipe numerik ataupun karakter.
Pengurutan dapat dilakukan secara ascending ( ururt naik ) dan descending ( urut turun )
Pengurutan ( Sorting ) adalah proses menyusun kembali data yang sebelumnya telah tersusun secara teratur menurut aturan tertentu
Metode Pengurutan Data
Pengurutan berdasarkan perbandingan ( comparison – based sorting ) -> Bubble sort, exchange sort
Pengurutan berdasarkan prioritas ( priority queue sorting method ) -> Selection sort, heap sort
Pengurutan berdasarkan penyisipan dan penjagaan terurut ( insert and keep sorted method ) -> Insertion sort, tree sort
Pengurutan berdasarkan pembagian dan penguasaan ( devide and conquer method ) -> Quick sort, merge sort
Pengurutan berkurang menurun ( diminishing increment sort method ) -> Shell sort
Disini saya akan membahas 4 macam teknik sort yakni :
Bubble Sort
Insertion Sort
Quick Sort
Selection Sort
Teknik – teknik tersebut mempunyai tujuan yang sama yakni mengurutkan
data. Teknik yang satu dengan yang lainnya mempunyai kelemahan dan
kelebihan masing – masing.
Apa itu Bubble Sort ?
Metode bubble sort merupakan metode pertama yang paling banyak
dipelajari oleh programmer. Karena lebih sederhana, akan tetapi Bubble
Sort sendiri memiliki kelemahan / kekurangan, seperti :
Bubble sort tidak efisien dan menyita banyak waktu processor dibandingkan dengan metode Sorting yang lain.
Penggunaan bubble sort masih terlihat baik jika jumlah data / elemen
yang diinputkan tidak lebih dari 30 atau kurang dari 30 elemen.
Metode gelembung / penukaran adalah metode yang mendasarkan penukaran
2 buah elemen untuk mencapai keadaan urut yang diinginkan. Disebut
sebagai bubble sort atau gelembung karena algoritma ini memang mirip
tingkah gelembung udara dalam air. Gelembung naik perlahan – lahan ke
permukaan air. Algoritma ini merupakan algoritma paling dasar dan paling
lambat karena tekniknya adalah dengan membandingkan satu angka dengan
angka – angka yang lain dalam deret dan jika angka yang dibandingkan
lebih besar daripada angka pembanding, maka nilainya dipertukarkan (
swap )
Ciri – ciri Bubble Sort
Metode sorting termudah
Merupakan proses pengurutan secara berangsur – angsur bergerak /
berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari
sebuah gelas bersoda
Pengurutan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya
Pengurutan ascending : jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar
Pengurutan descending : jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar
Algoritma ini seolah – olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya
Ketika satu proses telah selesai, maka bubble sort akan mengulangi
proses. Demikian seterusnya dari 0 sampai dengan iterasi sebanyak n – 1
Kapan berhenti ? Bubble sort berhenti jika seluruh array telah diperiksa
dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai
perurutan yang telah diinginkan
Prinsip Kerja Bubble Sort
Pengecekan mulai dari data ke – 1 sampai data ke – n
bandingkan data ke – n dengan data sebelumnya ( n – 1 )
Jika lebih kecil maka pindahkan bilangan tersebut dengan bilangan yang
ad didepannya ( sebelumnya ) satu persatu ( n-1, n-2, n-3, …dst )
Jika lebih besar maka tidak terjadi pemindahan
Ulangi langkah 2 dan 3 s/d sort optimal
Bagaimana cara kerja bubble sort ?
Mari kita coba mengurutkan deret array 5 1 4 2 8 , dari angka
terendah ke angka terbesar menggunakan bubble sort. Dalam setiap langkah
unsur – unsur yang ditulis dalam huruf tebal sedang dibandingkan.
Disini, algoritam membandingkan dua elemen pertama, dan mereka swap.
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ) 5 > 1 maka posisi di tukar
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ) 5 > 4 maka posisi di tukar
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ) 5 > 2 maka posisi di tukar
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ) 5 < 8 maka algoritma tidak menukar
posisi Fase Ke-2 Kini deret sudah tersortir, namun algoritma yang
berjalan belum selesai, algoritma masih mengecek deret hingga benar –
benar deret tidak ada lagi yang di swap / di tukar. ( 1 2 4 5 8 ) –> (
1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Contoh Program Bubble Sort
Contoh 1
void bubble_sort () {
for ( int i=1;i<n;i++){ for ( int j=n-1;j>=i;j–){
if ( data[j]<data[j-1])
tukar (&data[j],&data[j-1]);
//ascending
}
}
}
Keterangan contoh 1
Dengan prosedur diatas, data terurut naik ( ascending ), untuk urut turun ( descending ) silahkan ubah bagian:
if ( data[j]<data[j-1]) tukar (&data[j],&data[j-1]); MENJADI if (data[j]>data[j-1])
tukar (&data[j],&data[j-1]);
Bubble sort paling mudah algoritmanya tetapi paling lambat dibandingkan algoritam lain
Contoh 2
#include
void main ()
{
int i,n,x,j,arr[25];
printf (“Masukkan Banyaknya Array yang ingin di Sort: “);
scanf (“%d”,&n);
printf ( “\nMasukkan Array:\n\n”);
for (i=0 ; i {
printf (” Array[%d] = “,i);
scanf (“%d”,&arr[i]);
}
//proses pengurutan
for (i=0 ; i {
for (j=0 ; jarr[j+1])
{
x=arr[j];
arr[j]=arr[j+1];
arr[j+1]=x;
}
}
}
//lihat hasil sortir
printf (“\nHasil Pensortirannya adalah:\n\n”);
{
printf (“%4d\n”,arr[i]);
}
}
SUMBER
http://melinda-dwihastuti.blogspot.co.id/2015/02/materi-struktur-data.html
