Jeni Slides Intro2 Bab06 Algorithm A Sorting

Algoritma sorting Pengenalan Pemrograman 2

Versi 2.0

Topik 

Sorting



Insertion Sort



Selection Sort



Merge Sort ◦ Paradigma Divide-and-Conquer



Quicksort ◦ Paradigma Divide-and-Conquer

Sorting



Mengatur elemen berdasar urutan tertentu



Digunakan secara luas dalam aplikasi



Beberapa algoritma sorting telah dibuat karena proses tersebut sangat mendasar dan sering digunakan

Insertion Sort Salah satu algoritma paling sederhana  Cukup intuitif dan prosesnya mirip dengan mengurutkan kartu ◦ Tujuan: mengurutkan kartu dari paling kecil hingga terbesar ◦ Terdapat: kartu, meja 1, meja 2 ◦ Awal: Kartu acak diletakkan pada meja 1 ◦ Teknik: Kartu berurutan diletakkan pada meja 2 ◦ Ambil kartu pertama dari meja 1, bandingkan dengan tabel 2 dan tempatkan sesuai posisi urutan di meja 2 ◦ Ulangi hingga seluruh kartu terletak pada meja 2 

Insertion Sort: Algoritma 

Bagi elemen data yang akan diurutkan menjadi dua ◦ Bagian yang belum diurutkan ◦ Bagian yang telah terurutkan



Ulangi langkah tersebut hingga tidak ada elemen tersisa dalam array ◦ Elemen pertama dipilih dari bagian yang belum diurutkan ◦ Tempatkan elemen terpilih sesuai urutan pada array

Insertion Sort: Algoritma 1 2 3 4 5 6 7 8 9 10 11 12 13

void insertionSort(Object array[], int startIdx, int endIdx) { for (int i = startIdx; i < endIdx; i++) { int k = i; for (int j = i + 1; j < endIdx; j++) { if (((Comparable) array[k]).compareTo( array[j])>0) { k = j; } } swap(array[i], array[k]); } }

Insertion Sort: Contoh

Selection Sort 

Algoritma sorting yang lainnya ◦ Intuitif dan mudah diimplementasikan



Juga mirip dengan cara lain dalam pengurutan kartu ◦ Tujuan: mengurutkan kartu secara ascending ◦ Diberikan: kartu, meja ◦ Awal: Kartu disebar secara acak pada tabel ◦ Periksa nilai, kemudian pilih kartu dengan nilai terendah ◦ Tukarkan posisi kartu ini dengan kartu pertama pada meja ◦ Cari kartu dengan nilai terendah dari sisa kartu yang ada ◦ Tukarkan kartu terpilih dengan kartu pada posisi kedua ◦ Ulangi proses hingga kartu kedua sebelum terakhir pada meja dibandingkan dan ditukar dengan kartu terakhir

Selection Sort: Algoritma

 Pilih

elemen dengan nilai terendah

 Tukarkan

elemen terpilih dengan elemen pada posisi ke - i

◦ i dimulai dari 1 hingga n ◦ Dimana n adalah total elemen yang ada dikurangi 1

Selection Sort: Algoritma 1 2 3 4 5 6 7 8 9 10 11 12 13 14

void selectionSort(Object array[], int startIdx, int endIdx) { int min; for (int i = startIdx; i < endIdx; i++) { min = i; for (int j = i + 1; j < endIdx; j++) { if (((Comparable) array[min]).compareTo( array[j])>0) { min = j; } } swap(array[min], array[i]); } }

Selection Sort: Contoh

Merge Sort: Paradigma Divide-and-Conquer 

Menggunakan rekursi dalam penyelesaiannya : ◦ Permasalahan awal dipilah menjadi sub-masalah ◦ Solusi atas sub-masalah menuntun menuju permasalahan utama



3 Langkah: ◦ Divide

 Membagi permasalahan menjadi submasalah

◦ Conquer

Menyelesaikan sub-masalah secara rekursif Jika sub-masalah cukup sederhana dan kecil, selesaikan secara langsung

◦ Combine

Kombinasikan solusi dari sub-masalah yang ada, hingga mencapai permasalahan utama

Merge Sort: Algoritma 

Menggunakan pendekatan divide-and-conquer ◦ Divide

 Membagi elemen data menjadi dua bagian ◦ Conquer

Selesaikan tiap bagian secara rekursif dengan memanggil method mergeSort.

◦ Combine

Kombinasikan dua bagian secara rekursif untuk mendapatkan urutan yang diharapkan



Rekursi selesai pada saat sisa dari sebagian elemen yang akan diurutkan tepat tersisa satu ◦ Telah terurutkan

Merge Sort: Algoritma 1 2 3 4 5 6 7 8 9 10

void mergeSort(Object array[], int startIdx, int endIdx) { if (array.length != 1) { Divide the array into two halves, leftArr and rightArr mergeSort(leftArr, startIdx, midIdx); mergeSort(rightArr, midIdx+1, endIdx); combine(leftArr, rightArr); } }

Merge Sort: Contoh

Quicksort: Algoritma 

Ditemukan oleh C.A.R. Hoare



Berdasar pada paradigma divide-and-conquer ◦ Divide

 Bagi array menjadi dua subarray A[p...q-1] dan A[q+1...r] dimana A[p...q-1] adalah kurang dari atau sama dengan A[q] dan elemen pada A[q+1...r] adalah lebih dari atau sama dengan A[q] A[q] disebut sebagai pivot Perhitungan q adalah bagian dari prosedur pemisahan ◦ Conquer

Urutkan subarray tersebut dengan memanggil method quickSort secara rekursif

◦ Tak perlu melakukan proses “Combine”

Subarrays telah terurutkan

Quicksort: Algoritma

1 2 3 4 5 6 7 8 9 10

void quickSort(Object array[], int leftIdx, int rightIdx) { int pivotIdx; /* Termination condition! */ if (rightIdx > leftIdx) { pivotIdx = partition(array, leftIdx, rightIdx); quickSort(array, leftIdx, pivotIdx-1); quickSort(array, pivotIdx+1, rightIdx); } }

Quicksort: Contoh

Quicksort: Contoh

Kesimpulan  Teknik

Sorting sederhana

◦ Insertion Sort ◦ Selection Sort  Paradigma

◦ Merge Sort ◦ Quicksort

Divide-and-Conquer