PENGURUTAN
BILANGAN
Pengurutan data (sorting) didefinisikan sebagai suatu
proses untuk menyusun
kembali humpunan obyek menggunakan aturan tertentu.
Mnurut Microsoft Book-shelf,
definisi algoritma pengurutan adalah algoritma untuk
meletakkan kumpulan elemen data ke dalam urutan tertentu berdasarkan satu atau
beberapa kunci dalam tiap-tiap elemen. Ada dua macam urutan yang biasa digunakan dalam proses
pengurutan yaitu:
• 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
ataulebih besar dari yang lain didasarkan pada urutan relatif (collating sequence) seperti dinyatakan dalam tabel ASCII
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.
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.
Pada
Pembahasan ini akan dijelaskan beberapa
metode pengurutan beserta analisanya.
Metode Bubble Sort
PROSES PENGURUTAN
Untuk mengurutkan bilangan diperlukan variabel array untuk menampung semua
bilangan yang akan diurutkan. Proses pengurutan dilakukan dengan membandingkan
semua elemen array satu per satu.
Dimetode bubble sort, proses pengurutan dimulai dengan membandingkan elemen
pertama untuk mendapatkan angka terbesar. Lalu angka 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 berubah menjadi :
Lalu elemen ke-2 dibandingkan dengan elemen ke-3. jika isi elemen ke-3
lebih besar, maka isi kedua elemen tersebut tidak ditukar.
Perbandingan selanjutnya dilakukan
terhadap elemen ke-3 dengan ke-4. Karena elemen ke-4 lebih kecil, maka isi
kedua elemen tersebut ditukar. Sehingga isi array sebelumnya berubah menjadi :
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.
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. Lanjutkan proses diatas sampai
pada elemen ke-7.
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.
IMPLEMENTASI DALAM BENTUK FLOWCHART
Seperti telah dijelaskan sebelumnya, proses pengurutan memakai variabel
array untuk menampung semua bilangan yang akan diurutkan. Oleh karena itu
sebelum proses pengurutan dilakukan, terlebih dahulu dibuat proses untuk
mengisi semua bilangan ke dalam array. Setelah array tersebut terisi, barulah
proses pengurutan dilakukan untuk mengurutkan isinya.
Seperti diketahui, jika salah satu elemen array diisi dengan nilai baru,
maka nilai lama akan terhapus. Oleh sebab itu untuk mempertukarkan isi elemen
array harus mengggunakan satu variabel cadangan. Variabel ini digunakan untuk
menyimpan isi array yang akan ditukar.
Misalnya isi elemen ke-2 dari variabel BILARR akan ditukar dengan elemen
ke-3. Maka isi elemen ke-2 disimpan terlebih dahulu ke variabel cadangan (
misalnya untuk variabel ini diberi nama TEMP). Setelah itu, isi elemen ke-3
dipindahkan ke elemen ke-2, lalu isi dari variabel TEMP dipindahkan ke elemen
ke-3. Ilustrasi dibawah ini memperlihatkan pertukaran kedua elemen tersebut.
Berdasarkan flowchart proses pengurutan bilangan dari kecil ke besar dapat
dirangkum sebagai berikut :
1. persiapan variabel yang dipakai dalam proses, yaitu :
N : variabel untuk menyatakan jumlah elemen array. Jumlah ini diketahui
berdasarkan banyaknya bilangan yang diinputkan melalui keyboard.
I, J : variabel indeks untuk
membandingkan isi array
2. prose pertama yang dilakukan adalah mengisi semua bilangan yang akan
diurutkan ke array. Pada flowchart diatas, array tersebut diberi nama BILARR.
Bilangan diinput melalui keyboard dan disimpan didalam variabel BIL.
3. periksa isi variabel BIL. Pada flowchart diatas, diasumsikan pengisian
bilangan berakhir jika operator mengetik 0 untuk bilangan yang diinput. Oleh
karena itu, jika BIL = 0 maka proses dilanjutkan ke langkah 7 untuk mulai
pengurutan bilangan. Jika BIL tidak sama dengan 0 berarti pengisian bilnagan
belum berakhir, maka proses dilanjutkan ke langkah 4.
4. variabel N ditambah 1. variabel ini untuk menentukan elemen array yang
akan diisi nilai dari variabel BIL.
5. isi elemen array dengan nilai yang tersimpan di variabel BIL. Posisi
elemen tersebut ditentukan berdasarkan harga N.
6. kembali ke langkah 2 untuk menginput bilangan lainnya.
7. variabel J ditambah 1.
8. variabel I ditambah 1.
9. bandingkan isi elemen array pada posisi sesuai dengan nilai variabel I
atau BILARR (I) dengan elemen array didepannya yaitu posisi I+1 atau BILARR
(I+1). Jika isi BILARR(I) lebih kecil dari BILARR (I+1) maka isi kedua elemen
tersebut tidak ditukar. Untuk itu proses dilanjutkan ke lankah 11. namun juka
isi BILARR(I) > dari BILARR(I+1) lanjutkan ke langkah 10 untuk menukar isi
kedua elemen tersebut.
10. pindahkan isi BILARR(I) ke variabel sementara yaitu TEMP.
pindahkan isi BILARR(I+1) ke BILARR(I).
pindahkan isi TEMP ke BILARR(I+1).
11. periksa isi variabel I. jika I sama dengan N-J maka proses perbandingan
untuk mencari bilangan terbesar pertama selesai. Untuk itu proses dilanjutkan
ke langkah 12. jika isi I belum sama, maka proses perbandingan untuk mencari
bilangan terbesar belum selesai. Untuk itu proses selanjutnya kembali ke
langkah 8.
12. periksa isi variabel J. jika J sama dengan N-1, maka semua elemen telah
diperbandingkan dan proses pengurutan telah selesai. Untuk itu proses
dilanjutkan ke langkah 15 untuk mencetak seluruh isi arrray. Jika isi J masih
belum sama dengan N-1 maka semua bilangan belum terurut. Proses dilanjutkan ke
langkah 13 untuk mencari bilangan terbesar lainnya.
13. variabel I diisi nilai 0.
14. kembali ke langkah 7 untuk mencari bilangan terbesar lainnya.
15. Variabel I diisi nilai 0.
16. variabel I ditambah 1.
17. cetak isi BILARR(I).
18. periksa isi I. jika I sama dengan N berarti semua elemen array telah
dicetak maka proses selesai. Jika isi I belum sama dengan N berarti semua
elemen array belum tercetak. Untuk itu kembali ke langkah 16 untuk mencetak elemen
lainnya.
Metode Selection Sort
Selection Sort
salah satu algoritma pengurutan yang mudah untuk dipelajari.
Konsep dasarnya yaitu : “Melakukan pencarian data terkecil/terbesar pada suatu iterasi. Kemudian data tersebut ditukar dengan data[index]. index=iterasi. Jumlah iterasi ditentukan oleh banyaknya data atau ‘N’. Iterasi=N-1.”
Konsep dasarnya yaitu : “Melakukan pencarian data terkecil/terbesar pada suatu iterasi. Kemudian data tersebut ditukar dengan data[index]. index=iterasi. Jumlah iterasi ditentukan oleh banyaknya data atau ‘N’. Iterasi=N-1.”
Selection
Sort adalah sebuah algoritma pengurutan, dimana data terkecil / terbesar akan
ditempatkan di awal atau di akhir data. Berbeda dengan Bubble Sort yang langsung menukarkan data jika ditemukan,
maka dalam selection sort setelah data yang “nyeleneh” alias tidak terurut
ditemukan, tidak akan langsung ditukarkan melainkan akan ditandai terlebih
dahulu sebagai data terkecil / terbesar dalam satu iterasi.
Pengurutan Seleksi ada dua macam, yaitu :1. Pengurutan Seleksi Minimum
Sesuai dengan namanya, maka yang dijadikan acuan dalam satu iterasi adalah data terkecil. Untuk lebih jelasnya bisa dilihat pada syntax dibawah ini
#include<iostream.h>
#include<conio.h>
class seleksi{
static int A[10];
public:
void seleksi_maksimum();
void tampil();
};
int seleksi::A[10]={54,23,12,56,78,50,12,89,10,12};
void seleksi::tampil(){
for(int a=0;a<10;a++) cout<<A[a]<<" ";
cout<<endl<<endl;
}
void seleksi::seleksi_maksimum(){
int i,j,imax,temp;
for(i=10;i>=0;i--){
imax=i;
for(j=i-1;j>=0;j--){
if(A[j]>A[imax]){
imax=j;
}
}
temp=A[i];
A[i]=A[imax];
A[imax]=temp;
}
}
main(){
cout<<"SELEKSI MAKSIMUM"<<endl<<endl;
seleksi x;
cout<<"Sebelum diurut : "<<endl<<"A = ";
x.tampil();
x.seleksi_maksimum();
cout<<"Setelah diurut : "<<endl<<"A = ";
x.tampil();
getch();
}
Pada
dasarnya, data paling ujung akan di anggap sebagai data terbesar. Data terbesar
ini kemudian akan dibandingkan dengan data sebelumnya. Jika ternyata data
sebelumnya lebih besar, maka “gelar” data terbesar / imax akan diwariskan ke
data sebelumnya.
imax=i;for(j=i-1;j>=0;j--){if(A[j]>A[imax]){imax=j;}}
Begitu seterusnya, sampai pengulangan berhenti. Jika
pengulangan sudah berhenti, maka barulah akan terjadi penukaran data
temp=A[i];A[i]=A[imax];A[imax]=temp;
2. Pengurutan Seleksi Minimum
Ini adalah kebalikan dari Pengurutan Seleksi Maksimum ,
dimana disini yang dijadikan acuan adalah data terkecil. Untuk lebih jelasnya bisa dilihat padakode dibawah :
#include<conio.h>
#include<stddef.h>
#include<iomanip.h>
class seleksi{
static int bil[8];
public :
void seleksi_minimum();
void tampil();
};
int seleksi::bil[8]={5,34,32,25,75,42,22,2};
void seleksi::tampil(){
for( int a=0;a<8;a++) cout<<setw(3)<<bil[a];
cout<<endl<<endl;
}
void seleksi::seleksi_minimum(){
int i,j,smallest,temp;
for(i=0;i<8-1;i++){
smallest = i;
for(j=i+1;j<8;j++){
if(bil[smallest]>bil[j]){
smallest=j;
}
}
temp=bil[i];
bil[i]=bil[smallest];
bil[smallest]=temp;
}
}
void main(){
seleksi x;
cout<<"Data sebelum diurutkan : ";
x.tampil();
x.seleksi_minimum();
cout<<"Data setelah diurutkan : ";
x.tampil();
getch();
}
Perhatikan bahwa algoritma diatas sama saja dengan
pengurutan seleksi maksimum, hanya saja disini yang dijadikan acuan adalah data
terkecil (smallest), sehingga “gelar” disini bukan lagi imax, melainkan
smallest.
<html><head><title>$ Sorting Algorithm $</title></head>
<body>
<h2>Algoritma Selection Sort</h2>
<font size=4>
<?PHP
//data awal
$data[0]=5; $data[3]=7;
$data[1]=2; $data[4]=6;
$data[2]=4; $data[5]=3;
echo"<b>Jumlah Data : 6</b><br>";
echo"<b>Data Awal : </b>";
//menampilkan data awal
for($i=0;$i<=5;$i++)
{
echo"$data[$i] ";
}
echo"<br><br>";
//——–Algoritma Selection Sort
for($j=0;$j<=5-1;$j++)
{
$BilMin=$data[$j];
for($k=$j+1;$k<=5;$k++)
{
if($data[$k]<$BilMin)
{
$BilMin=$data[$k];
$Posisi=$k;
}
//Algo Tukar…
$Temp=$data[$j];
$data[$j]=$data[$Posisi];
$data[$Posisi]=$Temp;
}
//menampilkan data tiap Iterasi
$NoIte=$j+1;
echo"Iterasi ke-$NoIte : ";
for($i=0;$i<=5;$i++)
{
echo"$data[$i] ";
}
echo"<br>";
//——-
}
?>
</font>
</body>
</html>
Metode Insertion Sort
Metode Insertion Sort
ada 2 jenis,yaitu :
1.
Metode Penyisipan Langsung
2. Metode Penyisipan Biner
Penjelasan materi tersebut sebagai berikut.
Metode
Penyisipan Langsung (Straight Insertion Sort)
Proses pengurutan dengan
metode penyisipan langsung dapat dijelaskan sebagai berikut :
Data dicek satu per satu mulai
dari yang kedua sampai dengan yang terakhir. Apabila
ditemukan data yang lebih
kecil daripada data sebelumnya, maka data tersebut disisipkan
pada posisi yang sesuai. Akan
lebih mudah apabila membayangkan pengurutan kartu.
Pertama-tama anda meletakkan
kartu-kartu tersebut di atas meja, kemudian melihatnya
dari kiri ke kanan. Apabila
kartu di sebelah kanan lebih kecil daripada kartu di sebelah
kiri, maka ambil kartu
tersebut dan sisipkan di tempat yang sesuai.
Algoritma penyisipan langsung dapat dituliskan sebagai
berikut :
1. i ← 1
2. selama (i < N) kerjakan baris 3 sampai dengan 9
3. x ← Data[i]
4. j ← i – 1
5. selama (x < Data[j]) kerjakan baris 6 dan 7
6. Data[j + 1] ← Data[j]
7. j ← j – 1
8. Data[j+1] ← x
9. i ← i + 1
Untuk lebih memperjelas
langkah-langkah algoritma penyisipan langsung dapat
dilihat pada tabel 6.1. Proses pengurutan pada tabel 6.1 dapat dijelaskan sebagai
berikut:
• Pada saat i=1, x sama dengan Data[1] = 35 dan j=0. Karena
Data[0] = 12 dan 35 > 12
maka proses dilanjutkan untuk i=2.
• Pada saat i=2, x = Data[2] = 9 dan j=1. Karena Data[1]
= 35 dan 9 < 35, maka
dilakukan pergeseran sampai ditemukan data yang lebih
kecil dari 9. Hasil
pergeseran ini, Data[1] = 12 dan Data[2] = 35
sedangkan Data[0] = x = 9.
• Pada saat i=3, x = Data[3] = 11 dan j=3. Karena Dataa[2]
= 35 dan 11 < 35, maka
dilakukan pergeseran sampai ditemukan data yang lebih
kecil dari 11. Hasil
pergeseran ini, Data[2] = 12 dan Data[3] = 35
sedangkan Data[1] = x = 11.
• Dan seterusnya.
Di bawah ini merupakan
prosedur yang menggunakan metode penyisipan
langsung.
void StraighInsertSort()
{
int i, j, x;
for(i=1; i<Max; i++){
x = Data[i];
j = i - 1;
while (x < Data[j]){
Data[j+1] = Data[j];
j--;
}
Data[j+1] = x;
}
}
Prosedur Pengurutan dengan Metode Penyisipan Langsung
Dari algoritma dan prosedur
diatas, jumlah perbandingan (=C) minimum, rata-rata dan maksimum pada metode penyisipan
langsung adalah
Cmin = N
– 1
Crata-rata = (N2 + N + 2) / 4
Cmax =
(N2 + N – 2) / 2
Jumlah perbandingan minimum
terjadi jika data sudah dalam keadaan urut,
sebaliknya jumlah perbandingan maksimum terjadi jika
data dalam keadaan urut terbalik.
Cara menghitung Cmin adalah dengan melihat kalang
paling luar yaitu i,
pengulangan ini dimulai dari 1 sampai dengan N-1 atau
sama dengan N-1
Cara menghitung Cmax dengan menganggap selalu
terjadi pergeseran. Kalang
dalam (while) diatas akan melakukan pengulangan dari 0
sampai dengan i. Apabila hal
ini dilakukan sebanyak N-1 kali, maka Cmax adalah jumlah dari deret
aritmetik 2, 3, 4, ..., N atau (N – 1) / 2 . (2 + N)
Cara menghitung Crata-rata adalah
dengan menjumlahkan Cmin dan Cmax dan dibagi dengan 2. Jumlah penggeseran (=M) minimum, rata-rata dan
maksimum untuk metode penyisipan langsung adalah :
Mmin = 2(N – 1)
Mrata-rata = (N2 + 7N - 8) / 4
Mmax =
(N2 + 3N – 4) / 2
Metode Penyisipan Biner (Binary Insertion Sort)
Metode ini merupakan
pengembangan dari metode penyisipan langsung. Dengan cara penyisipan langsung,
perbandingan selalu dimulai dari elemen pertama (data ke-0), sehingga untuk
menyisipkan elemen ke i kita harus melakukan perbandingan sebanyak i-1 kali.
Ide dari metode ini didasarkan pada kenyataan bahwa pada saat menggeser data ke-i,
data ke 0 s/d i-1 sebenarnya sudah dalam keadaan terurut. Sebagai contoh pada tabel
6. Dengan demikian posisi dari data ke-i sebenarnya dapat ditentukan dengan
pencarian biner.
Misalnya pada saat i = 7, data
yang akan dipindah adalah 15 sedangkan data di
sebelah kiri 15.
Pertama-tama dicari data
pada posisi paling tengah diantara data diatas. Data
yang terletak di tengah adalah data ke-3, yaitu 12.
Karena 12 < 15, berarti 15 harus
disisipkan di sebelah kanan 12.
Dari hasil ini, didapat data tengahnya adalah data 23.
Karena 15 < 23, berarti 15 harus
disisipkan di sebelah kiri 23.
Karena 17 > 15, berarti 15 harus disisipkan di sebelah
kiri 17. Algoritma penyisipan biner dapat dituliskan sebagai berikut :
1. i ← 1
2. selama (i < N) kerjakan baris 3 sampai dengan 14
3. x ← Data[i]
4. l ← 0
5. r ← i – 1
6. selama (l<=r) kerjakan baris 7 dan 8
7. m ← (l + r) / 2
8. jika (x < Data[m]) maka r ← m – 1, jika tidak l ← m + 1
9. j ← i – 1
10. selama ( j >=l) kerjakan baris 11 dan 12
11. Data[j+1] ← Data[j]
12. j ← j – 1
13. Data[l] ← x
14. I ← i + 1
Di bawah ini merupakan
prosedur yang menggunakan metode penyisipan biner.
void BinaryInsertSort()
{
int i, j, l, r, m, x;
for (i=1; i<Max; i++){
x = Data[i];
l = 0;
r = i - 1;
while(l <= r){
m = (l + r) / 2;
if(x
< Data[m])
r
= m - 1;
else
l
= m + 1;
}
for(j=i-1;
j>=l; j--)
Data[j+1] = Data[j];
Data[l]=x;
}
}
Tidak ada komentar:
Posting Komentar