Fighting....!!!!!

Fighting....!!!!!

Sabtu, 16 Juni 2012

Sorting (pengurutan)


 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.”
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 pada
kode 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.
Contoh lain penggunaan algoritma selection sort , kita gunakan PHP, sebagai  berikut :
<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