Pengurutan pada Array Tim PHKI Modul Dasar Pemrograman Fakultas Ilmu Komputer UDINUS Semarang
Pengurutan (Sorting) • Sorting atau pengurutan data adalah proses yang sering harus dilakukan dalam pengolahan data • Ada 2 macam teknik pengurutan:
– pengurutan internal, terhadap data yang tersimpan di memori – pengurutan eksternal, terhadap data yang tersimpan di secondary storage
• Algoritma pengurutan internal yang utama antara lain: Counting Sort, Maximum Sort, Insertion Sort, Bubble sort • Performansi pengurutan data sangat menentukan performansi sistem, karena itu pemilihan metoda pengurutan yang cocok akan berperan dalam suatu aplikasi
Pengurutan (Sorting) Definisi dan Kamus Umum
• Definisi Persoalan:
Diberikan sebuah Tabel integer T [1..N] yang isinya sudah terdefinisi. Tuliskan sebuah algoritma yang mengurutkan elemen tabel sehingga terurut membesar : T1 T2 ≤ T3 ..... ≤ TN
• Kamus Umum:
Counting Sort (Pengurutan dengan Pencacah) • Pengurutan dengan pencacahan adalah pengurutan yang paling sederhana • Jika diketahui bahwa data yang akan diurut mempunyai daerah jelajah (range) tertentu, dan merupakan bilangan bulat, misalnya [Min..Max] maka cara paling sederhana untuk mengurut adalah : – Sediakan array TabCount [Min..Max] yang elemennya diinisialisasi dengan nol, dan pada akhir proses TabCounti berisi banyaknya data pada tabel asal yang bernilai i – Tabel dibentuk kembali dengan menuliskan kembali hargaharga yang ada berdasarkan isi dari TabCount
Counting Sort Ilustrasi
1. Elemen Tabel TabCount diinisialisasi 0 2. Telusuri TabInt, sambil mengupdate elemen TabCount TabCount berisi jumlah kemunculan elemen pada TabInt 3. Telusuri TabCount, untuk mengisi TabInt sesuai isi TabCount TabInt terurut
TabInt 1
1
2
3
3
6
4
3
5
5
6
4
7
1
8
3
9
5
10
6
TabCount
TabInt’
1
2 0 1
1
1
2
2
1
3
0 13 0 2
3
4
0 1
4
3 3
5
20 1
5
3
6
1 0 2
6
4
7
5
8
5
9
6
10
6
1.
Counting Sort Ilustrasi Elemen Tabel
3. Telusuri TabCount, untuk mengisi TabInt sesuai isi TabCount TabInt terurut
TabCount diinisialisasi 0
TabInt 1
0
2
0
3
0
4
0
5
0
6
0
2. Telusuri TabInt, sambil mengupdate elemen TabCount TabCount berisi jumlah kemunculan elemen pada TabInt
1
1
2
3
3
6
4
3
5
5
6
4
7
1
8
3
9
5
10
6
TabCount
TabInt’
1
2 0 1
1
1
2
2
1
3
0 13 0 2
3
4
0 1
4
3 3
5
20 1
5
3
6
1 0 2
6
4
7
5
8
5
9
6
10
6
Counting Sort Algoritma
Kamus : T : array [0..NMax] of integer {ValMin & ValMax: batas Minimum dan Maximum nilai dalam T, harus diketahui} TabCount : array [ValMin..ValMax] of integer [0..NMax] i, j : integer { indeks untuk traversal tabel } K : integer { jumlah elemen T yang sudah diisi pada pembentukan kembali } N : integer {Jumlah elemen T} ALGORITMA Inisialisasi TabCount } Elemen Tabel TabCount diinisialisasi 0 i traversal [ValMin..ValMax] TabCounti 0 Telusuri TabInt, sambil { Counting } mengupdate elemen i traversal [1..N] TabCount TabCount berisi TabCountTi TabCountTi + 1 jumlah kemunculan elemen { Pengisian kembali : T1 ≤T2 ... ≤ TN } pada TabInt K0 Telusuri TabInt, sambil i traversal [ValMin..ValMax] mengupdate elemen if (TabCounti ≠ 0) then TabCount TabCount berisi j traversal [1..TabCounti] jumlah kemunculan elemen KK+1 pada TabInt TK i
Selection Sort (Pengurutan berdasarkan Seleksi) Contoh : maksimum suksesif (pengurutan dari besar ke kecil)
• Idenya adalah:
– Cari indeks penampung nilai maksimum ‘tabel’ – Tukar elemen pada indeks maksimum dengan elemen ter’ujung’ • elemen terujung "diisolasi“, tidak disertakan pada proses berikutnya • proses diulang untuk sisa tabel
• Hasil proses: tabel terurut mengecil T1 ≥ T2 ≥ T3 ...... ≥TN • Proses dilakukan sebanyak N-1 tahapan (disebut "pass")
Selection Sort Ilustrasi • Proses diulang untuk elemen 1..NMax-1 • Pada iterasi ke-i: – Elemen 1..i-1 sudah terurut – Cari indeks dgn nilai maksimum elemen i..NMax – Tukar elemen ke-i dengan elemen pada indeks dengan nilai maksimum
1
12 60
2
35
3
10 30
4
60 12 25
5
30 10 12
12 25 6 10
Elemen maksimum 2..6, tukar dengan elemen 2 Elemen maksimum 1..6, tukar dengan elemen 3 Elemen maksimum 3..6, tukar dengan elemen 3 Elemen maksimum 5..6, 4..6, tukar dengan elemen 5 4
Selection Sort Ilustrasi
• Proses diulang untuk elemen 1..NMax-1 • Pada iterasi ke-i:
– Elemen 1..i-1 sudah terurut – Cari indeks dgn nilai maksimum elemen i..NMax – Tukar elemen ke-i dengan elemen pada indeks dengan nilai maksimum
1
12
60
60
60
60
60
2
35
35
35
35
35
35
3
10
10
10
30
30
30
4
60
12
12
12
25
25
5
30
30
30
10
10
12
6
25
25
25
25
12
10
Elemen maksimum pada iterasi Elemen yang akan menampung posisi elemen maksimum
Selection Sort Algoritma Kamus Lokal : T : array [0..NMax] of integer N : integer {Jumlah elemen T} i : integer { indeks untuk traversal tabel } Pass : integer { tahapan pengurutan } Temp : integer { memorisasi harga untuk penukaran } IMax : integer { indeks, dimana T [Pass..N] bernilai maksimum } ALGORITMA Pass traversal [1..N-1] Cari indeks dgn nilai maksimum (di bagian { Tentukan Maximum [Pass..N] } tabel yang belum terurut) IMax Pass Tukarkan elemen pada indeks i traversal [Pass+1..N] maksimum dengan elemen if (TIMax < Ti ) then terujung dari bagian tabel yang IMax i belum terurut { TIMax adalah maximum T[Pass..N] } {Tukar TIMax dengan TPass } Temp TIMax TIMax TPass TPass Temp { T[1..Pass] terurut: T1 ≥ T2 ≥ T3 .. ≥TPass} {Seluruh tabel terurut, T1 T2 T3 ...... TN }
Insertion Sort (Pengurutan dengan Penyisipan) • Idenya adalah:
– mencari tempat yang "tepat" untuk setiap elemen tabel dengan cara menyisipkan elemen tersebut pada tempatnya di bagian tabel yang sudah terurut – Proses dilakukan sebanyak N-1 tahapan (disebut "pass"). – Pada setiap Pass:
• tabel "terdiri dari" dua bagian: yang sudah terurut yaitu [1..Pass - 1] dan yang belum terurut yaitu [Pass..NMax] • Ambil elemen TPass, sisipkan ke dalam T[1..Pass-1] dengan tetap menjaga keterurutan dengan cara menggeser elemenelemen, hingga ditemukan tempat yang cocok untuk elemen TPass tersebut
Insertion Sort Ilustrasi • Elemen 1 dianggap sudah terurut • Pada iterasi ke-i:
– Elemen 1..i-1 sudahterurut – Sisipkan elemen ke-i di antara elemen 1..i1 dengan tetap menjaga keterurutan elemen • Dapat dicapai dengan cara menggeser elemen yang nilainya lebih besar
1
12
12
10
10
10
10
2
35
35
12
12
12
12
3
10
10
35
35
30
25
4
60
60
60
60
35
30
5
30
30
30
30
60
35
6
25
25
25
25
25
60
Elemen yang akan disisipkan
Insertion Sort Algoritma
Kamus : i : integer { indeks untuk traversal tabel } Pass : integer { tahapan pengurutan } Temp : integer { penampung nilai sementara untuk pergeseran} T : array [0..NMax] of integer N : integer {Jumlah elemen T}
ALGORITMA { T1 adalah terurut} Pass traversal [2...N] Temp TPass {Simpan harga TPass sebelum pergeseran } { Sisipkan elemen ke Pass dalam T[1..Pass-1] sambil menggeser:} iPass-1 while(Temp < Ti ) and (i>1) do Ti+1 Ti {geser} i i -1 {berikutnya} { Temp >= Ti (tempat yang tepat) or i=1 (sisipkan sebagai elemen pertama) } depend on T, i, Temp Temp >= T1 : T1 +1 Temp {menentukan tempat yang tepat} Temp < T1 : T1 +1 T1 T1 Temp {sebagai elemen pertama} { T[1..Pass] terurut: T1 ≤ T2 ≤ T3 .. ≤TPass} {Seluruh tabel terurut, karena Pass = N : T1≤ T2 ≤ T3 ...... ≤ TN }
Diskusikan • Bagaimana cara membuat notasi algoritmik untuk membuat: – Bubble sort dengan urutan dari besar ke kecil – Selection sort dengan urutan dari kecil ke besar – Insertion sort dengan urutan dari besar ke kecil
Referensi • Inggriani Liem, IF-ITB, Diktat Pemrograman Prosedural (2007) • Catatan: Sebagian besar slide ini transformasi dari pdf slide presentasi itb
THANKS
