Sorting (1)

Pertemuan 4

SortingTujuan : memahami proses tracing algoritma

pengurutan.Beberapa jenis algoritma sorting :

Bubble sortSelection sortInsertion sort

Ada sebuah tim bola yang memiliki ketinggian yang beragam

Jika diminta untuk urut dari yang paling kecil di kiri dan yang paling tinggi di kanan

Maka manusia bisa langsung melihat secara keseluruhan siapa yang paling tinggi untuk diletakkan di kanan

kita tidak perlu membandingkan maupun mengukur satu per satu secara detail

Tapi program komputer tidak bisa melakukan seperti yang dilakukan manusia

Program komputer hanya dapat membandingkan 2 pemain dalam satu waktu

3 algoritma pada bab ini melibatkan 2 step. Dieksekusi dan diulang terus hingga terurut dengan benar

1. bandingkan dua item2. tukar posisi dua item, atau copy posisi satu

item

Algoritma dasar sorting

- Bubble sort termasuk sorting yang lambat, tapi paling simple dalam konsep algoritma sorting

- Dan paling bagus untuk mulai mempelajari teknik algoritma sorting

- Rules yang bisa dikuti- 1. bandingkan 2 pemain- 2. jika pemain kiri lebih tinggi dari di kanan, tukar

- 3. geser ke posisi di sebelah kanan- 4. jika pemain tertinggi telah sampai di sebelah kanan, mulai lagi dari kiri

Bubble sort

Bubble Sortvoid bubble ( int X [ ], int n ){

int hold, j, pass;for ( pass = 0; pass < n-1; pass++)

for ( j = 0; j < n-pass-1; j++)if ( X[j] > X[j+1] ){

hold = X[j];X[j] = X[j+1];X[j+1] = hold;

}}

Jumlah langkah dalam bubble sort = triangle(n-1)

Misal n = 6, maka jumlah langkah = triangle(5) 5+4+3+2+1 = 15

Atau n*(n-1) / 2 6(5) /2 = 15

Dalam banyak kasus, insertsion sort merupakan algoritma sorting paling baik dalam dasar sorting

kecepatan insertion sort sekitar dua kali kecepatan bubble sort

Dalam situasi normal, lebih cepat dari selection sort

Dan dalam beberapa kondisi digunakan dalam final stage advance sorting seperti quick sort

Insertion sort

Insertion Sortvoid insertion ( int X [ ], int n ){

int i, j, y;for ( j = 1; j < n; j++){

y = X[j];for ( i = j-1; i >= 0 && y < X[i]; i--){

X[i+1] = X[i];}X[i+1] = y;

}}