Sorting adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu ataupun secara acak, sehingga menjadi tersusun secara teratur menurut aturan tertentu.
Pada umumnya ada 2 macam pengurutan, yaitu:
* Pengurutan secara ascending (urut naik)
* Pengurutan secara descending (urut turun)
Jenis – jenis sorting ada 5 yaitu :
(-) bUBBlE sort
(-) Exchange Sort
(-) sELection sort
(-) inSert soRt
(-) Quick SorT
a). BUBBLE SORT
:: metode paling sederhana dalam mengurutkan data
:: tapi kinerja paling buruk jika data dalam jumlah besar
:: terdapat istilah descending ( dari besar ke kecil ) dan ascending ( dari kecil ke besar )
:: pengurutan dilakukan dengan membandingkan setiap elemen yang terletak setelah posisinya
:: contoh program :
void bubble_sort1 ( int data [ ] )
{
for ( int i=1 ; i
{
for ( int j=n-1 ; j>=i ; j-- )
{
if ( data[ j ] < style=""> // ascending
}
}
}
void bubble_sort2 ( int data [ ] )
{
for ( int i=1 ; i<6>
{
for ( int j=0 ; j<6-i>
{
if ( data[ j ] > data[ j+1] tukar ( &data[ j ],&data[ j+1] ); // descending
}
}
}
b). EXCHANGE SORT
:: sangat mirip dengan bubble sort, perbedaanny hanya dalam hal bagaimana membandingkan antar elemennya
:: exchange sort membandingkan suatu elemen dengan elemen lainnya dalam array tsb, dan melakukan pertukaran elemen jika perlu, jadi ada elemen yang selalu menjadi elemen pusat ( pivot )
:: contoh program :
void exchange_sort ( int data [ ] )
{
for ( int i=0 ; i
{
for ( int j=i+1 ; j
{
if ( data[ i ] < style="">
}
}
}
c). SELECTION SORT
:: Kombinasi sorting dan searching.
:: Metode sorting ini menggunakan ide menemukan data dengan nilai terbesar dalam array lalumemindahkannya ke bagian akhir array ( jika array harus dalam urutan dari kecil ke besar ). Jikaterbesar sudah berada di posisi yang benar, kita bisa menerapkan hal yang sama untuk data yang tersisa lainnya. Yaitu, menemukan data terbesar berikutnya dan memindahkan ke bagian akhir
:: Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.
:: Contoh fungsi selection sort :
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) ;
}
d) INSERTION SORT
:: Metode sorting ini bisa diterapkan dalam menjaga array dalam urutan tertentu. Misalkan kita memiliki array yang telah tersortir dan kita ingin memasukkan sebuah data ke dalam array. Jika kita ingin memastikan bahwa array yang telah berubah tersebut masih tetap dalam urutan tertentu, maka data baru harus dimasukkan dalam posisi tertentu yang tepat, misalnya semua data yang memiliki nilai lebih kecil berada sebelumnya dan data yang lebih besar berada di posisi sesudahnya. Ini berarti memindahkan setiap data yang lebih besar satu elemen ke kanan, sehingga terbentuk sebuah ruang kosong untuk elemen baru ini
:: Misal ascending : pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan dimasukkan di posisi yang seharusnya.
:: Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.
:: Contoh program insertion sort :
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 ;
}
e). QUICK SORT
:: Merupakan metode sorting yang paling cepat ( saat ini tercepat ).
:: Quick sort adalah sebuah algoritma rekursif
:: Algoritma Quicksort didasarkan pada sebuah ide yang sederhana : Diberikan sebuah
array, pilih data manapun dari array. Data yang dipilih tersebut selanjutnya kita sebut
pivot. ( Dalam praktek kali ini, kita akan gunakan data pertama dari array ) Pindah semua data yang lebih kecil dari pivot ke bagian awal list, dan pindahkan semua data yang lebih besar dari pivot ke akhir dari list. Sekarang, taruh pivot diantara dua kumpulan data tadi. Posisi pivot tersebutsudah tidak akan dipindah-pindah lagi. Kita sebut prosedur tersebut QuicksortStep
:: QuicksortStep tidak rekursif, ia hanya digunakan sebagai subroutine oleh Quicksort.
Dengan subroutine QuicksortStep ini, Quicksort menjadi mudah. Algoritma Quicksort
70 untuk melakukan sorting pada sebuah array menerapkan QuicksortStep pada array,
kemudian menerapkan Quicksort secara rekursif pada data yang berada di sebelah kiri
dan sebelah kanan pivot
:: contoh program :
void QuickSort ( int L,int R )
{
int I , j ;
int mid ;
i = L ;
j = R ;
mid = data[ (L+R) / 2] ;
do
{
while( data[ I ] <>
while( data[ j ] > mid ) j--;
if( i <=j )
{
tukar( i,j );
i++;
j--;
}
}
while( i
if( L <>
if( i > R ) QuickSort( i,R );
}
