ALGORITMA PENGURUTAN

Dalam algoritma pengurutan ada beberapa cara tapi yang akan dibahas hanya empat, yaitu:

1. Metode Pengurutan apung ( Bubble Sort )

2. Metode Pengurutan seleksi ( Selection Sort )

3. Metode Pengurutan sisip ( Insertion Sort )

4. Metode Pengurutan Shell ( Shell Sort)

1. ALGORITMA PENGURUTAN APUNG

Proses pengapungan ini dilakukan sebanyak n-1 langkah ( satu langkah disebut juga satu kali pass) dengan n adalah ukuran larik.

Untuk mendapatkan larik yang terurut menaik , algoritma pengurutan apung secara global sebagai berikut :

- 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]

Procedure BubbleSort1(input/output L : LarikInt, input n: integer )

{mengurutkan larik L[1..n] sehingga terurut menaik dengan metode pengurutan apung}

k.awal : Elemen larik L sudah terdefinisi nilai – nilainya

k.akhir : Elemen larik L terurut menaik sedemikian sehingga L[1] <=L[2]<=...<=L[n]

deklarasi

i, k, temp : integer

Algoritma :

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

Endif

endfor

Algoritma pengurutan apung tidak efficient disebabkan oleh banyaknya operasi pertukaran yanga dilakukan pada setiap langkahnya, tetapi kelebihannya ada pada kesederhanaanya dan mudah untuk dipahami.

2. ALGORITMA PENGURUTAN SELEKSI

Algoritma pengurutan ini memiliki gagasan dasar , yaitu : memilih elemen maksimun / minimum dari larik, lalu menempatkan elemen tersebut itu pada awal / akhir larik ( elemen terujung). Selanjutnya elemen terujung “diisolasi “ dan tidak disertakan pada proses selanjutnya.

Algoritma pengurutan untuk maksimum ditulis secara garis besar sebagai berikut :

- Jumlah pass = n-1

- Untuk setiap pass i =1, 2, .., jumlah pass dilakukan :

# cari elemen terbesar (maks) mulai dari elemen ke – 1 sampai elemenke – n;

# Pertukarkan maks dengan elemen ke – n;

# Kurangi n satu ( karena elemen ke – n sudah terurut)

Procedure SelectionSort1(input/output L : LarikInt, input n : integer )

k.awal : elemen larik L sudah terdefinisi harganya

k.akhir : elemen larik L terurut menaik sedemikian sehingga L[1]<=L[2]<=... <= L[n]

deklarasi

i, j, imaks, maks, temp : integer

Algoritma

For i←n downto 2 do { jumlah pass sebanyak n-1}

{cari elemen maks pada L[1...i]

imaks ← 1 {elemen pertama diasumsikan sebagai maks}

maks ← L[1]

for j←2 to i do

if L[j] > maks then

imaks←j

maks←L[j]

endif

endfor

{pertukarkan maks dengan L[i]}

temp←L[i]

L[i]←maks

L[imaks]←temp

Endfor

Algoritma Pengurutan Seleksi Minimum

Procedure SelectionSort2 (input/output L : LarikInt, input n : interger)

{mengurutkan elemen-elemen larik L[1..n] sehingga tersusun menurun dengan metode pengurutan seleksi minimum}

DEKLARASI

i : interger {pencacah pass}

j : interger {pencacah untuk mencari nilai maksimum}

imin : interger {indeks yang berisi nilai minimu sementara}

ALGORITMA

for i ← n downto 2 do {jumlah pass sebanyak n – 1 kali}

{cari elemen terkecil pada elemen L[1..i]}

imin ←1

for j ← 2 to i do

if L[j] > L[imin] then

imin ← L[j]

endif

endfor

{pertukaran L[imin] dengan L[i]}

Tukar (L[imin], L[i]);

Endfor

3. Insertion Sort / Metode Pengurutan Sisip

Salah satu algoritma sorting yang paling sederhana adalah insertion sort.Ide dari algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan berikut ini menerangkan bagaimana algoritma insertion sort bekerja dalam pengurutan kartu. Anggaplah ingin mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar. Seluruh kartu diletakkan pada meja, sebutlah meja ini sebagai meja pertama, disusun dari kiri ke kanan dan atas kebawah. Kemudian kita mempunyai meja yang lain, meja kedua, dimana kartu yang diurutkan akan diletakkan. Ambil kartu pertama yang terletak pada pojok kiri atas meja pertama dan letakkan pada meja kedua.Ambil kartu kedua darimejapertama, bandingkan dengan kartu yang berada pada meja kedua, kemudian letakkan pada urutan yang sesuai setelah perbandingan. Proses tersebut akan berlangsung hingga seluruh kartu pada meja pertama telah diletakkan berurutan pada meja kedua.

Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah diurutkan.Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.

Kelemahan metode ini adalah jika ada data pada posisi ke-1000, maka dibutuhkan pergeseran elemen sebanyak 998 kali.

Contoh penulisan dalam algoritma:

procedure UrutSisip(input/output L: Larik, input N : integer)

DEKLARASI

K : integer {pencacah langkah}

J : integer {pencacah untuk penelusuran larik}

Temp : integer {peubah bantu untuk agar L[K] tidak ditimpa selama pergeseran}

ALGORITMA

{elemen L[1] dianggap sudah terurut}

for K ← 2 to N do {mulai dari langkah 2 sampai langkah N}

Temp ← L[K] {ambil elemen L[K] supaya tidak ditimpa pergeseran}

{cari posisi yang tepat untuk L[K] di dalam L[1..K-1] sambil menggeser}

J ← K – 1

while Temp ≤ L[J] AND (J > 1) do

L[J+1] ← L[J]

J ← J-1

Endwhile

if Temp ≥ L[J] then

L[J+1] ← Temp

Else

L[J+1] ← L[J]

L[J] ← Temp

endif

endfor

4. Shell Sort

Algoritma pengurutan shell ini ditemukan oleh Donald Shell pada tahun1959. Algoritma ini merupakan perbaikan terhadap pengurutan sisip.Jika pada metode pengurutan sisip, jika ada data pada posisi ke-1000, maka dibutuhkan pergeseran elemen sebanyak 998 kali.

Untuk mengurangi pergeseran terlalu jauh, harus mengurutkan larik setiap k elemen dengan metode pengurutan shell, misalkan kita urutkan setiap 5 elemen (k kita namakan juga step atau increment). Selanjutnya, kita gunakan nilai step yang lebih kecil, misalnya k = 3, lalu kita urut setiap 3 elemen. Begitu seterusnya sampai nilai k = 1. Karena nilai step selalu berkurang maka algoritma pengurutan Shell kadang – kadang dinamakan juga algoritma pengurutan kenaikan yang berkurang (diminishing increment sort).

Contoh :

Procedure InSort(input/output L : LarikInt, input n,start,step : interger)

{mengurutkan elemen larik L[start..n] sehingga tersusun menaik dengan metode pengurutan sisip yang dimodifikasi untuk shell sort}

DEKLARASI

i : interger {pencacah step}

j : interger {pencacah untuk penelusuran larik}

y : interger {peubah bantu yang menyimpan nilai L[k]}

ketemu : Boolean {untuk menyatakan posisi penyisipan ditemukan}

ALGORITMA

{elemen L[start] dianggap sudah terurut}

i← start + step

while i ≤ n do