26/05/2010
Pengurutan (Sorting) Algoritma Pemrograman
[email protected]
http://learning.mas-anto.com
1
Definisi • Sorting /pengurutan – proses mengatur sekumpulan obyek menurut urutan atau susunan tertentu. • Bentuk susunan/urutan : – Ascending – menaik/membesar – Descending – menurun/mengecil
• Data yang diurut dapat berupa numerik atau tipe bentukan. • Jika tipe bentukan harus berupa field. http://learning.mas-anto.com
2
1
26/05/2010
Pengelompokan Pengurutan • Dikelompokkan dalam 2 kelompok : 1. Pengurutan internal – pengurutan sekumpulan data yang disimpan didalam memori utama komputer. 2. Pengurutan eksternal – pengurutan data yang ada dalam memori sekunder dan biasanya volumenya besar.
• Pengurutan internal mempunyai performansi yang baik cepat, tapi boros memori. http://learning.mas-anto.com
3
Macam Algoritma Pengurutan •
Macam-macam algoritma sorting : 1. 2. 3. 4. 5. 6. 7. 8. 9.
Maximum Sort Insertion Sort Bubble Sort Heap Sort Shell Sort Quick Sort Merge Sort Radix Sort Tree Sort http://learning.mas-anto.com
4
2
26/05/2010
Tiga Algoritma Sorting • Algoritma yang akan dibahas adalah : 1. Pengurutan Gelembung (Bubble Sort) 2. Pengurutan Pemilihan (Selection Sort 1. Minimum Sort 2. Maksimum Sort
3. Pengurutan Sisip (Insertion Sort)
http://learning.mas-anto.com
5
Bubble Sort (1) • Terinspirasi oleh gelembung sabun yang ada diatas permukaan. Gelembung mengapung karena massa-nya lebih kecil dari air itu sendiri. • Prinsipnya : mengapungkan elemen array berharga paling kecil ‘diapungkan’ artinya diangkat ke atas (ke ujung kiri array).
http://learning.mas-anto.com
6
3
26/05/2010
Bubble Sort (2) Tahapan Pengurutan – Bubble Sort Ascending 1. Langkah 1 : Mulai elemen K=N, N-1, …, 2 bandingkan L[K] dengan L[K-1]. Jika L[K]
http://learning.mas-anto.com
7
Bubble Sort (3) Array dengan N=6 belum terurut “
Ilustrasi : Langkah 1 : K=N=6 K=5 K=4 K=3 K=2 8 Langkah 2 : K=N=6 K=5 K=4 K=3 8
8 25
10
25
27
10
8
76
21
1
2
3
4
5
6
8 27 27
10 25
8 10 10 10
21 21 21 21 21
76 76 76 76 76
10 27 27
21 21 21 21
76 76 76 76
Langkah 3 : K=N=6 K=5 K=4 8
10
Langkah 4 : K=N=6 K=5 8 Langkah 5 : K=N=6 8
http://learning.mas-anto.com
21
21 25
21 27 27
76 76 76
10
21
25
27 27
76 76
10
21
25
27
76
8
4
26/05/2010
Bubble Sort (4) Algoritma Bubble Sort Ascending : Procedure BubbleSortAsc(input/output L : Larik; input N : integer) Deklarasi I : integer {jumlah langkah} K : integer { pengapungan tiap langkah} Temp : integer { untuk penukaran nilai} Tukar : boolean { kontrol} 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 Temp = L[K] L[K] = L[K-1] L[K-1] = Temp Endif EndFor I=I+1 EndWhile http://learning.mas-anto.com
9
Bubble Sort (4) Procedure BubbleSortDesc(input/output L : Larik; input N : integer) Deklarasi I : integer {jumlah langkah} K : integer { pengapungan tiap langkah} Temp : integer { untuk penukaran nilai} 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 EndFor
http://learning.mas-anto.com
10
5
26/05/2010
Selection Sort Selection sort terdiri dari : 1. Maximum Sort 2. Minimum Sort
http://learning.mas-anto.com
11
Maximum Sort (1) Algoritma Maximum Sort Ascending Langkah 1 : Tentukan harga maksimum didalam L[1..N]. Tukar harga maksimum dengan elemen L[N] Langkah 2 : Tentukan harga maksimum didalam L[1..N-1]. Tukar harga maksimum dengan elemen L[N-1] Langkah 3 : Tentukan harga maksimum didalam L[1..N-2]. Tukar harga maksimum dengan elemen L[N-2] ….. Langkah N : Tentukan harga maksimum didalam L[1..2]. Tukar harga maksimum dengan elemen L[2] http://learning.mas-anto.com
12
6
26/05/2010
Maximum Sort (2) Ilustrasi : 25
27
10
8
76
21
1
2
3
4
5
6
Langkah 1 : Cari elemen maksimum dalam L[1..6], maks = 76. Tukar Maks dengan L[N] menjadi :
25
27
10
8
21
76
1
2
3
4
5
6
Langkah 2: Cari elemen maksimum dalam L[1..5], maks = 27. Tukar Maks dengan L[5] menjadi :
25
21
10
8
27
76
1
2
3
4
5
6
Langkah 3: Cari elemen maksimum dalam L[1..4], maks = 25. Tukar Maks dengan L[4] menjadi :
8
21
10
25
27
76
1
2
3
4
5
6
Langkah 4: Cari elemen maksimum dalam L[1..3], maks = 21 Tukar Maks dengan L[3] menjadi :
8
10
21
25
27
76
1
2
3
4
5
6
Langkah 5: Cari elemen maksimum dalam L[1..2], maks = 10 Tukar Maks dengan L[2] menjadi :
8
10
21
25
27
76
1
2
3
4
5
6
http://learning.mas-anto.com
13
Maximum Sort (3) Algoritma Maksimum Sort Ascending Procedure MaksSortAsc(input/output L : Larik; input N : integer) Deklarasi I : integer {jumlah langkah} J : integer { mencari nilai maks} U : integer { indeks ujung kiri } Maks : integer { nilai maks sementara } Imaks : Integer { indeks maks sementara } Temp : integer { untuk penukaran nilai} Algoritma U = N For I=1 to N-1 do Imaks = 1 For J=2 to U do If L[J] > L[Imaks] then Imaks=J Endif Endfor Temp=L[U] L[U]=L[Imaks] L[Imaks]= Temp U=U-1 http://learning.mas-anto.com Endfor
14
7
26/05/2010
Maximum Sort (4) Algoritma Maximum Sort Descending Langkah 1 : Tentukan harga minimum didalam L[1..N]. Tukar harga maksimum dengan elemen L[1] Langkah 2 : Tentukan harga minimum didalam L[2..N]. Tukar harga maksimum dengan elemen L[2] Langkah 3 : Tentukan harga maksimum didalam L[3..N]. Tukar harga maksimum dengan elemen L[3] ….. Langkah N : Tentukan harga maksimum didalam L[N-1,N]. Tukar harga maksimum dengan elemen L[N-1] http://learning.mas-anto.com
15
Minimum Sort (1) • Prinsipnya sama dengan maksimum sort hanya, sebagai dasar adalah nilai minimum. • Algoritma Minimum Sort Ascending – mencari nilai minimum dalam sebuah array, taruh hasilnya pada elemen pertama (kiri), dan seterusnya. • Algoritma Minimum Sort Descending – mencari nilai minimum dalam sebuah array, taruh hasilnya pada elemen terakhir (kanan), dan seterusnya. http://learning.mas-anto.com
16
8
26/05/2010
Minimum Sort (2) Procedure MinSortAsc(input/output L : Larik; input N : integer) Deklarasi I : integer {jumlah langkah} J : integer { mencari nilai min} U : integer { indeks ujung kiri } Min : integer { nilai maks sementara } Imin : Integer { indeks maks sementara } Temp : integer { untuk penukaran nilai} Algoritma U = N For I=1 to N-1 do Imin = 1 For J=2 to U do If L[J]
17
Insertion Sort (1) • Menyisipkan elemen larik pada posisi yang tepat dan dilakukan secara beruntun dalam larik. • Setelah menemukan posisi yang tepat, maka akan dilakukan proses pergeseran elemen yang ada.
http://learning.mas-anto.com
18
9
26/05/2010
Insertion Sort (2) Mekanisme Pengurutan : • Langkah 1 : Anggap L[1] sudah pada posisi yang tepat. • Langkah 2 : L[2] harus dicari posisi yang tepat antara L[1..2] dengan cara menggeser elemen. • Langkah 3 : L[3] harus dicari posisi yang tepat antara L[1..3] dengan cara menggeser elemen. • …. • Langkah N: L[N] harus dicari posisi yang tepat antara L[1..N] dengan cara menggeser elemen. http://learning.mas-anto.com
19
Insertion Sort (3) Ilustrasi Insertion Sort Ascending 25
27
10
8
76
21
1
2
3
4
5
6
Anggap L[1] sudah terurut
25
27
10
8
76
21
1
2
3
4
5
6
Langkah 2 : Cari posisi yang tepat untuk L[2] pada L[1..2] maka :
25
27
10
8
76
21
1
2
3
4
5
6
Cari posisi yang tepat untuk L[3] pada L[1..3] maka :
25
27
8
8
10
25
27
76
21
1
2
3
4
5
6
Langkah 5 : Cari posisi yang tepat untuk L[5] pada L[1..5] maka :
8
10
25
27
76
21
1
2
3
4
5
6
Langkah 6 : Cari posisi yang tepat untuk L[6] pada L[1..6] maka :
Langkah 3 :
10
Langkah 4 : Cari posisi yang tepat untuk L[4] pada L[1..4] maka :
76
21
8
10
21
25
27
76
1
2
3
4
5
6
http://learning.mas-anto.com
20
10
26/05/2010
Insertion Sort (3) Ascending Procedure InsertSortAsc(input/output L : Larik; input N : integer) Deklarasi K : integer {jumlah langkah} J : integer { penelusuran array } Temp : integer { untuk penukaran nilai} Algoritma For K=2 to N do Temp = L[K] 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 http://learning.mas-anto.com
21
Insertion Sort (4) Descending Procedure InsertSortDesc(input/output L : Larik; input N : integer) Deklarasi K : integer {jumlah langkah} J : integer { penelusuran array } Temp : integer { untuk penukaran nilai} Algoritma For K=2 to N do Temp = L[K] 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 http://learning.mas-anto.com
22
11
26/05/2010
Latihan Perhatikan array dibawah ini : 45
12
-1
0
4
5
-2
14
17
3
1
2
3
4
5
6
7
8
9
10
Soal : Tuliskan langkah proses pengurutan dengan metode algoritma : a) b) c)
Buble Sort Descending Minimum Sort Ascending Insertion Sort Descending
http://learning.mas-anto.com
23
Tugas Kelompok • Terjemahkan algoritma-algoritma pengurutan berikut ini ke dalam bahasa pemrograman Pascal atau C atau Visual Basic atau Java : – – – –
Binnary Search Bubble Sort Ascending Maksimum Sort Ascending Insertion Sort Descending
• Program harus disertai dengan penjelasannya dan siap dieksekusi serta tanpa error. • Hasilnya diupload paling lambat tanggal 26 Juni 2010 melalui eSinaukoe. http://learning.mas-anto.com
24
12
