Algoritma sorting

Tenia Wahyuningrum, SKom., MT

Topik Sorting

Selection Sort

Straight insertion Sort

Merge SortParadigma Divide-and-Conquer

QuicksortParadigma Divide-and-Conquer

Algoritma Pengurutan / Sorting

Algoritma pengurutan adalah algoritma untuk meletakkan kumpulan elemen data ke dlm urutan tertentu, berdasarkan satu atau beberapa kunci ke dalam tiap-tiap elemen

• Mengatur elemen berdasar urutan tertentu

• Digunakan secara luas dalam aplikasi

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

Memudahkan dalam pencarian & memudahkan dalam melihat data

Contoh : Kamus, buku telepon, kartu berobat, kartu perpustakaan, dst

Mengapa sorting?

Selection Sort Algoritma sorting yang lainnya

Intuitif dan mudah diimplementasikan

Juga mirip dengan cara lain dalam pengurutan kartuTujuan: mengurutkan kartu secara ascendingDiberikan: kartu, mejaAwal: Kartu disebar secara acak pada tabelPeriksa nilai, kemudian pilih kartu dengan nilai terendahTukarkan posisi kartu ini dengan kartu pertama pada mejaCari kartu dengan nilai terendah dari sisa kartu yang adaTukarkan kartu terpilih dengan kartu pada posisi keduaUlangi 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 - ii dimulai dari 1 hingga nDimana n adalah total elemen yang ada dikurangi 1

Selection Sort: Algoritma1 void selectionSort(Object array[], int startIdx, 2 int endIdx) {3 int min;4 for (int i = startIdx; i < endIdx; i++) {5 min = i;6 for (int j = i + 1; j < endIdx; j++) {7 if (((Comparable) array[min]).compareTo(8 array[j])>0) {9 min = j;10 }11 } 12 swap(array[min], array[i]);13 }14 }

Selection Sort: Contoh

Straight Insertion Sort

Data di cek satu persatu mulai dari yang kedua sampai dengan yang terakhir, apabila ditemukan data yang lebih kecil, daripada data sebelumnya, maka data tersebut disisipkan pada posisi yang sesuai.

i=2,N

x=data[i]data[0]=x

j=i-1

x<data[j]

data[j+1]=data[j]

dec(j)

data[j+1]=x

y

t

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

DivideMembagi elemen data menjadi dua bagian

ConquerSelesaikan 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 void mergeSort(Object array[], int startIdx, 2 int endIdx) {3 if (array.length != 1) {4 Divide the array into two halves, 5 leftArr and rightArr6 mergeSort(leftArr, startIdx, midIdx);7 mergeSort(rightArr, midIdx+1, endIdx);8 combine(leftArr, rightArr);9 }10 }

Merge Sort: Contoh

Quicksort: Algoritma Ditemukan oleh C.A.R. Hoare

Berdasar pada paradigma divide-and-conquerDivide

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 pivotPerhitungan q adalah bagian dari prosedur pemisahan

ConquerUrutkan subarray tersebut dengan memanggil method

quickSort secara rekursifTak perlu melakukan proses “Combine”

Subarrays telah terurutkan

Quicksort: Algoritma

1 void quickSort(Object array[], int leftIdx, 2 int rightIdx) {3 int pivotIdx;4 /* Termination condition! */5 if (rightIdx > leftIdx) {6 pivotIdx = partition(array, leftIdx, rightIdx);

7 quickSort(array, leftIdx, pivotIdx-1);8 quickSort(array, pivotIdx+1, rightIdx);9 }10 }

Quicksort: Contoh

Quicksort: Contoh

Kesimpulan

Teknik Sorting sederhana Insertion Sort Selection Sort

Paradigma Divide-and-Conquer Merge Sort Quicksort