Sorting 1

Algoritma Sorting 1. 2. 3. 4. 5. Bubble Selection Insertion Merge Quick Fakultas Teknik Elektro & Komputer UKSW 1 / 156 Download 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 1 77 2 42 3 35 4 12 5 101 6 5 Fakultas Teknik Elektro & Komputer UKSW 2 / 156 Download 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 1 2 3 35 4 12 5 101 6 5 Swap77 42 42 77 Fakultas Teknik Elektro & Komputer UKSW 3 / 156 Download 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 1 42 2 3 4 12 5 101 6 5 35 77 Swap77 35 Fakultas Teknik Elektro & Komputer UKSW 4 / 156 Download 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 1 42 2 35 3 4 5 101 6 5 12 77 77 Swap12 Fakultas Teknik Elektro & Komputer UKSW 5 / 156 Download 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 1 42 2 35 3 12 4 77 5 101 6 5 Tidak butuh swap Fakultas Teknik Elektro & Komputer UKSW 6 / 156 Download 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 1 42 2 35 3 12 4 77 5 6 5 101Swap101 5 Fakultas Teknik Elektro & Komputer UKSW 7 / 156 Download 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 1 42 2 35 3 12 4 77 5 5 6 101 Nilai terbesar berada di kanan Fakultas Teknik Elektro & Komputer UKSW 8 / 156 Download dari : http://ambonmemanggil.blogspot.com Bubble Sort index = 1 last_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 + 1 End of repeat Fakultas Teknik Elektro & Komputer UKSW 9 / 156 Download 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 1 42 2 35 3 12 4 77 5 5 6 101 Fakultas Teknik Elektro & Komputer UKSW 10 / 156 Download dari : http://ambonmemanggil.blogspot.com Bubble Sort 1 42 1 35 N-1 1 12 1 12 1 5 2 35 2 12 2 35 2 5 2 12 3 12 3 42 3 5 3 35 3 35 4 77 4 5 4 42 4 42 4 42 5 5 5 77 5 77 5 77 5 77 6 101 6 101 6 101 6 101 6 101 Fakultas Teknik Elektro & Komputer UKSW 11 / 156 Download dari : http://ambonmemanggil.blogspot.com Mengurangi Jumlah Perbdgn 1 77 1 42 1 35 1 12 1 12 2 42 2 35 2 12 2 35 2 5 3 35 3 12 3 42 3 5 3 35 4 12 4 77 4 5 4 42 4 42 5 101 5 5 5 77 5 77 5 77 6 5 6 101 6 101 6 101 6 101 Fakultas Teknik Elektro & Komputer UKSW 12 / 156 Download 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 1 12 2 35 3 5 4 42 5 77 6 101 Fakultas Teknik Elektro & Komputer UKSW 13 / 156 Download 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; } } Inner loop Fakultas Teknik Elektro & Komputer UKSW 14 / 156 Download dari : http://ambonmemanggil.blogspot.com Outer loop 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 1 5 2 12 3 35 4 42 5 77 6 101 Fakultas Teknik Elektro & Komputer UKSW 15 / 156 Download dari : http://ambonmemanggil.blogspot.com Deteksi Menggunakan 'Flag' • Proses deteksi data yang terurut bisa menggunakan Flag • Misal : – Flag = 0 – Flag = 1 : Jika tidak terjadi swap : Jika terjadi swap • Dari iterasi pertama, jika Flag=0 maka dipastikan data sudah terurut Fakultas Teknik Elektro & Komputer UKSW 16 / 156 Download 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 Inner loop data[i] = data[i+1]; data[i+1] = temp; flag = 1; } } if (flag==0) return; } } Fakultas Teknik Elektro & Komputer UKSW 17 / 156 Download dari : http://ambonmemanggil.blogspot.com Outer loop temp = data[i]; 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 18 / 156 Download 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 19 / 156 Download dari : http://ambonmemanggil.blogspot.com Sorting Algorithms 1. 2. 3. 4. 5. Bubble Selection Insertion Merge Quick Fakultas Teknik Elektro & Komputer UKSW 20 / 156 Download dari : http://ambonmemanggil.blogspot.com Selection Sort (Salah satu algoritma sorting sederhana) 3 10 4 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 Fakultas Teknik Elektro & Komputer UKSW 21 / 156 Download dari : http://ambonmemanggil.blogspot.com 3 3 10 5 4 4 6 6 8 8 9 9 7 7 2 2 1 1 5 10 Cari data terbesar berikutnya, angka 9 Tukarkan dengan data yang berada pada posisi terakhir ke-2, angka 1 3 3 5 5 4 4 6 6 8 8 9 1 7 7 2 2 1 9 10 10 Fakultas Teknik Elektro & Komputer UKSW 22 / 156 Download dari : http://ambonmemanggil.blogspot.com 3 5 4 6 8 1 7 2 9 10 Dua data terakhir, 9 dan 10, tidak akan diubahubah lagi karena sudah menempati posisi yang sesuai. Lakukan langkah selanjutnya seperti yang telah dicontohkan Fakultas Teknik Elektro & Komputer UKSW 23 / 156 Download dari : http://ambonmemanggil.blogspot.com 3 3 3 3 3 5 5 5 5 5 4 4 4 4 4 6 6 6 6 1 8 2 2 2 2 1 1 1 1 6 7 7 7 7 7 2 8 8 8 8 9 9 9 9 9 10 10 10 10 10 Fakultas Teknik Elektro & Komputer UKSW 24 / 156 Download dari : http://ambonmemanggil.blogspot.com 3 3 3 3 3 1 1 5 2 2 2 2 2 2 4 4 4 1 1 3 3 1 1 1 4 4 4 4 2 5 5 5 5 5 5 6 6 6 6 6 6 6 7 7 7 7 7 7 7 8 8 8 8 8 8 8 9 9 9 9 9 9 9 10 10 10 10 10 10 10 Fakultas Teknik Elektro & Komputer UKSW 25 / 156 Download 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 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 42 / 156 Download 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 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 6 67 33 42 Fakultas Teknik Elektro & Komputer UKSW 44 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 6 67 33 42 6 67 33 42 Fakultas Teknik Elektro & Komputer UKSW 45 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 45 14 6 67 33 42 6 67 33 42 Fakultas Teknik Elektro & Komputer UKSW 46 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 6 67 33 42 6 67 33 42 Fakultas Teknik Elektro & Komputer UKSW 47 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 6 67 33 42 6 67 33 42 Merge Fakultas Teknik Elektro & Komputer UKSW 48 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 Merge 23 45 14 6 67 33 42 6 67 33 42 Fakultas Teknik Elektro & Komputer UKSW 49 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 6 67 33 42 6 67 33 42 23 98 Merge Fakultas Teknik Elektro & Komputer UKSW 50 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 23 98 Fakultas Teknik Elektro & Komputer UKSW 51 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 23 98 Merge Fakultas Teknik Elektro & Komputer UKSW 52 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 Merge 14 6 67 33 42 6 67 33 42 23 98 Fakultas Teknik Elektro & Komputer UKSW 53 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 23 98 14 45 Merge Fakultas Teknik Elektro & Komputer UKSW 54 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 23 98 14 45 Merge Fakultas Teknik Elektro & Komputer UKSW 55 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 23 98 14 14 45 Merge Fakultas Teknik Elektro & Komputer UKSW 56 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 23 98 14 23 14 45 Merge Fakultas Teknik Elektro & Komputer UKSW 57 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 23 98 14 45 14 23 45 Merge Fakultas Teknik Elektro & Komputer UKSW 58 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 23 98 14 45 14 23 45 98 Merge Fakultas Teknik Elektro & Komputer UKSW 59 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 33 42 23 98 14 45 14 23 45 98 Fakultas Teknik Elektro & Komputer UKSW 60 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 23 98 14 45 14 23 45 98 Fakultas Teknik Elektro & Komputer UKSW 61 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 23 98 14 45 Merge 14 23 45 98 Fakultas Teknik Elektro & Komputer UKSW 62 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 6 Merge 67 33 42 23 98 14 45 14 23 45 98 Fakultas Teknik Elektro & Komputer UKSW 63 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 23 98 14 45 6 67 Merge 14 23 45 98 Fakultas Teknik Elektro & Komputer UKSW 64 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 33 42 23 98 14 45 6 67 14 23 45 98 Fakultas Teknik Elektro & Komputer UKSW 65 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 33 42 23 98 14 45 6 67 Merge 14 23 45 98 Fakultas Teknik Elektro & Komputer UKSW 66 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 33 33 Merge 42 23 98 14 45 6 67 14 23 45 98 Fakultas Teknik Elektro & Komputer UKSW 67 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 33 42 23 98 14 45 6 67 33 42 Merge 14 23 45 98 Fakultas Teknik Elektro & Komputer UKSW 68 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 33 42 23 98 14 45 6 67 33 42 14 23 45 98 Merge Fakultas Teknik Elektro & Komputer UKSW 69 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 33 42 23 98 14 45 6 67 6 33 42 14 23 45 98 Merge Fakultas Teknik Elektro & Komputer UKSW 70 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 33 42 23 98 14 45 6 67 6 33 33 42 14 23 45 98 Merge Fakultas Teknik Elektro & Komputer UKSW 71 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 33 42 23 98 14 45 6 67 6 33 42 33 42 14 23 45 98 Merge Fakultas Teknik Elektro & Komputer UKSW 72 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 33 42 23 98 14 45 6 67 33 42 14 23 45 98 6 33 42 67 Merge Fakultas Teknik Elektro & Komputer UKSW 73 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 33 42 23 98 14 45 6 67 33 42 14 23 45 98 6 33 42 67 Merge Fakultas Teknik Elektro & Komputer UKSW 74 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 33 42 23 98 14 45 6 67 33 42 14 23 45 98 6 Merge Fakultas Teknik Elektro & Komputer UKSW 75 / 156 Download dari : http://ambonmemanggil.blogspot.com 6 33 42 67 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 33 42 23 98 14 45 6 67 33 42 14 23 45 98 6 14 Merge Fakultas Teknik Elektro & Komputer UKSW 76 / 156 Download dari : http://ambonmemanggil.blogspot.com 6 33 42 67 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 33 42 23 98 14 45 6 67 33 42 14 23 45 98 6 14 23 Merge Fakultas Teknik Elektro & Komputer UKSW 77 / 156 Download dari : http://ambonmemanggil.blogspot.com 6 33 42 67 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 33 42 23 98 14 45 6 67 33 42 14 23 45 98 6 14 23 33 Merge Fakultas Teknik Elektro & Komputer UKSW 78 / 156 Download dari : http://ambonmemanggil.blogspot.com 6 33 42 67 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 33 42 23 98 14 45 6 67 33 42 14 23 45 98 6 14 23 33 42 Merge Fakultas Teknik Elektro & Komputer UKSW 79 / 156 Download dari : http://ambonmemanggil.blogspot.com 6 33 42 67 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 33 42 23 98 14 45 6 67 33 42 14 23 45 98 6 33 42 67 6 14 23 33 42 45 Merge Fakultas Teknik Elektro & Komputer UKSW 80 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 33 42 23 98 14 45 6 67 33 42 14 23 45 98 6 33 42 67 6 14 23 33 42 45 67 Merge Fakultas Teknik Elektro & Komputer UKSW 81 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 33 42 23 98 14 45 6 67 33 42 14 23 45 98 6 33 42 67 6 14 23 33 42 45 67 98 Merge Fakultas Teknik Elektro & Komputer UKSW 82 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 98 23 45 14 98 23 98 23 45 14 45 14 6 67 33 42 6 67 33 42 6 67 6 67 33 42 33 42 23 98 14 45 6 67 33 42 14 23 45 98 6 33 42 67 6 14 23 33 42 45 67 98 Fakultas Teknik Elektro & Komputer UKSW 83 / 156 Download dari : http://ambonmemanggil.blogspot.com 98 23 45 14 6 67 33 42 6 14 23 33 42 45 67 98 Fakultas Teknik Elektro & Komputer UKSW 84 / 156 Download 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 85 / 156 Download dari : http://ambonmemanggil.blogspot.com Sorting Algorithms 1. 2. 3. 4. 5. Bubble Selection Insertion Merge Quick Fakultas Teknik Elektro & Komputer UKSW 86 / 156 Download 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 87 / 156 Download 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 88 / 156 Download dari : http://ambonmemanggil.blogspot.com Idea of Quicksort • Pilih: pivot, misal X • Bagi: pecah elements sehingga X berada pada posisi yang tepat • Fakultas Teknik Elektro & Komputer UKSW 89 / 156 Download dari : http://ambonmemanggil.blogspot.com Urutkan setiap bagian yang lebih kecil dari X dan yang lebih besar dari X 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 90 / 156 Download 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 91 / 156 Download dari : http://ambonmemanggil.blogspot.com Idea of Quicksort • Pilih: pivot, misal X • Bagi: pecah elements sehingga X berada pada posisi yang tepat • Fakultas Teknik Elektro & Komputer UKSW 92 / 156 Download dari : http://ambonmemanggil.blogspot.com Urutkan setiap bagian yang lebih kecil dari X dan yang lebih besar dari X 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 93 / 156 Download dari : http://ambonmemanggil.blogspot.com Idea of Quicksort • Pilih: pivot, misal X • Bagi: pecah elements sehingga X berada pada posisi yang tepat • Fakultas Teknik Elektro & Komputer UKSW 94 / 156 Download dari : http://ambonmemanggil.blogspot.com Urutkan setiap bagian yang lebih kecil dari X dan yang lebih besar dari X pivot_index = 0 40 20 10 80 60 50 7 30 100 [0]    [1]   [2]    [3]   [4]   [5]    [6]   [7]   [8] too_big_index Fakultas Teknik Elektro & Komputer UKSW 95 / 156 Download dari : http://ambonmemanggil.blogspot.com too_small_index 1. While data[too_big_index]