Pengurutan (Sorting) • Pengurutan adalah proses mengatur sekumpulan obyek menurut urutan atau susunan tertentu. • Urutan obyek tersebut dapat menaik atau menurun. • Bila N obyek disimpan dalam larik L, maka pengurutan menaik berarti menyusun elemen larik sedemikian sehingga: • L[1] ≤ L[2] ≤ L[3] ≤ …≤ L[N] Kamis, 25 Mei 2006
Algoritma dan Pemrograman II
1
Kamis, 25 Mei 2006
Algoritma dan Pemrograman II
2
• Pengurutan Internal adalah pengurutan terhadap sekumpulan data yang disimpan di dalam memori utama komputer. Umumnya struktur data yang dipakai adalah larik, sehingga pengurutan internal disebut juga pengurutan larik. • Pengurutan Eksternal adalah pengurutan data yang disimpan di dalam memori sekunder, biasanya data bervolume besar sehingga tidak mampu dimuat semuanya dalam memori komputer, disebut juga pengurutan arsip (file), karena struktur eksternal yang dipakai adalah arsip.
• Mempercepat pencarian; • Mudah menentukan data maksimum / minimum.
Algoritma dan Pemrograman II
(i) 23, 27, 45, 67 (data integer terurut menaik) (ii) 25.12, 20.19,-12.20 (data riil terurut menurun) (iii) Amir, Badu, Budi, Dudi (data string terurut manaik) (iv) <08053110001, Eko, A>, < 08053110011, Reza, C>, <08053110012, Sam, E> (data mahasiswa terurut menaik berdasarkan field NIM)
Pengurutan Terbagi Dua Kelompok:
Keuntungan Data Terurut
Kamis, 25 Mei 2006
• Sedangkan pengurutan menurun berarti menyusun elemen larik sedemikian sehingga: • L[1] ≥ L[2] ≥ L[3] ≥ … ≥ L[N] • Data yang diurut dapat berupa data bertipe numerik dasar atau tipe bentuk. Jika data bertipe bentukan (rekaman), maka harus dijelaskan berdasarkan field apa data tersebut diurutkan. • Contoh:
3
Kamis, 25 Mei 2006
Algoritma dan Pemrograman II
4
1
Bubble Sort (Pengurutan Gelembung)
Macam-macam Pengurutan • • • • • • • • •
• Metode pengurutan gelembung diinspirasikan oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan. • Prinsip di atas dipakai pada pengurutan gelembung. Elemen larik yang berharga paling kecil “diapungkan”, artinya diangkat ke atas (ke ujung kiri larik) melalui proses pertukaran. Proses pengapungan terdiri dari N1 langkah. Setiap akhir langkah ke-I, larik L[1..N] akan terdiri atas dua bagian, yaitu bagian yang sudah terurut, L[1..I] dan bagian yang belum terurut, L[I+1..N]. Langkah terakhir, diperoleh larik L[1..N] yang sudah terurut.
Bubble Sort; Maximum/Minimum Sort (Selection Sort); Insertion Sort; Heap Sort; Shell Sort; Quick Sort; Merge Sort; Radix Sort; Tree Sort, dan lain-lain.
Kamis, 25 Mei 2006
Algoritma dan Pemrograman II
5
Algoritma Pengurutan Gelembung
Kamis, 25 Mei 2006
Algoritma dan Pemrograman II
procedure UrutGelembung(input/output L: Larik; input N : integer)
•
Untuk mendapatkan larik yang terurut menaik, proses yang dilakukan pada setiap langkah sebagai berikut: Langkah 1: Mulai 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.
Kamus I : integer {pencacah untuk jumlah langkah} K : integer {pencacah untuk pengapungan pada setiap langkah} Temp : integer {peubah bantu untuk pertukaran}
Langkah 2: Mulai 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 kedua dan larik L[1..2] terurut. … Langkah N-1: Mulai elemen K =N, bandingkan L[K] dengan L[K-1]. Jika L[K] < L[K-1], pertukarkan L[K] dengan L[K-1].
Algoritma for I ← 1 to N-1 do for K ← N downto 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
Pada akhir langkah N-1, elemen L[N-1] berisi harga minimum ke-(N-1) dan larik L[1..N-1] terurut menaik, sehingga elemen yang tersisa adalah L[N] yang tidak perlu lagi diurutkan karena hanya satusatunya. Kamis, 25 Mei 2006
Algoritma dan Pemrograman II
6
7
Kamis, 25 Mei 2006
Algoritma dan Pemrograman II
8
2
procedure UrutGelembung1(input/output L: Larik; input N : integer)
Pengurutan Gravitasi
Kamus I : integer {pencacah untuk jumlah langkah} K : integer {pencacah untuk pengapungan pada setiap langkah} Temp : integer {peubah bantu untuk pertukaran} Tukar : boolean {flag untuk mengidentifikasi adanya pertukaran, bernilai true jika dalam satu langkah ada pertukaran}
Pengurutan gravitasi sebagai kebalikan dari pengurutan gelembung, yaitu “membenamkan” elemen larik yang berharga paling besar ke bawah, jadi proses “pemberatan” selalui dimulai dari “atas” ke “bawah”.
Algoritma I← 1 Tukar ← true while I ≤ N-1 AND Tukar do Tukar ← false for K ← N downto 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 Tukar ← true endif endfor I← I+1 endwhile { I = N or not Tukar }
Kamis, 25 Mei 2006
Algoritma dan Pemrograman II
9
Kamus I : integer {pencacah untuk jumlah langkah} K : integer {pencacah untuk pemberatan pada setiap langkah} U : integer {indeks ujung kiri bagian larik yang telah terurut} Temp : integer {peubah bantu untuk pertukaran}
10
Gagasan maksimum/minimum adalah memilih elemen maksimum/minimum kemudian mempertukarkan elemen maksimum/minimum tersebut dengan elemen terujung larik (elemen ujung kiri atau elemen ujung kanan). Selanjutnya elemen terujung tersebut “diisolasi” dan tidak disertakan pada proses selanjutnya. Proses yang sama diulang untuk elemen larik yang tersisa, yaitu memilih elemen maksimum/minimum berikutnya dan mempertukarkannya dengan elemen terujung larik sisa.
Algoritma U←N for I ← 1 to N-1 do for K ← 1 to U-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 { larik L[U..N] terurut, larik L[1..U-1] belum terurut } U←U-1 endfor Algoritma dan Pemrograman II
Algoritma dan Pemrograman II
Pengurutan Maksimum/Minimum
procedure UrutGravitasi(input/output L: Larik; input N : integer)
Kamis, 25 Mei 2006
Kamis, 25 Mei 2006
11
Kamis, 25 Mei 2006
Algoritma dan Pemrograman II
12
3
procedure UrutMaksimum(input/output L: Larik, input N : integer)
Algoritma Pengurutan Maksimum Elemen larik akan diurut menaik: Langkah 1: Tentukan harga maksimum di dalam L[1..N]. Pertukarkan harga maksimum dengan elemen L[N]. Langkah 2: Tentukan harga maksimum di dalam L[1..N-1]. Pertukarkan harga maksimum dengan elemen L[N-1]. … Langkah N-1: Tentukan harga maksimum di dalam L[1..2]. Pertukarkan harga maksimum dengan elemen L[2]. Kamis, 25 Mei 2006
Algoritma dan Pemrograman II
13
Algoritma Pengurutan Maksimum dengan Elemen Larik Diurut Menurun
Algoritma dan Pemrograman II
Algoritma U←N for I ← 1 to N-1 do Maks ← L[1] Imaks ← 1 for J ← 2 to U do if L[J] > L[Imaks] then Maks ← L[J] Imaks ← J endif endfor {pertukarkan Maks dengan L[U]} Temp ← L[U] L[U] ← L[Imaks] L[Imaks] ← Temp { larik L[U..N] terurut, larik L[1..U-1] belum terurut } U←U-1 endfor
Kamis, 25 Mei 2006
Algoritma dan Pemrograman II
14
procedure UrutMaks_Menurun(input/output L: Larik, input N : integer) Kamus Lokal I : integer{pencacah untuk jumlah langkah} J : integer {pencacah untuk mencari nilai maksimum} Imaks : integer {indeks yang berisi nilai maksimum sementara} Temp : integer {peubah bantu untuk pertukaran} Algoritma
Langkah 1: Tentukan harga maksimum di dalam L[1..N]. Pertukarkan harga maksimum dengan elemen L[1]. Langkah 2: Tentukan harga maksimum di dalam L[2..N]. Pertukarkan harga maksimum dengan elemen L[2]. … Langkah N-1: Tentukan harga maksimum di dalam L[N-1,N]. Pertukarkan harga maksimum dengan elemen L[N-1]. Kamis, 25 Mei 2006
Kamus Lokal I : integer {pencacah untuk jumlah langkah} J : integer {pencacah untuk mencari nilai maksimum} U : integer {indeks ujung kiri bagian larik yang telah terurut} Maks : integer {nilai maksimum sementara} Imaks : integer {indeks yang berisi nilai maksimum sementara} Temp : integer {peubah bantu untuk pertukaran}
for I ← 1 to N-1 do Imaks ← I for J ← I+1 to N do if L[J] > L[Imaks] then Imaks ← J endif endfor {pertukarkan Maks dengan L[U]} Temp ← L[I] L[I] ← L[Imaks] L[Imaks] ← Temp endfor 15
Kamis, 25 Mei 2006
Algoritma dan Pemrograman II
16
4
Algoritma Pengurutan Minimum
procedure UrutMin(input/output L: Larik, input N : integer) Kamus Lokal I : integer {pencacah untuk jumlah langkah} J : integer {pencacah untuk mencari nilai minimum} U : integer {indeks ujung kiri bagian larik yang telah terurut} Imin : integer {indeks yang berisi nilai minimum sementara} Temp : integer {peubah bantu untuk pertukaran}
Elemen larik akan diurut minimum menaik: Langkah 1: Tentukan harga minimum di dalam L[1..N]. Pertukarkan harga minimum dengan elemen L[N]. Langkah 2: Tentukan harga minimum di dalam L[1..N1]. Pertukarkan harga minimum dengan elemen L[N1]. … Langkah N-1: Tentukan harga minimum di dalam L[1..2]. Pertukarkan harga minimum dengan elemen L[2]. Kamis, 25 Mei 2006
Algoritma dan Pemrograman II
Algoritma U←N for I ← 1 to N-1 do Imin ← 1 for J ← 2 to U do if L[J] < L[Imin] then Imin ← J endif endfor {pertukarkan Maks dengan L[U]} Temp ← L[U] L[U] ← L[Imin] L[Imin] ← Temp { larik L[U..N] terurut, larik L[1..U-1] belum terurut } U←U-1 endfor 17
Algoritma Pengurutan Minimum dengan Elemen Larik Diurut Menurun
Algoritma dan Pemrograman II
Algoritma dan Pemrograman II
18
procedure UrutMin_Menurun(input/output L: Larik, input N : integer) Kamus Lokal I : integer {pencacah untuk jumlah langkah} J : integer {pencacah untuk mencari nilai minimum} Imin : integer {indeks yang berisi nilai minimum sementara} Temp : integer {peubah bantu untuk pertukaran}
Langkah 1: Tentukan harga minimum di dalam L[1..N]. Pertukarkan harga minimum dengan elemen L[1]. Langkah 2: Tentukan harga minimum di dalam L[2..N]. Pertukarkan harga minimum dengan elemen L[2]. … Langkah N-1: Tentukan harga minimum di dalam L[N-1,N]. Pertukarkan harga minimum dengan elemen L[N-1]. Kamis, 25 Mei 2006
Kamis, 25 Mei 2006
Algoritma
for I ← 1 to N-1 do Imin ← I for J ← I+1 to N do if L[J] < L[Imin] then Imin ← J endif endfor {pertukarkan Maks dengan L[U]} Temp ← L[I] L[I] ← L[Imin] L[Imin] ← Temp endfor
19
Kamis, 25 Mei 2006
Algoritma dan Pemrograman II
20
5
Pengurutan Sisip (Insertion Sort)
Pengurutan Sisip yang Menaik
Pengurutan sisip adalah metode pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat. Pencarian posisi yang tepat dilakukan dengan melakukan pencarian beruntun di dalam larik. Selama pencarian posisi yang tepat dilakukan pergeseran elemen larik.
Andaikan: L[1] dianggap sudah pada tempatnya Langkah 2: L[2] harus dicari tempatnya yang tepat pada L[1..2] dengan cara menggeser elemen L[1..1] ke kanan (atau ke bawah, jika anda membayangkan larik terentang vertikal) bila L[1..1] lebih besar daripada L[2]. Misalkan posisi yang tepat adalah K. Sisipkan L[2] pada L[K]. Langkah 3: L[3] harus dicari tempatnya yang tepat pada L[1..3] dengan cara menggeser elemen L[1..2] ke kanan (atau ke bawah) bila L[1..2] lebih besar daripada L[3]. Misalkan posisi yang tepat adalah K. Sisipkan L[3] pada L[K]. … Langkah N: L[N] harus dicari tempatnya yang tepat pada L[1..N] dengan cara menggeser elemen L[1..N-1] ke kanan (atau ke bawah) bila L[1..N-1] lebih besar daripada L[N]. Misalkan posisi yang tepat adalah K. Sisipkan L[N] pada L[K]. Hasil dari langkah N: Larik L[1..N] sudah terurut, yaitu L[1] ≤ … ≤ L[N]
Kamis, 25 Mei 2006
Algoritma dan Pemrograman II
21
procedure UrutSisip(input/output L: Larik, input N : integer)
Kamis, 25 Mei 2006
Algoritma dan Pemrograman II
procedure UrutSisip_Turun(input/output L: Larik, input N : integer)
Kamus Lokal K : integer {pencacah langkah} J : integer {pencacah untuk penelusuran larik} Temp : integer {peubah bantu untuk agar L[K] tidak ditimpa selama pergeseran}
Kamus Lokal 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
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 {Temp > L[J] or J = 1} if Temp ≤ L[J] then L[J+1] ← Temp else L[J+1] ← L[J] L[J+1] ← Temp endif endfor
Kamis, 25 Mei 2006
Algoritma dan Pemrograman II
22
23
Kamis, 25 Mei 2006
Algoritma dan Pemrograman II
24
6
