Sorting Algorithms

Sorting Algorithms

Beberapa Algoritma Sorting

1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort

Bubble Sort: pseudocode

BUBBLESORT(A)

1              for i←1 to length[A]

2                              do for j←length[A] downto i+1

3                                              do if A[j] < A[j-1]

4                                                              then exchange A[j] ↔ A[j-1]

Contoh Algoritma: BUBBLE SORT

banyaknya data:  n

                Data diurutkan/disorting dari yang bernilai besar

Proses

step 1     :             Periksalah nilai dua elemen mulai dari urutan ke-n                           sampai urutan ke-1. Jika nilai kiri<kanan, tukarkan                              kedua data itu.

step 2     :             Periksalah nilai dua elemen mulai dari urutan ke-n                           sampai urutan ke-2. Jika nilai kiri<kanan, tukarkan                              kedua data itu.

step n-1    :          Periksalah nilai dua elemen mulai dari urutan ke-n                           sampai urutan ke-n-1. Jika nilai kiri<kanan, tukarkan                              kedua data itu.

Bubble Sort: tahap demi tahap

Awal    7                4              5              8              10

Bubble Sort: tahap demi tahap

Awal    7                4              5              8              10

Step-   7                4              5              8              10

Bubble Sort: tahap demi tahap

Awal     7               4              5              8              10

Step-1   7             4              5              10           8

Bubble Sort: tahap demi tahap

Awal     7               4              5              8              10

Step-1     10         7              4             5              8

Step-2   10           7              8             4              5

Beberapa Algoritma Sorting

1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort

Selection Sort: Pseudocode

SELECTIONSORT(A)

        1      for i← 1 to length[A]-1

2              min = i;

3              do for j ← i+1 to length[A]

4                   do if  A[j] < A[min]

5                       min = j;                  

6              exchange A[min] ↔ A[i]

7         Prinsip kerja:

8         Dari elemen sebanyak n,

9         Carilah elemen terkecil dari array A, dan swap-lah elemen terkecil tersebut dengan elemen pertama (A[1] ).

10     Carilah elemen terkecil kedua dari array A, dan swap-lah elemen tersebut dengan elemen kedua (A[2])

11     Ulangi sampai  n-1 elemen pertama dari array A

Selection Sort: contoh

Beberapa Algoritma Sorting

1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort

Insertion Sort: pseudocode

INSERTION-SORT(A)

1       for j←2 to length[A]

2              do key←A[j]

3                                              Insert A[j] ke sekuens yang sudah disorting A[1…j-1]

4                                              i← j-1

5                                              while i>0  and A[i] > key

6                                                              do  A[i+1] ←A[i]

7                                                                              i ← i -1

8                                              A[i+1] ←key

Insertion Sort: contoh

Quiz

Diketahui deretan data sbb.

                                                80  84 100  24  79  85  91  65  17   3   1   21                

1. Urutkan data tsb. memakai Selection Sort, agar elemen terkecil berada paling depan (urutan pertama), semakin ke belakang semakin besar
2. Urutkan data tsb. memakai Selection Sort, agar elemen terbesar berada paling depan (urutan pertama), semakin ke belakang semakin kecil
3. Urutkan data tsb. memakai Insertion Sort, agar elemen terkecil berada paling depan (urutan pertama), semakin ke belakang semakin besar
4. Urutkan data tsb. memakai Insertion Sort, agar elemen terbesar berada paling depan (urutan pertama), semakin ke belakang semakin kecil

Beberapa Algoritma Sorting

1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort

Prinsip Kerja Quick Sort

•          Divide

–        Partisilah array A[p…r] ke dalam dua buah subarray A[p…q-1] dan A[q+1…r] sedemikian hingga

•          tiap elemen pada A[p…q-1] senantiasa lebih kecil atau sama dengan A[q]  DAN

•          tiap elemen pada A[q+1…r] senantiasa sama atau lebih besar dari A[q]

–        Hitunglah q

•          Conquer

–        Urutkan (sorting-lah) A[p…q-1] dan A[q+1…r] secara rekursif

•          Combine

–        Kedua subarray telah diurutkan pada posisi masing-masing, sehingga tidak diperlukan upaya khusus untuk mengkombinasikan mereka. A[p…r]  telah ter-sorting

Quick Sort: pseudocode

Cara Kerja Quick Sort

Quick Sort: Contoh

Quick Sort: Contoh

Quick Sort: Contoh

Quick Sort: Contoh

Quick Sort: Contoh

Quick Sort: Contoh

Quick Sort: Contoh

Quick Sort: Contoh

4 region dalam procedure PARTITION

Best Case & Worst Case

Quiz

Diketahui deretan data sbb.

                                                80  84 100  24  79  85  91  65  17   3   1   21                

1. Urutkan data tsb. memakai Merge sort, agar elemen terkecil berada paling depan (urutan pertama), semakin ke belakang semakin besar
2. Urutkan data tsb. memakai Merge Sort, agar elemen terbesar berada paling depan (urutan pertama), semakin ke belakang semakin kecil
3. Urutkan data tsb. memakai Quick Sort, agar elemen terkecil berada paling depan (urutan pertama), semakin ke belakang semakin besar
4. Urutkan data tsb. memakai Quick Sort, agar elemen terbesar berada paling depan (urutan pertama), semakin ke belakang semakin kecil

Randomized Quicksort

RANDOMIZED-QUICKSORT (A, p,r)

1              If p<r

2                              then q←RANDOMIZED-PARTITION (A,p,r)

3                                              RANDOMIZED-QUICKSORT(A,p,q-1)

4                                             RANDOMIZED-QUICKSORT(A,q+1,r)

RANDOMIZED-PARTITION(A, p,r)

1     i←RANDOM(p,r)

2     exchange A[r] ↔A[i]              

3     return PARTITION (A,p,r)