• urut naik (ascending) yaitu dari data yang mempunyai nilai paling kecil sampai paling besar
• urut turun (descending) yaitu data yang mempunyai nilai paling besar sampai paling kecil. Contoh : data bilangan 5, 2, 6 dan 4 dapat diurutkan naik menjadi 2, 4, 5, 6 atau diurutkan turun menjadi 6, 5, 4, 2. Pada data yang bertipe char, nilai data dikatakan lebih kecil atau lebih besar dari yang lain didasarkan pada urutan relatif (collating sequence) seperti dinyatakan dalam tabel ASCII (Lampiran) Keuntungan dari data yang sudah dalam keadaan terurutkan antara lain :
• data mudah dicari (misalnya dalam buku telepon atau kamus bahasa), mudah untuk dibetulkan, dihapus, disisipi atau digabungkan. Dalam keadaan terurutkan, kita mudah melakukan pengeekan apakah ada data yang hilang
• melakukan komppilasi program komputer jika tabel-tabel simbol harus dibentuk • mempercepat proses pencarian data yang harus dilakukan berulang kali. 48 Data yang diurutkan sangat bervariasi, dalam hal jumlah data maupun jenis data yang akan diurutkan. Tidak ada algoritma terbaik untuk setiap situasi yang kita hadapi, bahkan cukup sulit untuk menentukan algoritma mana yang paling baik untuk situasi tertentu karena ada beberapa faktor yang mempengaruhi efektifitas algoritma pengurutan. Beberapa faktor yang berpengaruh pada efektifitas suatu algoritma pengurutan antara lain:
• banyak data yang diurutkan
• kapasitas pengingat apakah mampu menyimpan semua data yang kita miliki
• tempat penyimpanan data, misalnya piringan, pita atau kartu, atau media penyimpan yang lain. Pemilihan algoritma sangat ditentukan oleh struktur data yang digunakan. Metode pengurutan yang digunakan dapat diklasifikasikan menjadi dua katagori yaitu :
• pengurutan internal, yaitu pengurutan dengan menggunakan larik (array). Larik tersimpan dalam memori utama komputer
• pengurutan eksternal, yaitu pengurutan dengan menggunakan berkas (sequential access file). Berkas tersimpan dalam pengingat luar, misalnya cakram atau pita magnetis. Untuk menggambarkan pengurutan dengan larik, bisa kita bayangkan semua kartu terletak di hadapan kita sehingga semua kartu terlihat dengan jelas nomornya. Pada penyusunan kartu sebagai sebuah berkas, kita bayangkan semua kartu kita tumpuk sehingga hanya kartu bagian atas saja yang bisa kita lihat nomornya.
Sorting bisa didefinisikan sebagai suatu pengurutan data
yang sebelumnya disusun secara acak, sehingga menjadi tersusun secara teratur
menurut aturan tertentu. sorting yang kita terapkan menggunakan tipe data array
agar pemahaman serta pengimplementasiannya lebih mudah
Pada umumnya metode yang digunakan untuk sorting adalah :
1. Buble\Exchange sort
2. Selection sort
3. Shell Sort
4. Quick sort
Bubble/Exchange sort
Diberi nama "Bubble" karena proses pengurutan
secara berangsur-angsur bergera/berpindah ke posisi yang tepat , seperti
gelembung yang keluar dari sebuah gelas bersoda. Bubble sort mengurutkan data
dengan cara membandingkan elemen sekarang dengan elemen berikutnya. jika elemen
sekarang lebih besar dari elemen berikutnya maka elemen tersebut ditukar
(untuk pengurutan ascending) jika elemen sekarang lebih kecil daripada elemen
berikutnya, maka kedua elemen tersebut ditukar (untuk pengurutan
descending). algoritma ini seolanh olah menggeser satu per satu elemen dari
kenan ke kiri atau kiri ke kanan. tergantung jenis pengurutannya. Ketika suatu
proses telah selesai, maka bubble sort akan mengalami proses, demikian
seterusnya. Bubble sort berhenti jika seluruh array telah diperiksa dan tidak
ada pertukaran lagi yang bisa dilakukan,serta tercapai pengurutan yang telah
diinginkan
Contoh pengurutan data yang dilakukan dengan metode bubble sort sebagai berikut :
Proses 1 :
22 10 15 3 8 2
22 10 15 3 2 8
22 10 15 2 3 8
22 10 2 15 3 8
22 10 2 15 3 8
22 2 10 15 3 8
2 22 10 15 3 8
2 22 10 15 3 8
Pengecekan dimulai dari data yang paling akhir, kemudian
dibandingkan dengan data di depannya,jika data didepannya lebih besar maka akan
di tukar.
Proses 2:
2 22 10 15 3 8
2 22 10 15 3 8
2 22 10 3 15 8
2 22 3 10 15 8
2 3 22 10 15 8
pengecekan dilakukan sampai dengan data ke-2 karena data pertama pasti sudah paling kecil.
Proses 3 :
2 3 22 10 15 8
2 3 22 10 8 15
2 3 22 8 10 15
2 3 8 22 10 15
Proses 4 :
2 3 8 22 10 15
2 3 8 22 15 10
2 3 8 15 22 10
Proses 5 :
2 3 8 15 22 10
2 3 8 15 10 22
Pengurutan berhenti
2 22 10 15 3 8
2 22 10 15 3 8
2 22 10 3 15 8
2 22 3 10 15 8
2 3 22 10 15 8
pengecekan dilakukan sampai dengan data ke-2 karena data pertama pasti sudah paling kecil.
Proses 3 :
2 3 22 10 15 8
2 3 22 10 8 15
2 3 22 8 10 15
2 3 8 22 10 15
Proses 4 :
2 3 8 22 10 15
2 3 8 22 15 10
2 3 8 15 22 10
Proses 5 :
2 3 8 15 22 10
2 3 8 15 10 22
Pengurutan berhenti
Contoh Program :
#include
#include
#include
bubble_acak()
{
clrscr();
int arr[1000];
int x, i; //untuk array
int s, t, temp; //untuk sorting
//input jumlah data yang diproses
cout<<"angka yang akan dimasukkan : ";
cin>>x;
//input nilai masing" array
srand(time(NULL));
for (i=0; i
arr[i] = rand() %1000;
//output nilai" array
clrscr();
cout<<"====== array ======"<
cout<<"angka angkanya :"<
for (i=0; i
cout<
//sorting
cout<
cout<<"====== sorting ======"<
s = 0;
for (s=0; s
{
for (t = s+1; t
{
if (arr[s]>arr[t])
{
temp = arr[s];
arr[s] = arr[t];
arr[t] = temp;
}
}
}
cout<<"setelah sorting :"<
for (i=0; i
cout<
getch();
}
bubble_manual()
{
clrscr();
int arr[1000];
int x, i; //untuk array
int s, t, temp; //untuk sorting
//input jumlah data yang diproses
cout<<"angka yang akan dimasukkan : ";
cin>>x;
//input nilai masing" array
for (i=0; i
{
cout<<"masukkan angka ke-"<
cin>>arr[i];
}
//output nilai" array
clrscr();
cout<<"====== array ======"<
cout<<"angka angkanya :"<
for (i=0; i
cout<
//sorting
cout<
cout<<"====== sorting ======"<
s = 0;
for (s=0; s
{
for (t = s+1; t
{
if (arr[s]>arr[t])
{
temp = arr[s];
arr[s] = arr[t];
arr[t] = temp;
}
}
}
cout<<"setelah sorting :"<
for (i=0; i
cout<
//mission complete
getch();
}
main ()
{
int pilih;
char ulang;
do
{
clrscr ();
cout<<"tekan 1 : bilangan yang disorting
dimasukan secara acak"<
cout<<"tekan 2 : bilangan yang disorting
dimasukan secara manual"<
cout<<"masukkan pilihan : ";
cin>>pilih;
switch (pilih)
{
case 1:
bubble_acak();
break;
case 2:
bubble_manual();
break;
default:
clrscr();
cout<<"\"maaf\""<
cout<<"\"pilihan yang dimasukkan
salah\"";
break;
}
cout< "; cin>>ulang;
}
Dalam Procedure Pascal :
Procedure Bubble(Var Temp : Data; JmlData : Integer);
Var I,J : Integer;
Begin
For I:=2 To JmlData Do
For J:=JmlData DownTo I Do
If Temp[J] < Temp[J-1] Then {Untuk Descending
>}
SWAP(Temp[J], Temp[J-1]);
End;
Dalam Procedure SWAP :
Var Temp : Char;
Begin
Temp := A;
A := B;
B := Temp;
End;
Dalam Procedure Pascal :
Procedure Bubble(Var Temp : Data; JmlData : Integer);
Var I,J : Integer;
Begin
For I:=2 To JmlData Do
For J:=JmlData DownTo I Do
If Temp[J] < Temp[J-1] Then {Untuk Descending
>}
SWAP(Temp[J], Temp[J-1]);
End;
Dalam Procedure SWAP :
Var Temp : Char;
Begin
Temp := A;
A := B;
B := Temp;
End;
Selection Sort
Cara kerja metode ini didasarkan pada pencarian elemen
dengan nilai terkecil. kemudian dilakukan penukaran dengan elemen ke-I. Secara
singkat metode ini bisa dijelaskan sebagai berikut. Pada langkah pertama,
dicari data yang terkecil dari data pertama sampai terakhir. Kemudian data
tersebut kita tukar dari data pertama. Dengan demikian, data pertama sekarang
mempunyai nilai paling kecil dibanding dengan data lain. Pada langkah kedua,
data terkecil kita cari mulai dari data kedua sampai data terakhir. Data terkecil
yang kita peroleh kita tukar dengan data kedua. Demikian seterusnya sampai
seluruh data terurut.
Contoh dari proses sorting dengan menggunakan metode
Selection sort :
Dalam Procedure Pascal :
Procedure Shell(Var Temp : Data; JmlData : Integer);
Var I,J, Jarak : Integer;
Begin
Jarak :=
JmlData Div 2;
While Jarak
> 0 Do
Begin
For I:=1 To JmlData-Jarak Do
Begin
J := I +
Jarak;
If Temp[I] >
Temp[J] Then
SWAP(Temp[I],
Temp[Lok]);
End;
Jarak := Jarak Div 2;
End;
End;
Quick Sort
Metode ini dikembangkan oleh CAR Hoare. Secara garis besar
metode ini dijelaskan sebagai berikut. Misalnya kita ingin mengurutkan data A
yang membunyai N elemen. Kita pilih sembarang elemen dari data tersebut,
biasanya elemen pertama, misalnya X. Kemudain semua elemen tersebut disusun
dengan menempatkan X pada posisi J sedemikian rupa shingga elemen ke 1 sampai
ke J-1 mempuyai nilai lebih besar dari X. Sampai berikutnya diulang untuk
setiap sub data.
Contoh dari proses Soring dengan menggunakan metode Quick
Sort
Dalam Procedure Pascal :
Procedure Quick(Var Temp : Data; Awal, Akhir :
Integer);
Var I,J : Integer;
Procedure ATUR;
Begin
I:=Awal +1;
J:= Akhir;
While Temp[I] < Temp[Awal] Do Inc(I);
While Temp[J] > Temp[Awal] Do Dec(J);
While I < J Do
Begin
SWAP(Temp[I],
Temp[J]);
While Temp[I] <
Temp[Awal] Do Inc(I);
While Temp[J] >
Temp[Awal] Do Dec(J);
End;
SWAP(Temp[Awal], Temp[J]);
End;
Begin
If Awal < Akhir Then
Begin
ATUR;
Quick(Temp,
Awal, J-1);
Quick(Temp,J+1,Akhir);
End;
End;
