studi perbandingan tahapan analisis dan …si.ilkom.unsri.ac.id/wp-content/uploads/2018/11/6.pdf ·...

Halaman 1

Sorting (Pengurutan)

A. Definisi Pengurutan

Pengurutan adalah proses mengatur

sekumpulan objek menurut urutan atau

susunan tertentu.

Urutan Objek tersebut dapat menaik

(Ascending) atau menurun (Descending).

Halaman 2

Data yang telah diurutkan memiliki banyak

Keuntungan antara lain :

1. Mempercepat proses pencarian

2. Dapat dengan mudah ditentukan

maksimum dan minimumnya

Adanya kebutuhan terhadap proses

pengurutan memunculkan bermacam-

macam metode pengurutan yang

bertujuan untuk mendapatkan metode

pengurutan yang optimal.

Halaman 3

Algoritma pengurutan yang dikenal secara

luas antara lain :

1. Maximum/Minimum Sort

2. Insertion Sort (Pengurutan Sisip)

3. Bubble Sort (Pengurutan Gelembung)

4. Heap Sort

5. Shell Sort

6. Quick Sort

7. Merge Sort

8. Radix Sort

9. Tree Sort

Halaman 4

Pada Kuliah ini hanya akan dibahas tiga metode

pengurutan saja, yaitu :

1. Pengurutan Gelembung (Bubble Sort)

2. Pengurutan Maksimum/Minimum

(Maximum/Minimum Sort)

3. Pengurutan Sisip (Insertion Sort)

Untuk semua algoritma pengurutan yang akan dibicarakan kemudian menggunakan tipe Array (Larik), yang didefinisikan sebagai berikut :

{Deklarasi}

Const NMaks = 100 {Jumlah Maksimum elemen Array}

Type LarikInt = array[1...NMaks] of integer

Halaman 5

B. Pengurutan Gelembung (Bubble Sort)

Pengurutan gelembung diinspirasi oleh gelembung sabun yang berada di atas permukaan air. Karena berat jenis sabun lebih ringan daripada berat jenis air, maka gelembung sabun akan selalu terapung di atas pemukaan.

Prinsip pengapungan digunakan pada pengurutan gelembung. Elemen Array yang berharga paling kecil “diapungkan”, artinya diangkat ke atas (atau ke ujung kiri Array) melalui proses pertukaran, jika akan dilakukan pengurutan membesar, jika pengurutan mengecil sebaliknya.

Halaman 6

Proses pengapungan ini dilakukan

sebanyak N kali langkah. Pada akhir

setiap langkah ke- I, Array L[1..N]

akan terdiri dari dua bagian, yaitu

bagian yang sudah terurut, yaitu L[1..i]

dan bagian yang belum terurut, yaitu

L[i+1..N]. Setelah langkah terakhir,

diperoleh Array L[1..N] yang terurut

menaik

Halaman 7

Algoritma Pengurutan Gelembung

Untuk mendapatkan array yang terurut

menaik, Proses yang dilakukan pada setiap langkah adalah sebagai berikut :

Langkah 1 : Mulai dari elemen k = N, N-1, …2,

bandingkan L[k] dengan L[k-1]. Jika L[k] <

L[k-1], pertukarkan L[k] dengan L[k-1]. Pada

akhir langkah 1, elemen L[1] berisi harga

minimum pertama.

Halaman 8

Langkah 2 : Mulai dari elemen k = N, N-1, …,3, bandingkan L[k] dengan L[k-1]. Jika L[k] < L[k-1], pertukarkan L[k] dengan L[k-1].

Pada akhir langkah 2, elemen L[2] berisi harga minimum ke dua dan larik L[1..2] terurut

Langkah 3 : Mulai dari elemen k = N, N-1,…, 4, bandingkan L[k] dengan L[k-1]. Jika L[k] < L[k-1], pertukarkan L[k] dengan L[k-1].

Pada akhir langkah 3, elemen L[3] berisi harga minimum ke dua dan larik L[1..3] terurut

.

.

.

Halaman 9

Langkah N-1 : Mulai dari elemen k = N, bandingkan L[k]

dengan L[k-1]. Jika L[k] < L[k-1],

pertukarkan L[k] dengan L[k-1].

Pada akhir langkah N-1, elemen L[N-1]

berisi harga minimum ke N-1 dan larik

L[1..N-1] terurut menaik (elemen yang

tersisa adalah L[N], tidak perlu diurut

karena hanya satu-satunya)

Contoh :

Diketahui sebuah Array dengan N = 6 buah elemen yang

belum Terurut, Array ini akan diurutkan menaik. Elemen

Array tersebut Adalah 25, 27, 10, 8, 76, 21

Halaman 10

Algoritmanya adalah sebagai berikut :

Procedure BubleSort(Input/output L : LarikInt, Input N : Integer)

{ K. Awal : Elemen Array L Telah terdefinisi

K. Akhir : Elemen Larik L terurut menaik sedemikian hingga L[1] ≤ L[2] ≤ … ≤ L[N]

Proses : Mengurutkan elemen array L sehingga terurut menaik dengan metode Urut Gelembung}

{Deklarasi} i : integer {Pencacah untuk jumlah langkah}

k : integer {Pencacah untuk pengapungan pd tiap langkah}

Temp : integer {Peubah bantu untuk pertukaran}

Halaman 11

{Deskripsi}

For i ← 1 to N-1 do

for k ← N to i+1 do

if L[k] < L[k-1] then

{Pertukarkan L[k] dengan L[k-1] }

Temp ← L[k]

L[k] ← L[k-1]

L[k-1] ← Temp

endif

endfor

endfor

Halaman 12

Untuk memperoleh sebuah array yang

terurut menurun dilakukan langkah

sebaliknya.

Jika diperhatikan pengurutan dengan

metode Buble Sort adalah pengurutan

yang tidak efisien untuk Array yang

mempunyai ukuran yang besar, karena

banyaknya operasi pertukaran yang

dilakukan pada setiap langkah. Tetapi

metode ini sederhana dan mudah

dipahami.

Halaman 13

C. Pengurutan Maksimum/Minimum

Metode pengurutan ini disebut pengurutan Maksimum/minimum karena didasarkan pada pemilihan elemen maksimum/minimum sebagai basis pengurutan.

Gagasannya adalah memilih elemen maksimum/minimum kemudian pertukarkan elemen tersebut dengan elemen terujung Array (Elemen ujung kiri atau ujung kanan). Selanjutnya dengan cara yang sama diulang untuk elemen larik yang tersisa dengan tidak lagi menyertakan elemen Array yang telah terurut.

Halaman 14

1. Algoritma Pengurutan Maksimum

Misalkan elemen Array akan diurut menaik :

Langkah 1 : Tentukan harga maksimum di dalam L[1..N] Pertukarkan harga maksimum dengan L[N]

Langkah 2 : Tentukan harga maksimum di dalam L[1..N-1] Pertukarkan harga maksimum dengan L[N-1]

Langkah 3 : Tentukan harga maksimum di dalam L[1..N-2] Pertukarkan harga maksimum dengan L[N-2]

.

.

Langkah N-1 : Tentukan harga maksimum di dalam L[1..2] Pertukarkan harga maksimum dengan L[2]

Halaman 15

Elemen tersisa adalah L[1] tidak perlu diurutkan

karena merupakan elemen terakhir.

Jadi pada setiap langkah pengurutan terdapat

proses mencari harga maksimum dam proses

pertukaran dua buah elemen array. Jumlah

langkah pengurutan adalah N-1.

Contoh

Diketahui sebuah Array dengan N = 6 buah

elemen yang belum Terurut, Array ini akan

diurutkan menaik. Elemen Array tersebut Adalah

25, 27, 10, 8, 76, 21

Halaman 16

Algortimanya adalah sebagai berikut :

Procedure Urutmaksimum(Input/output L : LarikInt, Input N : Integer)



Proses : Mengurutkan elemen array L sehingga terurut menaik dengan metode Urut Maksimum}

{Deklarasi}

i : integer {Pencacah untuk jumlah langkah}

j : integer {Pencacah untuk mencari nilai maksimum}


u : integer {Indeks ujung kanan array yang telah terurut}

imaks : integer {Indeks elemen array maksimum sementara}

maks : integer {Elemen array maksimum sementara}

Halaman 17

{Deskripsi}

u ← N


Maks ← L[1]

iMaks ← 1

for j ← 2 to u do

if L[j] > Maks then

Maks ← L[j]

iMaks ← j

endif

endfor

{Pertukarkan L[u] dengan L[iMaks] }

Temp ← L[u]

L[u] ← L[iMaks]

L[imaks] ← Temp

endfor

Halaman 18

Untuk terurut menurun adalah kebalikannya, yaitu mempertukarkan elemen yang maksimum dengan elemen array sebelah kiri yang belum terurut.

2. Algoritma Pengurutan Minimum

Misalkan elemen Array akan diurut menurun :

Langkah 1 : Tentukan harga minumum di dalam L[1..N]

Pertukarkan harga minumum dengan L[N]

Langkah 2 : Tentukan harga minumum di dalam L[1..N-1]

Pertukarkan harga minumum dengan L[N-1]

Langkah 3 : Tentukan harga minumum di dalam L[1..N-2]

Pertukarkan harga minumum dengan L[N-2]

Halaman 19

.

.

.

Langkah N-1 : Tentukan harga minumum di dalam L[1..2]

Pertukarkan harga minumum dengan L[2]

Elemen yang tersisa adalah L[1], tidak perlu diurut karena

hanya satu-satunya

Untuk pengurutan menaik adalah kebalikannya, yaitu

mempertukarkan elemen yang minimum dengan elemen

yang sebelah kiri pada array yang belum terurut

Halaman 20

Algortimanya adalah sebagai berikut :

Procedure UrutMinimum(Input/output L : LarikInt, Input N : Integer)

{K. Awal : Elemen Array L Telah terdefinisi

K. Akhir : Elemen Larik L terurut menurun sedemikian hingga L[1] ≥ L[2] ≥ … ≥ L[N]

Proses : Mengurutkan elemen array L sehingga terurut menurun dengan metode Urut Minimum}

{Deklarasi}

i : integer {Pencacah untuk jumlah langkah}

j : integer {Pencacah untuk mencari nilai minimum}


u : integer {Indeks ujung kanan array yang telah terurut}

iMin : integer {Indeks elemen array minimum sementara}

Min : integer {Elemen array minimum sementara}

Halaman 21

{Deskripsi}

u ← N


Min ← L[1]

iMin ← 1

for j ← 2 to u do

if L[j] > Min then

Min ← L[j]

iMin ← j

endif

endfor

{Pertukarkan L[u] dengan L[iMin] }

Temp ← L[u]

L[u] ← L[iMin]

L[iMin] ← Temp

endfor

Halaman 22

D. Pengurutan Sisip (Insertion Sort)

Pengurutan sisip adalah metode pengurutan dengan

cara menyisipkan elemen array pada posisi yang

tepat.

Pencarian posisi pada yang tepat dimulai pada

elemen kedua, dengan pemisalan bahwa elemen

pertama sudah pada tempatnya. Selama

pencarian posisi yang tepat dilakukan pergeseran

elemen array.

Halaman 23

Algoritma Pengurutan Sisip Menaik

Andaian : L[1] sudah pada tempatnya

Langkah 2 : L[2] harus dicari tempatnya pada L[1..2]

dengan cara menggeser elemen L[1..1]

ke kanan bila L[1..1] lebih besar dari L[2].

Misalkan posisi yang tepat adalah k,

maka sisipkan L[2] pada L[k]


dengan cara menggeser elemen L[1..2]

ke kanan bila L[1..2] lebih besar dari

L[3]. Misalkan posisi yang tepat adalah k,

maka sisipkan L[3] pada L[k]

Halaman 24


dengan cara menggeser elemen L[1..3] ke

kanan bila L[1..3] lebih besar dari L[4].

Misalkan posisi yang tepat adalah k, maka

sisipkan L[4] pada L[k]

.

.

.

Langkah N : L[N] harus dicari tempatnya pada L[1..N]

dengan cara menggeser elemen L[1..N-1] ke

kanan bila L[1..N-1] lebih besar dari L[N].

Misalkan posisi yang tepat adalah k, maka

sisipkan L[N] pada L[k]

Halaman 25

Contoh

Diketahui sebuah Array dengan N = 6 buah

elemen yang belum Terurut, Array ini akan

diurutkan menaik. Elemen Array tersebut Adalah

25, 27, 10, 8, 76, 21

Kelemahan metode pengurutan sisip adalah

pada banyaknya operasi pergeseran yang

diperlukan dalam mencari posisi yang

tepat pada elemen array.

Halaman 26

Algortimanya adalah sebagai berikut : Procedure UrutSisip(Input/output L : LarikInt, Input N : Integer)



Proses : Mengurutkan elemen array L sehingga terurut menaik dengan metode Urut Sisip}

{Deklarasi}

k : integer {Pencacah untuk jumlah langkah}

j : integer {Pencacah untuk penelusuran array}

Temp : integer {Peubah bantu agar L[k] tidak ditimpa selama pergeseran}

Halaman 27

{Deskripsi}

{Elemen L[1] dianggap telah terurut}

For k ← 2 to N do

Temp ← L[k] {ambil L[k] agar tidak ditimpa pergeseran}

{Cari posisi yang tepat untuk L[k] di dalam L[1..k-1]

sambil menggeser}

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 {Posisi yang tepat untuk L[k] ditemukan}

else

L[j+1] ← L[j]

L[j] ← Temp

endif

endfor

studi perbandingan tahapan analisis dan …si.ilkom.unsri.ac.id/wp-content/uploads/2018/11/6.pdf ·...

Documents