Objectives Struktur Data & Algoritme (Data Structures & Algorithms)
Memahami beberapa algoritme sorting dan dapat menganalisa kompleksitas-nya
Sorting
Denny (
[email protected]) Suryana Setiawan (
[email protected]) Fakultas Ilmu Komputer Universitas Indonesia Semester Genap - 2004/2005 Version 2.0 - Internal Use Only
Sort
Outline
SDA/SORT/V2.0/2
Beberapa algoritme untuk melakukan sorting Idea Example Running time for each algorithm
Sorting = pengurutan Sorted = terurut menurut kaidah tertentu Data pada umumnya disajikan dalam bentuk sorted. Why? Bayangkan bagaimana mencari telepon seorang teman dalam buku yang disimpan tidak terurut.
SDA/SORT/V2.0/3
Bubble Sort: idea
SDA/SORT/V2.0/4
Bubble Sort
bubble = busa/udara dalam air, so? Busa dalam air akan naik ke atas. Why? How? • Ketika busa naik ke atas, maka air yang di atasnya akan turun memenuhi tempat bekas busa tersebut.
1
40
2
1
43
3
65
0
-1
58
3
42
4
2
2
1
40
3
43
0
-1 58
3
42
4
65
3
1
2
3
40
0
-1
43
3
42
4
58 65
4
1
2
3
0
-1
40
3
42
4
43 58 65
SDA/SORT/V2.0/5
Perhatikan bahwa pada setiap iterasi, dapat dipastikan satu elemen akan menempati tempat yang benar SDA/SORT/V2.0/6
1
Bubble Sort
Bubble Sort: algorithms
5
1
2
0
-1
3
3
40
4
6
1
0
-1
2
3
3
4
40 42 43 58 65
7
0
-1
1
2
3
3
4
40 42 43 58 65
8
-1
0
1
2
3
3
4
40 42 43 58 65
42 43 58 65
Algorithm (see jdk1.5.0_01\demo\applets\SortDemo) void sort(int a[]) throws Exception { for (int i = a.length; --i>=0; ) { boolean swapped = false; for (int j = 0; j
a[j+1]) { int T = a[j]; a[j] = a[j+1]; a[j+1] = T; swapped = true; } ... } if (!swapped) return; } }
Stop here… why? SDA/SORT/V2.0/7
Bubble Sort
SDA/SORT/V2.0/8
Selection Sort: idea
Running time: Worst case: O(n2) Best case: O(n) -- when? why? Variant: bi-directional bubble sort
Ambil yang terbaik (select) dari suatu kelompok, kemudian diletakkan di belakang barisan Lakukan terus sampai kelompok tersebut habis
• original bubble sort: hanya bergerak ke satu arah • bi-directional bubble sort bergerak dua arah (bolak balik).
see jdk1.5.0_01\demo\applets\SortDemo
SDA/SORT/V2.0/9
Selection Sort
SDA/SORT/V2.0/10
Selection Sort
40
2
1
43
3
65
0
-1 58
3
42
4
40
2
1
43
3
4
0
-1 58
3
42 65
40
2
1
43
3
4
0
-1 42
3
58 65
40
2
1
3
3
4
0
-1 42 43 58 65
SDA/SORT/V2.0/11
40
2
1
3
3
4
0
-1 42 43 58 65
-1
2
1
3
3
4
0
40 42 43 58 65
-1
2
1
3
3
0
4
40 42 43 58 65
-1
2
1
0
3
3
4
40 42 43 58 65 SDA/SORT/V2.0/12
2
Selection Sort
Selection: algoritme
-1
2
1
0
3
3
4
40 42 43 58 65
-1
0
1
2
3
3
4
40 42 43 58 65
-1
0
1
2
3
3
4
40 42 43 58 65
-1
0
1
2
3
3
4
40 42 43 58 65
-1
0
1
2
3
3
4
40 42 43 58 65
void sort(int a[]) throws Exception { for (int i = 0; i < a.length; i++) { int min = i; int j; /* Find the smallest element in the unsorted list */ for (j = i + 1; j < a.length; j++) ... } if (a[j] < a[min]) { min = j; } ... }
SDA/SORT/V2.0/13
Selection: algoritme (2)
SDA/SORT/V2.0/14
Selection Sort: analysis
/*
Swap the smallest unsorted element into the end of the sorted list. */ int T = a[min]; a[min] = a[i]; a[i] = T; ...
Running time: Worst case: O(n2) Best case: O(n2) Based on big-oh analysis, is selection sort better than bubble sort? Does the actual running time reflect the analysis?
} }
SDA/SORT/V2.0/15
Insertion Sort
SDA/SORT/V2.0/16
Insertion Sort
Idea: mengurutkan kartu-kartu
40
2
1
43
3
65
0
-1 58
3
42
4
2
40
1
43
3
65
0
-1 58
3
42
4
1
2
40 43
3
65
0
-1 58
3
42
4
SDA/SORT/V2.0/17
1
2
40 43
1
2
1
2
3
65
0
-1 58
3
42
4
3
40 43 65
0
-1 58
3
42
4
3
40 43 65
0
-1 58
3
42
4
SDA/SORT/V2.0/18
3
Insertion Sort
1
0
-1 0
2
1
1 0
3
2
2 1
40 43 65
3
3 2
Insertion Sort
0
40 43 65
-1 58
-1 58
40 3 40 43 43 65 65 58
3
3
3
42
42
42
-1 0
1 0
2 1
3 2
40 3 40 43 43 65 58 65
3
42
4
-1 0
1 0
2 1
3 2
40 3 43 3 40 65 43 43 58 58 65 65 42
4
-1 0
1 0
2 1
3 2
40 3 43 3 40 65 42 43 43 65 58 65
4
-1 0
1 0
2 1
3 2
40 3 43 3 43 65 4 40 42 42 65 43 43 58 58 65 65
4
4
4
SDA/SORT/V2.0/19
Insertion Sort: ineffecient version
Insertion sort untuk mengurutkan array integer
SDA/SORT/V2.0/20
Insertion Sort
Insertion sort yang lebih efisien
public static void insertionSort (int[] a) { for (int ii = 1; ii < a.length; ii++) { int jj = ii; while (( jj > 0) && (a[jj] < a[jj - 1])) { int temp = a[jj]; a[jj] = a[jj - 1]; a[jj - 1] = temp; jj--; } } }
public static void insertionSort2 (int[] a) { for (int ii = 1; ii < a.length; ii++) { int temp = a[ii]; int jj = ii; while (( jj > 0) && (temp < a[jj - 1])) { a[jj] = a[jj - 1]; jj--; } a[jj] = temp; } }
Perhatikan: ternyata nilai di a[jj] selalu sama ⇒ dapat dilakukan efisiensi di sini. SDA/SORT/V2.0/21
Insertion Sort
SDA/SORT/V2.0/22
Mergesort
Running time analysis: Worst case: O(n2) Best case: O(n) Is insertion sort faster than selection sort? Notice the similarity and the difference between insertion sort and selection sort.
Divide and Conquer approach Idea: Merging two sorted array takes O(n) time Split an array into two takes O(1) time
1
SDA/SORT/V2.0/23
2
3
40 43 65
-1
0
3
4
42 58
SDA/SORT/V2.0/24
4
Mergesort: Algorithm
Mergesort
If the number of items to sort is 0 or 1, return. Recursively sort the first and second half separately. Merge the two sorted halves into a sorted group.
40
2
1
43
3
65
0
-1
58
3
42
4
40
2
1
43
3
65
0
-1
58
3
42
4
40
2
1
43
3
65
0
-1
58
3
42
4
40
2
1
43
3
65
0
-1
58
3
42
4
split
SDA/SORT/V2.0/25
Mergesort
40
40
1
2
1
2
1
1
2
2
40
43
43
3
SDA/SORT/V2.0/26
Mergesort
3
65
3
65
3
65
43 65
0
0
-1
-1
58
-1
58
-1
0
58
58
3
3
3
42
4
42
4
4
4
42
split
merge
1
2
40
3
43 65
-1
0
58
3
4
1
2
3
40 43 65
-1
0
3
4
42 58
-1
0
1
2
4
40 42 43 58 62
3
3
merge
42
SDA/SORT/V2.0/27
Merge Sort: implementation
42
SDA/SORT/V2.0/28
Merge Sort: implementation
Implement operation to merge two sorted arrays into one sorted array! public static void merge (int [] array, int lo, int high) // assume: // mid = (lo + high) / 2; // array [lo..mid] and [mid+1..high] are sorted {
There are two ways to merge two sorted array: in place merging using extra place merging
} SDA/SORT/V2.0/29
SDA/SORT/V2.0/30
5
Merge Sort: analysis
Quicksort
Running Time: O(n log n) Why?
Divide and Conquer approach Quicksort(S) algorithm: If the number of items in S is 0 or 1, return. Pick any element v in S. This element is called the pivot. Partition S – {v} into two disjoint groups: • L = {x ∈ S – {v} | x ≤ v} and • R = {x ∈ S – {v} | x ≥ v}
Return the result of Quicksort(L), followed by v, followed by Quicksort(R).
SDA/SORT/V2.0/31
Quicksort: select pivot
-1
65
2 2
3 0
Quicksort: partition
58
4
SDA/SORT/V2.0/32
42
0
3
43
40
4
40
-1
43 3
1
42 58
1
3 65
SDA/SORT/V2.0/33
Quicksort: recursive sort & merge the results
-1 0 1 2 3 3 4
40
SDA/SORT/V2.0/34
Quicksort: partition algorithm 1
42 43 58 65
40
2
1
43
3
65
0
-1 58
3
42
4
4
2
1
43
3
65
0
-1 58
3
42 40
4
2
1
40
3
65
0
-1 58
3
42 43
left
right
-1 0 1 2 3 3 4 40 42 43 58 65
SDA/SORT/V2.0/35
SDA/SORT/V2.0/36
6
Quicksort: partition algorithm 1
Quicksort: partition algorithm 1
4
2
1
3
3
65
0
-1 58 40 42 43
4
2
1
3
3
40
0
-1 58 65 42 43
40
2
1
43
3
65
0
-1 58
4
2
1
3
3
-1
0
40 58 65 42 43
0
2
1
3
3
-1
4
43 42 58 65
-1
0
1
3
3
2
42 43
1
3
3
2
42
2
3
3
2
3
-1 4
4
2
2
1
1
3
3
3
3
-1
-1
0
0
40 58 65 42 43
40 58 65 42 43
left
3
-1
0
1
2
3
3
4
SDA/SORT/V2.0/38
Quicksort: partition algorithm 2 2
1
43
3
65
0
4
2
1
43
3
-1
58
3
42
0
-1
58
3
4
2
1
3
3
65
0
-1
4
2
1
3
3
-1
0
65 58 43 42 40
4
2
1
3
3
-1
left
2
1
43
3
65
0
-1
58
3
2
1
42 40 right
3
3
65
left
0
-1
sort
58 43 42 40 right
left
right
left 4
4
42 40
left 4
Quicksort: partition algorithm 2
right-- while >= pivot
65
65
40 42 43 58 65
SDA/SORT/V2.0/37
original 40
4
3
right
pivot = left++ while < pivot 40
42
right
right 0
65 58 43 42 40 left
CROSSING!
sort
58 43 42 40 right SDA/SORT/V2.0/39
Quicksort: algoritme static void QuickSort(int a[], int lo0, int hi0) { int lo = lo0; int hi = hi0; int pivot; // base case if ( hi0 <= lo0) { return; }
SDA/SORT/V2.0/40
// loop through while( lo <= hi /* find the or equal from the */ while( ( lo ++lo; }
the array until indices cross ) { first element that is greater than to the partition element starting left Index. < hi0 ) && ( a[lo] < pivot )) {
/* find an element that is smaller than the partition element starting from the right Index. */ while( ( hi > lo0 ) && ( a[hi] >= pivot )) { --hi; }
pivot = a[lo0];
// if the indexes have not crossed, swap if( lo <= hi ) { swap(a, lo, hi); ++lo; --hi; } } SDA/SORT/V2.0/41
SDA/SORT/V2.0/42
7
Quicksort: analysis /* If the right index has not reached the left side of array must now sort the left partition. */ if (lo0 < hi) { QuickSort( a, lo0, hi ); } /* If the left index has not reached the right side of array must now sort the right partition. */ if( lo < hi0 ) { QuickSort( a, lo, hi0 ); }
Partitioning takes O(n) Merging takes O(1) So, for each recursive call, the algorithm takes O(n) How many recursive calls does a quick sort need?
}
SDA/SORT/V2.0/43
Quicksort: selecting pivot
SDA/SORT/V2.0/44
Shellsort
Ideal pivot: median element Common pivot First element Element at the middle Median of three
Original: 40
2
1
43
3
65
0
-1 58
3
42
4
3
42
4
5-sort: Sort setiap item yang berjarak 5: 40
2
1
43
3
65
0
-1 58
SDA/SORT/V2.0/45
Shellsort
SDA/SORT/V2.0/46
Performance of Shellsort
Original: 40
2
1
43
3
65
0
-1
58
3
42
4
-1
43
3
42
2
1
58
3
65
4
-1
3
1
4
40
3
42 43 65 58
2 1
3 2
40 3 43 3 43 65 4 40 42 42 65 43 43 58 58 65 65
After 5-sort: 40
0
After 3-sort: 2
0
After 1-sort: -1 0
1 0
SDA/SORT/V2.0/47
N 1000 2000 4000 8000 16000 32000 64000
Insertion Sort 122 483 1936 7950 32560 131911 520000
Shell's 11 26 61 153 358 869 2091
O(N3/2)
Shellsort Odd Gaps Only Dividing by 2.2 11 9 21 23 59 54 141 114 322 269 752 575 1705 1249
O(N5/4)
O(N7/6)
SDA/SORT/V2.0/48
8
Generic Sort
Generic Sort
Bagaimana jika diperlukan method untuk mengurutkan array dari String, array dari Lingkaran (berdasarkan radiusnya) ? Apakah mungkin dibuat suatu method yang bisa dipakai untuk semua jenis object? Ternyata supaya object bisa diurutkan, harus bisa dibandingkan dengan object lainnya (mempunyai behavior bisa dibandingkan - comparable ⇒ method). Solusinya: Gunakan interface yang mengandung method yang dapat membandingkan dua buah object.
REVIEW: Suatu kelas yang meng-implements sebuah interface, berarti kelas tersebut mewarisi interface (definisi method-method) = interface inheritance, bukan implementation inheritance Dalam Java, terdapat interface java.lang.Comparable method: int compareTo (Object o)
SDA/SORT/V2.0/49
Other kinds of sort
SDA/SORT/V2.0/50
Further Reading
Heap sort. We will discuss this after tree. Postman sort / Radix Sort. etc.
SDA/SORT/V2.0/51
http://telaga.cs.ui.ac.id/WebKuliah/IKI101 00/resources/animation/
Chapter 8: Sorting Algorithm
SDA/SORT/V2.0/52
What’s Next
Recursive (Chapter 7)
SDA/SORT/V2.0/53
9
