PENGURUTAN

9.1  Definisi
Pengurutan adalah proses mengatur sekumpulan objek/ data menurut urutan atau susunan tertentu. Susunan pengurutan ada dua macam, yaitu:
1.      Menaik (Ascending)
Pengurutan dengan susunan dari objek data terkecil ke objek data terbesar.
L[1] £ L[2] £ L[3] £ ………… £  L[n]
2.      Menurun (Descending)
Pengurutan dengan susunan dari objek data terbesar ke objek data terkecil.
L[1] ³ L[2] ³ L[3] ³ ………… ³  L[n]
Klasifikasi pengurutan:
Pengurutan Internal
Metode pengurutan untuk data yang disimpan di dalam memory komputer, umumnya memakai struktur larik sehingga disebut pengurutan larik.
Pengurutan Eksternal
Pengurutan untuk data yang disimpan dalam disk storage, disebut pengurutan arsip/ file
Pada mata kuliah ini hanya dibahas untuk pengurutan larik (internal) saja.
Macam-macam metode pengurutan:
Bubble Sort (Pengurutan Apung)
Selection Sort (Pengurutan Seleksi/ Pilihan)
Insertion Sort (Pengurutan Sisipan)
Shell Sort
Dsb.
Semua metode pengurutan selalu melakukan perbandingan elemen larik untuk menemukan posisi urutan yang tepat.
Pada dasarnya tidak ada metode terbaik untuk pengurutan. Pengurutan metode sederhana hanya bagus untuk data yang kecil. Sebaliknya pengurutan metode cepat (quick sort dan merge sort) bagus untuk volume data yang besar tetapi jika diterapkan pada volume data yang kecil menjadi tidak bagus karena memerlukan beban tambahan (overhead) yang boros waktu dan memori.

9.2  Bubble Sort
Pengurutan metode apung diinspirasi oleh gelembung sabun yang selalu berada di permukaan air. Prinsip metode ini adalah membandingkan kemudian mempertukarkan.

Algoritma pengurutan apung secara ascending:
Untuk setiap pass I = 1, 2, …., n-1, lakukan:
Mulai dari elemen k = n, n-1, ……, i+1, lakukan
Bandingkan L[k] dengan l[k-1]
Pertukarkan L[k] dengan L[k-1] jika L[k] < L[k-1]
Contoh:
Terdapat larik sebagai berikut:
            25        27        10        8          76        21
Akan dilakukan pengurutan dengan metode apung
            Pass 1 à 8      25        27        10        21        76
            Pass 2 à 8      10        25        27        21        76
            Pass 3 à 8      25        21        27        10        76
            Pass 4 à 8      25        27        10        21        76
            Pass 5 à 8      25        27        10        21        76




Pseudocode pengurutan apung secara ascending:
Algoritma apung_menaik;
Var
            i, k, n, temp : integer;
            L : array [1..100] of integer;
Begin
            {misalnya telah terdapat sekumpulan data yng tersimpan di dalam larik L}
For i ß 1 to n-1 do
For k ß n downto i+1 do
If L[k]< L[k-1] then
Temp ß L[k];
L[k] ß L[k-1];
L[k-1] ß temp;
End if
End for
End for
{lakukan pencetakan untuk data yang telah terurut pada larik L}
End.
Untuk pengurutan apung secara descending, ganti operator lebih kecil (<) menjadi lebih besar (>).
Metode pengurutan apung kurang efisien karena banyaknya proses pertukaran yang dilakukan pada setiap langkah pengapungan (pass). Untuk ukuran larik yang besar membutuhkan waktu yang lama untuk pengurutan apung. Keuntungan pengurutan ini adalah sederhana dan mudah dipahami.

9.3  Selection Sort
Metode pengurutan seleksi adalah metode yang memilih elemen maksimum atau minimum dari keseluruhan elemen larik, kemudian menempatkan elemen terpilih tersebut pada awal atau akhir larik (elemen terujung). Selanjutnya elemen terujung tersebut diisolasi dan tidak diikut sertakan pada proses pengurutan selanjutnya. Proses yang sama akan diulang sebanyak n-1 kali.
Terdapat dua macam pengurutan seleksi:
1.      Pengurutan seleksi maksimum (maximum selection)
Memilih elemen terbesar sebagai basis pengurutan
2.      Pengurutan seleksi minimum (minimum selection)
Memilih elemen terkecil sebagai basis pengurutan

Algoritma pengurutan seleksi maksimum secara ascending:
Jumlah pass = n-1
Untuk setiap pass I = 1, 2, …., jumlah pass, lakukan:
Cari elemen terbesar (maksimum) mulai dari elemen ke-1 sampai elemen ke-n.
Pertukarkan elemen terbesar (maksimum) dengan elemen ke-n
Kurangi n dengan satu (n-1), karena elemen ke-n sudah terurut
Contoh:
Terdapat larik sebagai berikut:
            29        27        10        8          76        21
Akan dilakukan pengurutan dengan metode seleksi maksimum
            Pass 1 à 29    27        10        8          21        76                   
Pass 2 à 21    27        10        8          29        76       
Pass 3 à 21    8          10        27        29        76       
Pass 4 à 10    8          21        27        29        76
            Pass 5 à 8      10        21        27        29        76







Pseudocode pengurutan seleksi maksimum secara ascending:
Algoritma seleksi_menaik;
Var
            i, j, n, imaks, temp : integer;
            L : array [1..100] of integer;
Begin
            {misalnya telah terdapat sekumpulan data yng tersimpan di dalam larik L}
For i ß n downto 2 do
            imaks ß 1;
For j ß 2 to i do
If L[j]> L[imaks] then
imaks ß j;
End if
End for
Temp ß L[i];
L[i] ß L[imaks];
L[imaks] ß temp;
End for
{lakukan pencetakan untuk data yang telah terurut pada larik L}
End.

Dibandingkan pengurutan apung, metode ini memiliki kinerja yang lebih baik karena operasi pertukaran elemen hanya dilakukan sekali saja setiap pass. Dengan demikian waktu pengurutan lebih cepat.

9.4  Metode Insertion
Metode insertion atau sisipan adalah metode dengan cara menyisipkan elemen larik pada posisi yang tepat. Pencarian posisi yang tepat dilakukan dengan menyisir larik dengan cara pergeseran elemen larik. Metode ini cocok untuk persoalan menyisipkan elemen baru ke dalam sekumpulan elemen yang telah terurut.

Algoritma pengurutan sisipan secara ascending:
Untuk setiap pass i = 2,3,…., n, lakukan
1.      y ßL[i]
2.      Sisipkan y pada tempat yang sesuai antara L[1] … L[i]
Contoh:
Terdapat larik sebagai berikut:
            29        27        10        8          76        21
Akan dilakukan pengurutan dengan metode sisipan
            Pass 1 à 29    27        10        8          76        21                   
Pass 2 à 27    29        10        8          76        21       
Pass 3 à 10    27        29        8          76        21       
Pass 4 à 8      10        27        29        76        21
            Pass 5 à 8      10        27        29        76        21
Pass 6 à 8      10        27        29        21        76














Pseudocode pengurutan sisipan secara ascending:
Algoritma sisip_menaik;
Var
            i, j, n, y : integer;
            L : array [1..100] of integer;
            Ketemu : boolean;
Begin
            {misalnya telah terdapat sekumpulan data yng tersimpan di dalam larik L}
For i ß 2 to n do
            y ß L[i];
j ß i – 1
ketemu ß false;
while (j >=1) and (not ketemu) do
If y <  L[j] then
L[j + 1] ß L[j];
J ß j – 1
                                                Else
                                                            Ketemu ß true;
End if
End while
L[j + 1] ß y;
End for
{lakukan pencetakan untuk data yang telah terurut pada larik L}
End.

Kelemahan metode ini terletak pada banyaknya operasi pergeseran yang diperlukan dalam mencari posisi yang tepat untuk elemen larik. Pada setiap pass I, operasi pergeseran yang diperlukan minimum i-1 kali. Untuk larik berukuran besar, jumlah pergeseran meningkat secara kuadratik sehingga metode ini tidak cocok untuk volume data yang besar.
9.5  Metode Shell
Metode shell dinamakan sesuai dengan nama penemunya yaitu Donald Shell pada tahun 1959. Merupakan metode perbaikan dari pengurutan sisipan. Pada metode sisipan jika data pada posisi ke-1000, ternyata membutuhkan 998 kali pergeseran elemen. Dengan metode Shell, kita akan mengurutkan larik setiap k elemen dengan metode sisipan, selanjutnya kita gunakan step yang lebih kecil, begitu seterusnya sampai k = 1.
Karena nilai step selalu berkurang, maka metode ini disebut juga sebagai metode pengurutan kenaikan yang berkurang (diminishing increment sort).
Nilai-nilai step dapat dipilih sesuka hati (misalnya 5, 3, 1). Pemilihan step yang merupakan perpangkatan dari 2 ( misalnya 8, 4, 2, 1) dapat mengakibatkan perbandingan elemen yang sama pada suatu pass akan terulang pada pass berikutnya. Sampai saat ini tidak ada yang dapat membuktikan bahwa pemilihan step tertentu paling bagus diantara pemilihan step yang lainnya.

Algortima pengurutan shell
Step ß n
while step > 1 do
step ß step div 3 + 1
for i ß 1 to step do
lakukan pengurutan sisipan setiap elemen ke-step mulai dari elemen ke-i









Pseudocode pengurutan shell
Algoritma urut_shell;
Var
            step, start,n : integer;
            L : array [1..100] of integer;
{Procedure pengurutan sisipan}
Begin
            {misalnya telah terdapat sekumpulan data yng tersimpan di dalam larik L}
                        Step ß n
                        While step > 1 do
                                    Step ß step div 3 +1
                                    For start ß 1 to step do
                                                {panggil prosedur pengurutan sisipan}
                                    End for
                        End while
            End.


0 Response to "Bab IX"