Pengurutan (Sorting)


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 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.
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 bab ini akan dijelaskan beberapa metode pengurutan beserta analisanya.



6.1 Deklarasi Larik

Pada pengurutan larik, ada beberapa aspek yang perlu dipertimbangkan, antara lain aspek menyangkut kapasitas pengingat yang ada dan aspek waktu, yaitu waktu yang diperlukan   untuk  melakukan  permutasi  sehingga  semua  elemen  akhirnya  menjadi terurutkan.
Deklarasi  larik  yang  digunakan  adalah  larik  dimensi  satu  (vektor)  dengan elemennya bertipe integer.


#define  Max 100;

int Data[Max];


Pada  deklarasi  diatas,  Max adalah  banyaknya  elemen  vektor.        Anda  bisa mengubah nilai konstantaa Max sesuai kebutuhan.  Indeks larik dimulai dari 0.  Data yang sebenarnya disimpan mulai dari indeks 0.
Selain  deklarasi  diatas,  proses  yang  juga  selalu  digunakan  pada  algoritma pengurutan adalah proses menukarkan elemen.  Di bawah ini satu prosedur sederhana untuk menukarkan nilai dua buah elemen A dan B.


void Tukar (int *a, int *b)

{



int temp;

temp = *a;

*a = *b;

*b = temp;

}



Program 6.1 Prosedur Penukaran 2 Bilangan




Prosedur tukar diatas akan digunakan pada beberapa prosedur pengurutan yang akan dijelaskan dibawah ini


6.2 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.



Tabel 6.1  Proses Pengurutan dengan Metode Penyisipan Langsung

Iterasi
Data[0]
Data[1]
Data[2]
Data[3]
Data[4]
Data[5]
Data[6]
Data[7]
Data[8]
Data[9]
Awal
12
35
9
11
3
17
23
15
31
20
i=1
12
35
9
11
3
17
23
15
31
20
i=2
12
35
9
11
3
17
23
15
31
20
i=3
9
12
35
11
3
17
23
15
31
20
i=4
9
11
12
35
3
17
23
15
31
20
i=5
3
9
11
12
35
17
23
15
31
20
i=6
3
9
11
12
17
35
23
15
31
20
i=7
3
9
11
12
17
23
35
15
31
20
i=8
3
9
11
12
15
17
23
35
31
20
i=9
3
9
11
12
15
17
23
31
35
20
Akhir
3
9
11
12
15
17
20
23
31
35


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;

}

}

Program 6.2 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



6.3 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.1 diatas, pada saat i=4, data ke 0 s/d 3 sudah dalam keadaan urut : 3, 9, 12, 35.




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 adalah sebagai berikut :

3
9
11
12
17
23
35
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.  Oleh karena itu, proses pencarian dlanjutkan lagi untuk
data berikut

17          23          35


Dari hasil ini, didapat data tengahnya adalah data 23.  Karena 15 < 23, berarti 15 harus disisipkan di sebelah kiri 23. Proses dilanjutkan kembali untuk data

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;

}

}


Program 6.3 Prosedur Pengurutan dengan Metode Penyisipan Biner


Dari algoritma dan  prosedur  diatas,  jumlah  perbandingan (=C)  untuk  metode penyisipan biner adalah :
C =  2log(i)

Sedangkan  jumlah  penggeseran  (=M)  untuk  metode  penyisipan  biner  sama dengan metode penyisipan langsung.



6.4 Metode Seleksi (Selection Sort)

Metode seleksi melakukan pengurutan dengan cara mencari data yang terkecil kemudian  menukarkannya dengan  data  yang  digunakan  sebagai  acuan  atau  sering dinamakan pivot.
Proses pengurutan dengan metode seleksi dapat dijelaskan sebagai berikut : langkah pertama dicari data terkecil dari data pertama sampai data terakhir.  Kemudian data terkecil  ditukar dengan data pertama.                                                                            Dengan demikian, data pertama sekarang
mempunyai nilai paling kecil dibanding data yang lain.  Langkah kedua, data terkecil kita

cari mulai dari data kedua sampai terakhir.  Data terkecil yang kita peroleh ditukar dengan data kedua dan demikian seterusnya sampai semua elemen dalam keadaan terurutkan.
Algoritma seleksi dapat dituliskan sebagai berikut :

1          i 0

2          selama (i < N-1) kerjakan baris 3 sampai dengan 9

3          k i

4          j i + 1

5          Selama (j < N) kerjakan baris 6 dan 7

6          Jika (Data[k] > Data[j]) maka k j

7          j j + 1

8          Tukar Data[i] dengan Data[k]

9          i i + 1

Untuk lebih memperjelas langkah-langkah algoritma seleksi dapat dilihat pada tabel 6.2. Proses pengurutan pada tabel 6.2 dapat dijelaskan sebagai berikut:
    Pada saat i=0, data terkecil antara data ke-1 s/d ke-9 adalah data ke-4, yaitu 3, maka data ke-0 yaitu 12 ditukar dengan data ke-4 yaitu 3.
    Pada saat i=1, data terkecil antara data ke-2 s/d ke-9 adalah data ke-2, yaitu 9, maka data ke-1 yaitu 35 ditukar dengan data ke-2 yaitu 9.
    Pada saat i=2, data terkecil antara data ke-3 s/d ke-9 adalah data ke-3, yaitu 11, maka data ke-2 yaitu 35 ditukar dengan data ke-3 yaitu 11.
    Pada saat i=3, data terkecil antara data ke-4 s/d ke-9 adalah data ke-4, yaitu 12, maka data ke-3 yaitu 35 ditukar dengan data ke-4 yaitu 12.
    Dan seterusnya.



Tabel 6.2  Proses Pengurutan dengan Metode Seleksi

Iterasi
Data[0]
Data[1]
Data[2]
Data[3]
Data[4]
Data[5]
Data[6]
Data[7]
Data[8]
Data[9]
Awal
12
35
9
11
3
17
23
15
31
20
i=0
12
35
9
11
3
17
23
15
31
20
i=1
3
35
9
11
12
17
23
15
31
20
i=2
3
9
35
11
12
17
23
15
31
20
i=3
3
9
11
35
12
17
23
15
31
20
i=4
3
9
11
12
35
17
23
15
31
20
i=5
3
9
11
12
15
17
23
35
31
20
i=6
3
9
11
12
15
17
23
35
31
20
i=7
3
9
11
12
15
17
20
35
31
23
i=8
3
9
11
12
15
17
20
23
31
35
Akhir
3
9
11
12
15
17
20
23
31
35



Di bawah ini merupakan prosedur yang menggunakan metode seleksi.



void SelectionSort()

{

int i, j, k;

for(i=0; i<Max-1;i++){

k = i;

for (j=i+1; j<Max; j++)

if(Data[k] > Data[j])
k = j; Tukar(&Data[i], &Data[k]);

}

}

Program 6.4 Prosedur Pengurutan dengan Metode Seleksi






adalah


Dari algoritma dan prosedur diatas, jumlah perbandingan (=C) metode seleksi



C = N(N 1) / 2

Jumlah  penukaran  (=M)  pada  metode  seleksi  tergantung  keadaan  datanya.



Penukaran minimum  terjadi  bila  data  sudah  dalam  keadaan  urut,  sebaliknya jumlah penukaran maksimum terjadi bila data dalam keadaan urut terbalik.  Jumlah penukaran minimum dan maksimum dapat dirumuskan sebagai berikut :
Mmin = 3(N 1)

Mmax  = N2  / 4 + 3(N 1)



SEBELUM ANDA ANDA MENGCOPY PASTE SELURUH ARTIKEL INI, MOHON DI SERTAKAN SUMBERNYA 
SHARE KLIK ICON FB / TWITTER DI KANAN ATAS

0 komentar:

 
Easyonlineplace © 2013. All Rights Reserved. Powered by Blogger
Top