Download - Sorting 1
Fakultas Teknik Elektro & Komputer UKSW 1 / 156Download dari : http://ambonmemanggil.blogspot.com
Algoritma Sorting
1. Bubble2. Selection3. Insertion4. Merge5. Quick
Fakultas Teknik Elektro & Komputer UKSW 2 / 156Download dari : http://ambonmemanggil.blogspot.com
Bubble Sort
• Sorting akan bergerak dari elemen pertama sampai elemen terakhir
• Membandingkan setiap elemen dengan elemen berikut
– Elemen terbesar akan ditempatkan sebelah kanan
– Proses Swap, sangat berperan
512354277 101
1 2 3 4 5 6
Fakultas Teknik Elektro & Komputer UKSW 3 / 156Download dari : http://ambonmemanggil.blogspot.com
Bubble Sort
• Sorting akan bergerak dari elemen pertama sampai elemen terakhir
• Membandingkan setiap elemen dengan elemen berikut
– Elemen terbesar akan ditempatkan sebelah kanan
– Proses Swap, sangat berperan
512354277 101
1 2 3 4 5 6
Swap42 77
Fakultas Teknik Elektro & Komputer UKSW 4 / 156Download dari : http://ambonmemanggil.blogspot.com
Bubble Sort
• Sorting akan bergerak dari elemen pertama sampai elemen terakhir
• Membandingkan setiap elemen dengan elemen berikut
– Elemen terbesar akan ditempatkan sebelah kanan
– Proses Swap, sangat berperan
512357742 101
1 2 3 4 5 6
Swap35 77
Fakultas Teknik Elektro & Komputer UKSW 5 / 156Download dari : http://ambonmemanggil.blogspot.com
Bubble Sort
• Sorting akan bergerak dari elemen pertama sampai elemen terakhir
• Membandingkan setiap elemen dengan elemen berikut
– Elemen terbesar akan ditempatkan sebelah kanan
– Proses Swap, sangat berperan
512773542 101
1 2 3 4 5 6
Swap12 77
Fakultas Teknik Elektro & Komputer UKSW 6 / 156Download dari : http://ambonmemanggil.blogspot.com
Bubble Sort
• Sorting akan bergerak dari elemen pertama sampai elemen terakhir
• Membandingkan setiap elemen dengan elemen berikut
– Elemen terbesar akan ditempatkan sebelah kanan
– Proses Swap, sangat berperan
577123542 101
1 2 3 4 5 6
Tidak butuh swap
Fakultas Teknik Elektro & Komputer UKSW 7 / 156Download dari : http://ambonmemanggil.blogspot.com
Bubble Sort
• Sorting akan bergerak dari elemen pertama sampai elemen terakhir
• Membandingkan setiap elemen dengan elemen berikut
– Elemen terbesar akan ditempatkan sebelah kanan
– Proses Swap, sangat berperan
577123542 101
1 2 3 4 5 6
Swap5 101
Fakultas Teknik Elektro & Komputer UKSW 8 / 156Download dari : http://ambonmemanggil.blogspot.com
Bubble Sort
• Sorting akan bergerak dari elemen pertama sampai elemen terakhir
• Membandingkan setiap elemen dengan elemen berikut
– Elemen terbesar akan ditempatkan sebelah kanan
– Proses Swap, sangat berperan
77123542 5
1 2 3 4 5 6
101
Nilai terbesar berada di kanan
Fakultas Teknik Elektro & Komputer UKSW 9 / 156Download dari : http://ambonmemanggil.blogspot.com
Bubble Sort
index = 1last_compare_at = n – 1
repeat exit if(index > last_compare_at) if(A[index] > A[index + 1]) then Swap(A[index], A[index + 1]) endif index = index + 1End of repeat
Fakultas Teknik Elektro & Komputer UKSW 10 / 156Download dari : http://ambonmemanggil.blogspot.com
Bubble Sort
• Dari setiap iterasi, Nilai yang terbesar akan menempati posisi paling kanan
• Jika terdapat N data, maka iterasi harus diulang sebanyak N-1
77123542 5
1 2 3 4 5 6
101
Fakultas Teknik Elektro & Komputer UKSW 11 / 156Download dari : http://ambonmemanggil.blogspot.com
Bubble Sort
77123542 51 2 3 4 5 6
101
5421235 771 2 3 4 5 6
101
42 5 3512 771 2 3 4 5 6
101
42 35 512 771 2 3 4 5 6
101
42 35 12 5 771 2 3 4 5 6
101
N -
1
Fakultas Teknik Elektro & Komputer UKSW 12 / 156Download dari : http://ambonmemanggil.blogspot.com
Mengurangi Jumlah Perbdgn
12 35 42 77 1011 2 3 4 5 6
5
77123542 51 2 3 4 5 6
101
5421235 771 2 3 4 5 6
101
42 5 3512 771 2 3 4 5 6
101
42 35 512 771 2 3 4 5 6
101
Fakultas Teknik Elektro & Komputer UKSW 13 / 156Download dari : http://ambonmemanggil.blogspot.com
Mengurangi Jumlah Perbdgn
• Jika sudah melakukan N buah iterasi maka jumlah perbandingan yang tersisa adalah MAX-N perbandingan.
• Contoh:– Sudah terjadi 4 iterasi– Jumlah MAX sebanyak 6– maka hanya tinggal 2 perbandingan lagi
42 5 3512 771 2 3 4 5 6
101
Fakultas Teknik Elektro & Komputer UKSW 14 / 156Download dari : http://ambonmemanggil.blogspot.com
void bubble_sort(int data[], int size) {
int temp; // for swap
int i, rightmost; // loop variables
for (rightmost = size-1; rightmost > 0; rightmost--)
for (i = 0; i < rightmost; i++)
if (data[i] > data[i+1] ) { // swap if greater
temp = data[i];
data[i] = data[i+1];
data[i+1] = temp;
}
}
Inn
er lo
op
Ou
ter
loo
p
Fakultas Teknik Elektro & Komputer UKSW 15 / 156Download dari : http://ambonmemanggil.blogspot.com
Perlu Deteksi Data Terurut
• Data yang sudah terurut perlu untuk dideteksi
– Pemborosan waktu, mengurutkan data yang sudah terurut
• Pendeteksian data terurut hanya butuh 1 (satu) iterasi, sehingga akan menghemat waktu jika dibandingkan tidak ada mekanisme deteksi ini
42 35 12 5 771 2 3 4 5 6
101
Fakultas Teknik Elektro & Komputer UKSW 16 / 156Download dari : http://ambonmemanggil.blogspot.com
Deteksi Menggunakan 'Flag'
• Proses deteksi data yang terurut bisa menggunakan Flag
• Misal :– Flag = 0 : Jika tidak terjadi swap– Flag = 1 : Jika terjadi swap
• Dari iterasi pertama, jika Flag=0 maka dipastikan data sudah terurut
Fakultas Teknik Elektro & Komputer UKSW 17 / 156Download dari : http://ambonmemanggil.blogspot.com
void bubble_sort(int data[], int size) {
int temp; // for swap
int i, rightmost; // loop variables
for (rightmost = size-1; rightmost > 0; rightmost--) {
for (i = 0; i < rightmost; i++) {
flag = 0;
if (data[i] > data[i+1] ) { // swap if greater
temp = data[i];
data[i] = data[i+1];
data[i+1] = temp;
flag = 1;
}
}
if (flag==0) return;
}
}
Inn
er lo
op
Ou
ter
loo
p
Fakultas Teknik Elektro & Komputer UKSW 18 / 156Download dari : http://ambonmemanggil.blogspot.com
Kesimpulan
• Bubble Sort akan menempatkan angka terbesar ke sebelah kanan
• Perlu beberapa iterasi untuk mendapatkan data yang terurut– Maksimum iterasi N-1– Jika data telah terurut, tidak terjadi swap,
proses bisa dihentikan setelah iterasi pertama
Fakultas Teknik Elektro & Komputer UKSW 19 / 156Download dari : http://ambonmemanggil.blogspot.com
Waktu O(N2) Runtime• Waktu run time dari sebuah algoritma perlu
diperhatikan• misal akan dilakukan pengurutan terhadap
250,000,000 data• N = 250,000,000• Jika waktu yang dibutuhkan adalah N2
• N2 = 6.25 x 1016
• Misal sebuah operasi butuh 1 nanosecond (10-9 sec) . Waktu yang sangat cepat
• waktu yang dibutuhkan 6.25 x 107 detik
• jadi 6.25 x 107
60 x 60 x 24 x 365 = 1.98 tahun
Fakultas Teknik Elektro & Komputer UKSW 20 / 156Download dari : http://ambonmemanggil.blogspot.com
Sorting Algorithms
1. Bubble2. Selection3. Insertion4. Merge5. Quick
Fakultas Teknik Elektro & Komputer UKSW 21 / 156Download dari : http://ambonmemanggil.blogspot.com
3 410 6 8 9 7 2 1 5
• Cari data terbesar, dalam contoh ini=10• Tukarkan data tersebut dengan data yang berada pada posisi terakhir, dalam contoh ini=5
Selection Sort (Salah satu algoritma sorting sederhana)
Fakultas Teknik Elektro & Komputer UKSW 22 / 156Download dari : http://ambonmemanggil.blogspot.com
3 410 6 8 9 7 2 1 55
3 45 6 8 9 7 2 1 10
93 45 6 8 7 2 1 101
3 45 6 8 7 21 109
Cari data terbesar berikutnya, angka 9Tukarkan dengan data yang berada pada posisi terakhir ke-2, angka 1
Fakultas Teknik Elektro & Komputer UKSW 23 / 156Download dari : http://ambonmemanggil.blogspot.com
Dua data terakhir, 9 dan 10, tidak akan diubah-ubah lagi karena sudah menempati posisi yang sesuai.
Lakukan langkah selanjutnya seperti yang telah dicontohkan
3 45 6 8 7 21 109
Fakultas Teknik Elektro & Komputer UKSW 24 / 156Download dari : http://ambonmemanggil.blogspot.com
3 45 6 8 7 21 1098 2
3 45 6 872 1 109
3 45 6 872 1 109
3 45 6 872 1 1096 1
3 45 6 8721 109
7
Fakultas Teknik Elektro & Komputer UKSW 25 / 156Download dari : http://ambonmemanggil.blogspot.com
3 45 6 8721 1095 2
3 4 5 6 872 1 109
3 4 5 6 872 1 1094
3 4 5 6 872 1 109
3 4 5 6 872 1 1093
3 4 5 6 8721 109
3 4 5 6 8721 109
1
1
Fakultas Teknik Elektro & Komputer UKSW 26 / 156Download dari : http://ambonmemanggil.blogspot.com
Void SelectionSort (Item A[], int left, int right){
int i, j;for (i = left; i < right; i++){
int min = i;for (j = i+1; j <= right; j++)
if (less(A[j], A[min]) min = j;exch(A[i], A[min]);
}}
Fakultas Teknik Elektro & Komputer UKSW 27 / 156Download dari : http://ambonmemanggil.blogspot.com
Fakultas Teknik Elektro & Komputer UKSW 28 / 156Download dari : http://ambonmemanggil.blogspot.com
Sorting Algorithms
1. Bubble2. Selection3. Insertion4. Merge5. Quick
Fakultas Teknik Elektro & Komputer UKSW 29 / 156Download dari : http://ambonmemanggil.blogspot.com
• Sisi sebelah kiri tetap dipertahankan• Telusuri sisi sebelah kanan, jika lebih
kecil dari sisi sebelah kiri, lakukan proses insert
• Perhatikan ilustrasi berikut (fokus ke gambar)
Algoritma Insertion
Fakultas Teknik Elektro & Komputer UKSW 30 / 156Download dari : http://ambonmemanggil.blogspot.com
3 410 6 8 9 7 2 1 5
Proses dimulai pada data ke-2, angka 10
Insertion Sort
Fakultas Teknik Elektro & Komputer UKSW 31 / 156Download dari : http://ambonmemanggil.blogspot.com
43 6 8 9 7 2 1 5
4 56 8 9 7 2 1
Cek apakah data ke-2 lebih kecil dari data sebelumnyaTernyata tidak, jadi tidak ada operasi insert
10
3 10
Fakultas Teknik Elektro & Komputer UKSW 32 / 156Download dari : http://ambonmemanggil.blogspot.com
4 56 8 9 7 2 1
Dua angka pertama sudah dalam posisi urut (tapi belum semuanya)
3
Pada state ini, angka empat akan disisipkan (proses insert) diantara 3 dan 10
10
4 56 8 9 7 2 13 10 4
Fakultas Teknik Elektro & Komputer UKSW 33 / 156Download dari : http://ambonmemanggil.blogspot.com
Hapus data yang ketiga, angka 4
56 8 9 7 2 13 10
4
geser angka 10, untuk memberikan tempat bagi angka 4
56 8 9 7 2 13 10
4
masukan angka 4 pada posisinya
56 8 9 7 2 13 104
Fakultas Teknik Elektro & Komputer UKSW 34 / 156Download dari : http://ambonmemanggil.blogspot.com
Saat ini sudah semakin banyak data yang di dalam posisi terurut
510 8 9 7 2 13 64
ulangi proses yang sama, sampai data yang terakhir
5108 9 7 2 13 64
5108 9 7 2 13 64
Fakultas Teknik Elektro & Komputer UKSW 35 / 156Download dari : http://ambonmemanggil.blogspot.com
5
108 9
2 13 64
7
5108 9 2 13 64 7
5108 92 13 64 7
5108 921 3 64 7
5 108 921 3 64 7
Fakultas Teknik Elektro & Komputer UKSW 36 / 156Download dari : http://ambonmemanggil.blogspot.com
void InsertionSort(T *a, tblIndex lb, tblIndex ub) {
T t; tblIndex i, j;
for (i = lb + 1; i <= ub; i++) {
t = a[i]; /* Shift elements down until */ /* insertion point found. */ for (j = i-1; j >= lb && compGT(a[j], t); j--)
a[j+1] = a[j]; /* insert */ a[j+1] = t;
} }
Fakultas Teknik Elektro & Komputer UKSW 37 / 156Download dari : http://ambonmemanggil.blogspot.com
Analisa Algoritma Insertion Sort
• Jika terdapat n element, perlu penelusuran sebanyak n-1 kali
• Pada setiap iterasi, ada kemungkinan akan selalu terjadi proses insert yang menyebabkan kondisi O(n2) untuk runtime.
• Tidak butuh memori tambahan untuk melakukan proses insert
• Algoritma ini adalah algoritma pengurutan yang stabil. setiap angka yang sudah berada pada posisinya, tidak akan diubah-ubah lagi
Fakultas Teknik Elektro & Komputer UKSW 38 / 156Download dari : http://ambonmemanggil.blogspot.com
• Bubble sort menggunakan N2/2 perbandingan dan N2/2 pertukaran pada kondisi rata-rata dan kondisi terburuk.
• Selection sort menggunakan N2/2 perbandingan dan N pertukaran pada kondisi rata-rata, dan menjadi 2xN pada kondisi terburuk.
• Insertion sort menggunakan N2/4
perbandingan dan N2/8 pertukaran dan bersifat linear pada kondisi data telah terurut.
Fakultas Teknik Elektro & Komputer UKSW 39 / 156Download dari : http://ambonmemanggil.blogspot.com
Sorting Algorithms
1. Bubble2. Selection3. Insertion4. Merge5. Quick
Fakultas Teknik Elektro & Komputer UKSW 40 / 156Download dari : http://ambonmemanggil.blogspot.com
Divide and Conquer
• Algoritma Jenis ini akan membagi masalah menjadi 2 (dua)
–Setiap bagian diproses lagi menjadi bagian yang lebih kecil
–Hasil dari bagian-bagian ini kemudian disatukan kembali dalam kondisi terurut
Fakultas Teknik Elektro & Komputer UKSW 41 / 156Download dari : http://ambonmemanggil.blogspot.com
Mergesort
• MergeSort termasuk dalam kategori algoritma Devide and Conquer
• Array yang belum terurut, dibagi menjadi separuh
– Proses diulang terus sampai ditemukan bagian terkecil
• Hasil dari setiap proses digabungkan :– membandingkan elemen pertama dari setiap bagian– hapus elemen terkecil dan letakan pada hasil– Ulangi semua proses sampai semua elemen terurut
• Contoh : data berikut ini akan diurutkan
37 23 6 89 15 12 2 19
Fakultas Teknik Elektro & Komputer UKSW 42 / 156Download dari : http://ambonmemanggil.blogspot.com
Algorithm
Mergesort(Passed an array) if array size > 1
Divide array in half Call Mergesort on first half. Call Mergesort on second half. Merge two halves.
Merge(Passed two arrays) Compare leading element in each array Select lower and place in new array. (If one input array is empty then place remainder of other array in output array)
Fakultas Teknik Elektro & Komputer UKSW 43 / 156Download dari : http://ambonmemanggil.blogspot.com
Algorithm
Mergesort(Passed an array) if array size > 1
Divide array in half Call Mergesort on first half. Call Mergesort on second half. Merge two halves.
Merge(Passed two arrays) Compare leading element in each array Select lower and place in new array. (If one input array is empty then place remainder of other array in output array)
Fakultas Teknik Elektro & Komputer UKSW 44 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
Fakultas Teknik Elektro & Komputer UKSW 45 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
Fakultas Teknik Elektro & Komputer UKSW 46 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
Fakultas Teknik Elektro & Komputer UKSW 47 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398
Fakultas Teknik Elektro & Komputer UKSW 48 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398
Merge
Fakultas Teknik Elektro & Komputer UKSW 49 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398
23
Merge
Fakultas Teknik Elektro & Komputer UKSW 50 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398
23 98
Merge
Fakultas Teknik Elektro & Komputer UKSW 51 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
23 98
Fakultas Teknik Elektro & Komputer UKSW 52 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
Merge
23 98
Fakultas Teknik Elektro & Komputer UKSW 53 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
14
Merge
23 98
Fakultas Teknik Elektro & Komputer UKSW 54 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
45
Merge
23 98 14
Fakultas Teknik Elektro & Komputer UKSW 55 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
Merge
98 451423
Fakultas Teknik Elektro & Komputer UKSW 56 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
Merge
98 14
14
23 45
Fakultas Teknik Elektro & Komputer UKSW 57 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
Merge
23 14
14 23
98 45
Fakultas Teknik Elektro & Komputer UKSW 58 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
Merge
23 98 4514
14 23 45
Fakultas Teknik Elektro & Komputer UKSW 59 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
Merge
23 98 4514
14 23 45 98
Fakultas Teknik Elektro & Komputer UKSW 60 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
23 98 4514
14 23 45 98
Fakultas Teknik Elektro & Komputer UKSW 61 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676
23 98 4514
14 23 45 98
Fakultas Teknik Elektro & Komputer UKSW 62 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676
Merge
23 98 4514
14 23 45 98
Fakultas Teknik Elektro & Komputer UKSW 63 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676
6
Merge
23 98 4514
14 23 45 98
Fakultas Teknik Elektro & Komputer UKSW 64 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676
67
Merge
23 98 4514 6
14 23 45 98
Fakultas Teknik Elektro & Komputer UKSW 65 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676 33 42
23 98 4514 676
14 23 45 98
Fakultas Teknik Elektro & Komputer UKSW 66 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676 33 42
Merge
23 98 4514 676
14 23 45 98
Fakultas Teknik Elektro & Komputer UKSW 67 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676 33 42
Merge
3323 98 4514 676
14 23 45 98
Fakultas Teknik Elektro & Komputer UKSW 68 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676 33 42
Merge
4223 98 4514 676 33
14 23 45 98
Fakultas Teknik Elektro & Komputer UKSW 69 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676 33 42
Merge
23 98 4514 676 4233
14 23 45 98
Fakultas Teknik Elektro & Komputer UKSW 70 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676 33 42
Merge
23 98 4514 6 4233
14 23 45 98 6
67
Fakultas Teknik Elektro & Komputer UKSW 71 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676 33 42
Merge
23 98 4514 6 33
14 23 45 98 6 33
67 42
Fakultas Teknik Elektro & Komputer UKSW 72 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676 33 42
Merge
23 98 4514 6 4233
14 23 45 98 6 33 42
67
Fakultas Teknik Elektro & Komputer UKSW 73 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676 33 42
Merge
23 98 4514 676 4233
14 23 45 98 6 33 42 67
Fakultas Teknik Elektro & Komputer UKSW 74 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676 33 42
Merge
23 98 4514 676 4233
23 45 98 33 42 6714 6
Fakultas Teknik Elektro & Komputer UKSW 75 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676 33 42
Merge
23 98 4514 676 4233
23 45 98 6 42 67
6
14 33
Fakultas Teknik Elektro & Komputer UKSW 76 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676 33 42
Merge
23 98 4514 676 4233
14 45 98 6 42 67
6 14
23 33
Fakultas Teknik Elektro & Komputer UKSW 77 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676 33 42
Merge
23 98 4514 676 4233
14 23 98 6 42 67
6 14 23
45 33
Fakultas Teknik Elektro & Komputer UKSW 78 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676 33 42
Merge
23 98 4514 676 4233
14 23 98 6 33 67
6 14 23 33
45 42
Fakultas Teknik Elektro & Komputer UKSW 79 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676 33 42
Merge
23 98 4514 676 4233
14 23 98 6 33 42
6 14 23 33 42
45 67
Fakultas Teknik Elektro & Komputer UKSW 80 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676 33 42
Merge
23 98 4514 676 4233
14 23 45 6 33 42
6 14 23 33 42 45
98 67
Fakultas Teknik Elektro & Komputer UKSW 81 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676 33 42
Merge
23 98 4514 676 4233
14 23 45 98 6 33 42 67
6 14 23 33 42 45 67
Fakultas Teknik Elektro & Komputer UKSW 82 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676 33 42
Merge
23 98 4514 676 4233
14 23 45 98 6 33 42 67
6 14 23 33 42 45 67 98
Fakultas Teknik Elektro & Komputer UKSW 83 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
674523 14 6 3398 42
4523 1498
2398 45 14
676 33 42
676 33 42
23 98 4514 676 4233
14 23 45 98 6 33 42 67
6 14 23 33 42 45 67 98
Fakultas Teknik Elektro & Komputer UKSW 84 / 156Download dari : http://ambonmemanggil.blogspot.com
674523 14 6 3398 42
6 14 23 33 42 45 67 98
Fakultas Teknik Elektro & Komputer UKSW 85 / 156Download dari : http://ambonmemanggil.blogspot.com
Kesimpulan
• Divide/membagi data yang tidak terurut menjadi dua bagian
• Ulangi sampai setiap array hanya
memiliki sebuah data• Lakukan merge untuk memperoleh
data terurut
Fakultas Teknik Elektro & Komputer UKSW 86 / 156Download dari : http://ambonmemanggil.blogspot.com
Sorting Algorithms
1. Bubble2. Selection3. Insertion4. Merge5. Quick
Fakultas Teknik Elektro & Komputer UKSW 87 / 156Download dari : http://ambonmemanggil.blogspot.com
Sorting algorithms
• Insertion, selection and bubble sort memiliki O(N2) pada kondisi terburuk
• Algoritma tercepat dengan metode pembandingan :
O(nlogn)
• Mergesort and Quicksort
Fakultas Teknik Elektro & Komputer UKSW 88 / 156Download dari : http://ambonmemanggil.blogspot.com
QuickSort
Pilih“pivot”. Bagi data menjadi lebih kecil dari & lebih besar dari “pivot”. Urutkan Setiap bagian tadi.
Fakultas Teknik Elektro & Komputer UKSW 89 / 156Download dari : http://ambonmemanggil.blogspot.com
Idea of Quicksort
• Pilih: pivot, misal X
• Bagi: pecah elements sehingga X berada pada posisi yang tepat
• Urutkan setiap bagian yang lebih kecil dari X dan yang lebih besar dari X
Fakultas Teknik Elektro & Komputer UKSW 90 / 156Download dari : http://ambonmemanggil.blogspot.com
Algoritma QuickSort
misal terdapat n elements bertipe integer• If array hanya memiliki sebuah data, return• Else
– pilih satu data sebagai pivot.– Pecah elemen menjadi sub-arrays:
• Elemen yang lebih kecil dari pivot• Elemen yang lebih besar dari pivot
– Lakukan Quicksourt pada kedua sub-arrays– kembalikan hasil
Fakultas Teknik Elektro & Komputer UKSW 91 / 156Download dari : http://ambonmemanggil.blogspot.com
Contoh
Misal data berikut akan diurutkan
40 20 10 80 60 50 7 30 100
Fakultas Teknik Elektro & Komputer UKSW 92 / 156Download dari : http://ambonmemanggil.blogspot.com
Idea of Quicksort
• Pilih: pivot, misal X
• Bagi: pecah elements sehingga X berada pada posisi yang tepat
• Urutkan setiap bagian yang lebih kecil dari X dan yang lebih besar dari X
Fakultas Teknik Elektro & Komputer UKSW 93 / 156Download dari : http://ambonmemanggil.blogspot.com
Memilih Pivot
• Ada banyak cara memilih pivot, pada contoh ini misal dipilih data pada index pertama, angka 40.
40 20 10 80 60 50 7 30 100
Fakultas Teknik Elektro & Komputer UKSW 94 / 156Download dari : http://ambonmemanggil.blogspot.com
Idea of Quicksort
• Pilih: pivot, misal X
• Bagi: pecah elements sehingga X berada pada posisi yang tepat
• Urutkan setiap bagian yang lebih kecil dari X dan yang lebih besar dari X
Fakultas Teknik Elektro & Komputer UKSW 95 / 156Download dari : http://ambonmemanggil.blogspot.com
40 20 10 80 60 50 7 30 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
Fakultas Teknik Elektro & Komputer UKSW 96 / 156Download dari : http://ambonmemanggil.blogspot.com
40 20 10 80 60 50 7 30 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1. While data[too_big_index] <= data[pivot]++too_big_index
Fakultas Teknik Elektro & Komputer UKSW 97 / 156Download dari : http://ambonmemanggil.blogspot.com
40 20 10 80 60 50 7 30 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1. While data[too_big_index] <= data[pivot]++too_big_index
Fakultas Teknik Elektro & Komputer UKSW 98 / 156Download dari : http://ambonmemanggil.blogspot.com
40 20 10 80 60 50 7 30 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1. While data[too_big_index] <= data[pivot]++too_big_index
Fakultas Teknik Elektro & Komputer UKSW 99 / 156Download dari : http://ambonmemanggil.blogspot.com
40 20 10 80 60 50 7 30 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
Fakultas Teknik Elektro & Komputer UKSW 100 / 156Download dari : http://ambonmemanggil.blogspot.com
40 20 10 80 60 50 7 30 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
Fakultas Teknik Elektro & Komputer UKSW 101 / 156Download dari : http://ambonmemanggil.blogspot.com
40 20 10 80 60 50 7 30 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
Fakultas Teknik Elektro & Komputer UKSW 102 / 156Download dari : http://ambonmemanggil.blogspot.com
40 20 10 30 60 50 7 80 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
Fakultas Teknik Elektro & Komputer UKSW 103 / 156Download dari : http://ambonmemanggil.blogspot.com
40 20 10 30 60 50 7 80 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
Fakultas Teknik Elektro & Komputer UKSW 104 / 156Download dari : http://ambonmemanggil.blogspot.com
40 20 10 30 60 50 7 80 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
Fakultas Teknik Elektro & Komputer UKSW 105 / 156Download dari : http://ambonmemanggil.blogspot.com
40 20 10 30 60 50 7 80 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
Fakultas Teknik Elektro & Komputer UKSW 106 / 156Download dari : http://ambonmemanggil.blogspot.com
40 20 10 30 60 50 7 80 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
Fakultas Teknik Elektro & Komputer UKSW 107 / 156Download dari : http://ambonmemanggil.blogspot.com
40 20 10 30 60 50 7 80 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
Fakultas Teknik Elektro & Komputer UKSW 108 / 156Download dari : http://ambonmemanggil.blogspot.com
40 20 10 30 60 50 7 80 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
Fakultas Teknik Elektro & Komputer UKSW 109 / 156Download dari : http://ambonmemanggil.blogspot.com
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
40 20 10 30 7 50 60 80 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
Fakultas Teknik Elektro & Komputer UKSW 110 / 156Download dari : http://ambonmemanggil.blogspot.com
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
40 20 10 30 7 50 60 80 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
Fakultas Teknik Elektro & Komputer UKSW 111 / 156Download dari : http://ambonmemanggil.blogspot.com
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
40 20 10 30 7 50 60 80 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
Fakultas Teknik Elektro & Komputer UKSW 112 / 156Download dari : http://ambonmemanggil.blogspot.com
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
40 20 10 30 7 50 60 80 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
Fakultas Teknik Elektro & Komputer UKSW 113 / 156Download dari : http://ambonmemanggil.blogspot.com
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
40 20 10 30 7 50 60 80 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
Fakultas Teknik Elektro & Komputer UKSW 114 / 156Download dari : http://ambonmemanggil.blogspot.com
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
40 20 10 30 7 50 60 80 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
Fakultas Teknik Elektro & Komputer UKSW 115 / 156Download dari : http://ambonmemanggil.blogspot.com
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
40 20 10 30 7 50 60 80 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
Fakultas Teknik Elektro & Komputer UKSW 116 / 156Download dari : http://ambonmemanggil.blogspot.com
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
40 20 10 30 7 50 60 80 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
Fakultas Teknik Elektro & Komputer UKSW 117 / 156Download dari : http://ambonmemanggil.blogspot.com
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
40 20 10 30 7 50 60 80 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
Fakultas Teknik Elektro & Komputer UKSW 118 / 156Download dari : http://ambonmemanggil.blogspot.com
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.5. Swap data[too_small_index] and data[pivot_index]
40 20 10 30 7 50 60 80 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
Fakultas Teknik Elektro & Komputer UKSW 119 / 156Download dari : http://ambonmemanggil.blogspot.com
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.5. Swap data[too_small_index] and data[pivot_index]
7 20 10 30 40 50 60 80 100pivot_index = 4
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
Fakultas Teknik Elektro & Komputer UKSW 120 / 156Download dari : http://ambonmemanggil.blogspot.com
Partition Result
7 20 10 30 40 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
<= data[pivot] > data[pivot]
Fakultas Teknik Elektro & Komputer UKSW 121 / 156Download dari : http://ambonmemanggil.blogspot.com
Idea of Quicksort
• Pilih: pivot, misal X
• Bagi: pecah elements sehingga X berada pada posisi yang tepat
• Urutkan setiap bagian yang lebih kecil dari X dan yang lebih besar dari X
Fakultas Teknik Elektro & Komputer UKSW 122 / 156Download dari : http://ambonmemanggil.blogspot.com
Recursion: Quicksort Sub-arrays
7 20 10 30 40 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
<= data[pivot] > data[pivot]
Fakultas Teknik Elektro & Komputer UKSW 123 / 156Download dari : http://ambonmemanggil.blogspot.com
Quicksort Analysis
• best case saat eksekusi?– Pivot selalu berada ditengah– Array terpecah tepat pada bagian tengah n/2 – Kedalaman tree yang terbentuk saat rekursi
adalah O(log2n)
• waktu eksekusi saat Best case : O(n log2n)
• waktu eksekusi saat worst case :O(N2)– terjadi saat Pivot yang dipilih mrpk angka
terbesar / terkecil
Fakultas Teknik Elektro & Komputer UKSW 124 / 156Download dari : http://ambonmemanggil.blogspot.com
Quicksort: Worst Case
• Asumsi elemen pertama selalu menjadi elemen yang dipilih
• Asumsi array sudah dalam kondisi terurut
2 4 10 12 13 50 57 63 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
Fakultas Teknik Elektro & Komputer UKSW 125 / 156Download dari : http://ambonmemanggil.blogspot.com
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.5. Swap data[too_small_index] and data[pivot_index]
2 4 10 12 13 50 57 63 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
Fakultas Teknik Elektro & Komputer UKSW 126 / 156Download dari : http://ambonmemanggil.blogspot.com
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.5. Swap data[too_small_index] and data[pivot_index]
2 4 10 12 13 50 57 63 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_small_indextoo_big_index
Fakultas Teknik Elektro & Komputer UKSW 127 / 156Download dari : http://ambonmemanggil.blogspot.com
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.5. Swap data[too_small_index] and data[pivot_index]
2 4 10 12 13 50 57 63 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
Fakultas Teknik Elektro & Komputer UKSW 128 / 156Download dari : http://ambonmemanggil.blogspot.com
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.5. Swap data[too_small_index] and data[pivot_index]
2 4 10 12 13 50 57 63 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
Fakultas Teknik Elektro & Komputer UKSW 129 / 156Download dari : http://ambonmemanggil.blogspot.com
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.5. Swap data[too_small_index] and data[pivot_index]
2 4 10 12 13 50 57 63 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
Fakultas Teknik Elektro & Komputer UKSW 130 / 156Download dari : http://ambonmemanggil.blogspot.com
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.5. Swap data[too_small_index] and data[pivot_index]
2 4 10 12 13 50 57 63 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
Fakultas Teknik Elektro & Komputer UKSW 131 / 156Download dari : http://ambonmemanggil.blogspot.com
1. While data[too_big_index] <= data[pivot]++too_big_index
2. While data[too_small_index] > data[pivot]too_small_index
3. If too_big_index < too_small_indexswap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.5. Swap data[too_small_index] and data[pivot_index]
2 4 10 12 13 50 57 63 100pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
> data[pivot]<= data[pivot]
Fakultas Teknik Elektro & Komputer UKSW 132 / 156Download dari : http://ambonmemanggil.blogspot.com
Quicksort Analysis Average Case
• Tantangan yang harus bisa dipecahkan adalah bagaiman memilih pivot yang merupakan nilai tengah (median) dari keseluruhan isi array
• Avarage case pada Quicsort memiliki waktu eksekusi yang sama dengan Best Case : O(n log2n).
Fakultas Teknik Elektro & Komputer UKSW 133 / 156Download dari : http://ambonmemanggil.blogspot.com
Quicksort Analysis
• Best case running time: O(n log2n)
• Worst case running time: O(n2)
• Average case running time: O(n log2n)
Fakultas Teknik Elektro & Komputer UKSW 134 / 156Download dari : http://ambonmemanggil.blogspot.com
Summary of Sorting Algorithms
• in-place, randomized• fastest (good for large inputs)
O(n log n)expected
quick-sort
• sequential data access• fast (good for huge inputs)
O(n log n)merge-sort
O(n2)
O(n2)
Time
insertion-sort
selection-sort
Algorithm Notes
• in-place• slow (good for small inputs)
• in-place• slow (good for small inputs)
Fakultas Teknik Elektro & Komputer UKSW 135 / 156Download dari : http://ambonmemanggil.blogspot.com
Mergesort X Quicksort
• Mergesort– membagi partisi menjadi dua– melakukan merge pada data yang paling kecil– Membutuhkan banyak langkah untuk
melakukan sorting
• Quicksort– sorting tergantung dari nilai pivot yang dipilih– Kinerja akan menurun jika salah memilih pivot
Fakultas Teknik Elektro & Komputer UKSW 136 / 156Download dari : http://ambonmemanggil.blogspot.com
Mergesort X Quicksort
• Mergesort– membutuhkan memori tambahan untuk eksekusi– memberi garansi O(n log n) untuk kondisi worst case
• Quicksort– tidak membutuhkan memori tambahan– tidak memberi garansi O(n log n) untuk kondisi worst case
Fakultas Teknik Elektro & Komputer UKSW 137 / 156Download dari : http://ambonmemanggil.blogspot.com
Quicksort Analysis
• Best case running time: O(n log2n)
• Worst case running time: O(n2)
• Average case running time: O(n log2n)
What can we do to avoid worst case?
Fakultas Teknik Elektro & Komputer UKSW 138 / 156Download dari : http://ambonmemanggil.blogspot.com
Idea of Quicksort
• Pilih: pivot, misal X
• Bagi: pecah elements sehingga X berada pada posisi yang tepat
• Urutkan setiap bagian yang lebih kecil dari X dan yang lebih besar dari X
Fakultas Teknik Elektro & Komputer UKSW 139 / 156Download dari : http://ambonmemanggil.blogspot.com
Memilih Pivot
• Quick sort akan bekerja sama seperti jika PIVOT yang dipilih salah selection sort
• Pilihlah PIVOT yang merupakan nilai tengah dari semua data yang ada di dalam array
Fakultas Teknik Elektro & Komputer UKSW 140 / 156Download dari : http://ambonmemanggil.blogspot.com
Contoh program yang memilih PIVOT adalah bilangan yang berada paling kanan dari array a
Fakultas Teknik Elektro & Komputer UKSW 141 / 156Download dari : http://ambonmemanggil.blogspot.com
Contoh program yang memilih PIVOT adalah adalah bilangan yang merupakan nilai tengah dari semua data yang ada pada elemen array a
Fakultas Teknik Elektro & Komputer UKSW 142 / 156Download dari : http://ambonmemanggil.blogspot.com
Fakultas Teknik Elektro & Komputer UKSW 143 / 156Download dari : http://ambonmemanggil.blogspot.com
Improving Performance of Quicksort
• Untuk array yang hanya memiliki 3 elemen atau kurang, lakukan metode bruteforce :– array yang berukuran 1 : tidak perlu proses
apapun– array yang berukuran 2:
• if(data[pertama] > data[kedua]) maka lakukan swap
– array yang berukuran 3: coba dipikirkan ya :)
Fakultas Teknik Elektro & Komputer UKSW 144 / 156Download dari : http://ambonmemanggil.blogspot.com
Sorting Algorithms
• Selection• Bubble• Insertion• Merge• Quick• Shell
Fakultas Teknik Elektro & Komputer UKSW 145 / 156Download dari : http://ambonmemanggil.blogspot.com
Definition
• This sort algorithm is also called diminishing increment sort. Actually this naming is more meaningful than Shell Sorting Algorithm
• The algorithm sorts the sub-list of the original list based on increment value or sequence number k
• Common Sequence numbers are 5,3,1. There is no proof that these are the best sequence numbers.
• Each sub-list contains every kth element of the original list
Fakultas Teknik Elektro & Komputer UKSW 146 / 156Download dari : http://ambonmemanggil.blogspot.com
Definition
• For example: if k = 5 then sub-lists will be as follows.
• s[0] s[5] s[10] ... This means that there are 5 sub-lists and each contain 1/5 of the original list.
Sublist1: s[0] s[5] s[10] ...Sublist2: s[1] s[6] s[11] ...Sublist3: s[2] s[7] s[12] ...Sublist4: s[3] s[8] s[13] ...Sublist5: s[4] s[9] s[14] ...
• If k = 3 then there will be three sub-lists and so on.
Fakultas Teknik Elektro & Komputer UKSW 147 / 156Download dari : http://ambonmemanggil.blogspot.com
Shell Sort Process
• Create the sub-lists based on increment number (Sequence number)
• Sort the lists
• Combine the lists
Let’s see this algorithm in action
Fakultas Teknik Elektro & Komputer UKSW 148 / 156Download dari : http://ambonmemanggil.blogspot.com
Shell Sort Process
• Let’s sort the following list given the sequence numbers are 5, 3, 1
30 62 53 42 17 97 91 38
Fakultas Teknik Elektro & Komputer UKSW 149 / 156Download dari : http://ambonmemanggil.blogspot.com
Shell Sort Process k=5
3030 62 53 42 17 97 91 38 62 53 42 17 97 91 38
30 62 53 42 17 97 91 38[0] [1] [2] [7][3] [4] [5] [6]
S[3]S[4]
S[0] S[5]S[1] S[6]S[2] S[7]
Step 1: Create the sub list k = 5
Step 2 3: Sort the sub list & combine
S[0] < S[5] This is OK
S[1] < S[6] This is OK
S[2] > S[7] This is not OK. Swap them
30 62 53 42 17 97 91 38[0] [1] [2] [7][3] [4] [5] [6]
5338
Fakultas Teknik Elektro & Komputer UKSW 150 / 156Download dari : http://ambonmemanggil.blogspot.com
Shell Sort Process k=3
3030 62 53 42 17 97 91 38 62 53 42 17 97 91 38
S[0] S[3] S[6]
S[1] S[4] S[7]
S[2] S[5]
30 62 38 42 17 97 91 53[0] [1] [2] [7][3] [4] [5] [6]
Step 1: Create the sub list k = 3
Step 2 3: Sort the sub list & combine
S[0] S[3] S[6] 30, 42, 91 OKS[1] S[4] S[7] 62, 17, 53 not OKSORT them 17, 53, 62
30 62 38 42 17 97 91 53[0] [1] [2] [7][3] [4] [5] [6]
17 53 62
S[2] S[5] 38, 97 OK
Fakultas Teknik Elektro & Komputer UKSW 151 / 156Download dari : http://ambonmemanggil.blogspot.com
Shell Sort Process k=1
3030 62 53 42 17 97 91 38 62 53 42 17 97 91 38S[0] S[1] S[2] S[3] S[4] S[5] S[6] S[7]
30 17 38 42 53 97 91 62[0] [1] [2] [7][3] [4] [5] [6]
Step 1: Create the sub list k =1
Step 2 3: Sort the sub list & combine
30 17 38 42 53 97 91 62[0] [1] [2] [7][3] [4] [5] [6]
17 9762Sorting will be like insertion sort 30
DONE
Fakultas Teknik Elektro & Komputer UKSW 152 / 156Download dari : http://ambonmemanggil.blogspot.com
Shellsort Algorithmtemplate <class T>void Shellsort( T A[], int N){ for(int Gap = N/2; Gap > 0; Gap = (Gap ==2) ? (int) (Gap
/2.2)) for( i = Gap; i < N; i++){ T tmp = A[i]; int j = i; for ( ; j>= Gap && tmp < A [ j–Gap ] ; j -= Gap) A[ j ] = A [ j – Gap ]; A[ j ] = tmp; }}
Fakultas Teknik Elektro & Komputer UKSW 153 / 156Download dari : http://ambonmemanggil.blogspot.com
Shellsort Analysis
• The running time of Shellsort depends heavily on the choice of increment sequences.
• Shell suggested starting gap at N/2 and halving it until reaches 1.
• Shellsort despite of three nested loop, represents a substantial improvement over the insertion sort
Fakultas Teknik Elektro & Komputer UKSW 154 / 156Download dari : http://ambonmemanggil.blogspot.com
Running time (millisecond) of the insertion and Shellsort
N insertion Shellsort1000 122 112000 483 264000 1936 618000 7950 15316000 32560 358
Ref: Mark Allan Wiess(Florida International University)
Fakultas Teknik Elektro & Komputer UKSW 155 / 156Download dari : http://ambonmemanggil.blogspot.com
Shellsort Analysis
• When Shell’s increment are used, the worst case can be O(N2).
• When N is an exact power of two one can prove that the average running time is O(N3/2).
• A minor change to the increment sequence can improve the quadratic worst case from occurring.and it becomes even, then we can add one to make it odd. We can then prove that the worst case is not quadratic but only O(N3/2).
Ref: Mark Allan Wiess
Fakultas Teknik Elektro & Komputer UKSW 156 / 156Download dari : http://ambonmemanggil.blogspot.com
Shellsort Analysis
• Another alternative that performs well in practice but has no theoretical basis is to divide by 2.2.
• This brings the average running time to below O(N5/4), and (perhaps to O(N7/6).