Data Structure Chapter 11
SORTING
Dahlia Widhyaestoeti, S.Kom
Agenda Hari Ini
Heap Sort Radix Sort Merge Sort Quick Sort
2
Heap Sort Sort yang memanfaatkan Pohon Heap. Pohon Heap adalah pohon biner complete dimana nilai yang terkandung dalam simpul bapak (Father/F) lebih besar atau lebih kecil dari nilai kedua buah simpul anaknya atau simpul Son (S), sedangkan simpul anak cabang kiri bisa lebih besar, lebih kecil atau sama dengan nilai simpul anak cabang kanan. Contoh pohon heap
92 1
37
Contoh bukan pohon heap
0
48 2
86
1
37
0 2
86
3
Heap Sort Sistem Penomoran Simpul
0
n
2n+1
2n+2
1
F=Father
5
2
11
12
S
S=Son
4
Heap Sort Proses 0
1
2
3
4
5
6
7
27 57 48 37 12 92 86 33 1 0
1
2
Data awal
Membentuk Heap 3
4
5
6
7
92 37 86 33 12 48 57 25
Data membentuk Pohon Heap
5
Heap Sort Proses
0
1
2
3
4
5
6
7
57 25 48 37 12 92 86 33
Tahap 1
57 25 57 1
0
57
0
25
25 1
37
48 12
92
86
33
6
Heap Sort Proses
0
1
2
3
4
5
6
7
57 25 48 37 12 92 86 33
Tahap 2
57 57
0
25
Tetap
48 1
37
48 12
92
86
33
7
0
Heap Sort Proses
1
2
4
5
6
7
57 25 48 37 12 92 86 33 57
Tahap 3
25
3
25 1
37
37 3
12
37
1
48 92
86
33
25 3 57 37
57 37 1
48
0
25
12
92
86
Tetap
33
0
1
2
3
4
5
6
7
57 37 48 25 12 92 86 33
8
0
Heap Sort Proses
1
2
3
4
5
6
7
57 37 48 25 12 92 86 33
Tahap 4 37
1
Tetap 4
0
1
2
3
4
5
6
7
57 37 48 25 12 92 86 33
12 57 37 25
48 12
92
86
33
9
0
Heap Sort Proses
92 5
2
92 48 5
4
5
6
7
57 37
2
3
57 37 48 25 12 92 86 33
Tahap 5 48
1
2
25 33
92 12
0
86
48 1
2
3
4
5
6
7
92 37 57 25 12 48 86 33 92 57
0
92 1
92
0
57
37 25 33
57 12
48
86 10
0
Heap Sort Proses
2
86
2
25
57
6
3
4
5
6
7
92 37
86 6
2
92 37 86 25 12 48 57 33
Tahap 6 57
1
33
86 12
0
57
48 1
2
3
4
5
6
7
92 37 86 25 12 48 57 33 92
92
0
37
Tetap 2
86
25 33
86 12
48
57 11
Heap Sort Proses
92 37
Tahap 7 25 33 7
3
33
12
33
3
86 48
57
25 25 7 0
1
2
3
4
5
6
7
92 37 86 33 12 48 57 25 Sampai disini bagian algoritma yang berfungsi menjadikan pohon awal menjadi Pohon Heap. (Pohon Heap belum terurut).
12
0
Heap Sort Proses
1 Ujung paling kanan TAHAP1
Tahap 1 0 25
1
2
92
3
4
5
6
7
37
86
3
4
33
12
25 7
92 37 86 33 12 48 57 25
x
92
1
37 4
33
12
25 7
2
37
86
3
48 5
Langkah-1 Menyimpan nilai ujung paling kanan di X
92
1
57 6
4
33
12
92 7
57
5
6
37
48
57
5
6
Langkah-2 Menenempatkan nilai tertinggi di ujung paling kanan
86
1
2
86
3
48
0
0
0
2
86
3
4
33
12
92 7
2
48
57
5
6
Langkah-3 86>37, dan 86>X Maka 86 yang diambil menggntikan 92 di no.0 13
Heap Sort Proses
0
1
2
3
4
5
92
37
86
33
12
48
0
1
2
3
4
5
86
37
57
33
6
7
57 25
Tahap 1
1
0
0
86
86
37 4
33
12
48
57
5
6
Langkah-4 57>48, dan 57>X Maka 57 yang diambil menggntikan 86 di no.2
25
92
57
3
4
33
12
92 7
7
2
37
57
3
92 7
1
2
12 48
6
48
25
5
6
Langkah-5 Selesai karena simpul 6 tidak punya anak, maka terakhir X disisipkan ke no 6 menggantikan 57
14
0
Heap Sort Proses
1 Ujung paling kanan TAHAP2
Tahap 2
25 x
86
0
1
2
3
4
86
37
57
33
5
12 48
6
7
25
92
2
37
57
3
4
33
12
92 7
48
25
5
6
0
86
1
37 3
4
33
12
92 7Langkah-1
2
1
57
37
48
25
5
6
Menyimpan nilai ujung paling kanan Tahap-2 di X
86
2
1
57
3
4
33
12
92 7 Langkah-2
2
37
48
86
5
6
Menenempatkan nilai tertinggi di ujung paling kanan Tahap-2
57
57
3
4
33
12
92 7
48
86
5
6
Langkah-3 57>37, dan 57>X Maka 57 yang diambil menggntikan 86 di no.0
15
Heap Sort Proses Tahap 2
57
1
37 3
4
33
12
2
1
48
37
48
86
5
6
Langkah-4 Hanya 48, (dan 48>X) Yang bisa menggantikan 57 di simpul no. 2
92 7
0
1
2
3
86
37
57
33
0
1
2
3
57
37
48
33
4
57
5
6
7
12 48
25
92
4
6
7
86
92
5
12 25
48
3
4
33
12
92 7
2
25
86
5
6
Langkah-5 Selesai karena 5 tidak punya anak, maka terakhir X diisikan ke A[5] menggantikan 48
16
Heap Sort Proses
1 Ujung paling kanan TAHAP3
Tahap 3
25 x
57
0
1
2
3
4
57
37
48
33
5
12 25
2
37
6
7
86
92
48
3
4
33
12
25
86
5
6
92 7 Simpul 6 dan 7 tidak ikut di proses
57
1
37
1
2
37
48
3
4
33
12
25
Langkah-1 Menyimpan nilai ujung paling kanan Tahap-3 di X
57
3
4
33
12
2
1
48
37
57
Langkah-2 Menenempatkan nilai tertinggi di ujung paling kanan Tahap-3
48
2
48
3
4
33
12
57
Langkah-3 48>37 Maka 48 yang diambil menggntikan 57 di no.0
17
Heap Sort Proses Tahap 3 48
1
37
0
1
2
3
57
37
48
33
0
1
2
3
48
37
25
33
4
5
12 25
6
7
86
92
6
7
86
92
2
25
3
4
33
12
57
Langkah-4 Selesai karena simpul 2 tidak punya anak yang bisa menggantikannya, maka terakhir X diisikan ke A[2], menngantikan 48
4
5
12 57
Dan selanjutnya dan berakhir sampai tahap ke-7
18
Radix Sort Radix adalah dasar atau basis (base) bilangan. Bilangan yang biasa digunakan sehari-hari adalah bilangan decimal yaitu bilangan dasar 10. Radix Sort adalah sort yang dilakukan dengan cara mengelompokkan nilai-nilai, bukan membandingkan nilai besar atau nilai kecil. Nilai-nilai dikelompokkan secara bertahap, dimana setiap tahap nilai-nilai dikelompokkan berdasarkan nilai setiap posisi angka, satuan, puluhan, ratusan dst.
19
Radix Sort Proses
Misal data yang ingin di sort (dalam array 1 dimensi) : 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
25
127
38
165
32
725
15
214
56
77
5
42
321
45
11
Dari semua nilai diatas, nilai yang terbesar adalah 725. Karena bilangan terbesar terdiri dari 3 angka, maka pengelompokkan dibagi 3 tahap.
20
Tahap 1
Radix Sort
Nilai dikelompokkan berdasarkan angka satuan yang sama, sehingga terlihat kelompok sebagai berikut:
Proses Angka satuan
Kelompok nilai yang angka satuannya sama
0 1
321 11
2
172 32 42
3 4
214
5
25 165 725 15 5 45
6
56
7
77
8
38
Kemudian dijadikan satu kembali kedalam array menjadi:
9 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
321
11
172
32
42
214
25
165
725
15
5
45
56
77
38
21
Tahap 2
Radix Sort
Nilainilai dari tahap1 dikelompokkan berdasarkan angka puluhan, sehingga didapat kelompok sebagai berikut:
Proses Angka puluhan
Kelompok nilai yang angka puluhannya sama
0
05
1
11 214 15
2
321 25 725
3
32 38
4
42 48
5
56
6
165
7
172 77
8
Kemudian dijadikan satu kembali kedalam array menjadi:
9 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
5
11
214
15
321
25
725
32
38
42
45
56
165
172
77
22
Tahap 3
Radix Sort
Hasil dari tahap1 dikelompokkan lagi berdasarkan angka ratusan, sehingga didapat kelompok sebagai berikut:
Proses Angka ratusan
Kelompok nilai yang angka ratusannya sama
0
005 011 015 025 032 038 042 045 056 077
1
165 172
2
214
3
321
4 5 6 Kemudian dijadikan satu kembali kedalam array menjadi:
7
725
8
9
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
5
11
15
25
32
38
42
45
56
77
165
172
214
321
725 23
Merge Sort
24
Merge Sort Data awal
25
Merge Sort
26
Merge Sort
27
Merge Sort
28
Merge Sort
29
Merge Sort
30
Merge Sort
31
Merge Sort
32
Merge Sort
33
Merge Sort
34
Merge Sort
35
Merge Sort
36
Merge Sort
37
Quick Sort Metode pengurutan yang membandingkan suatu elemen (pivot) dengan elemen yang lain yang lebih kecil dari pada pivot terletak disebelah kiri pivot sedangkan elemen yang lebih besar dari pivot diletakkan di sebelah kanan pivot. Proses yang dilakukan : Cari nilai pivot : i bergerak ke kiri ke kanan sampai mendapat nilai>=pivot j bergerak ke kanan ke kiri sampai mendapat nilai
38
Quick Sort
39
Quick Sort
40
Quick Sort
41
Quick Sort
42
Quick Sort
43
Quick Sort
44
Quick Sort
45
