S or ti n g
S o rt in g S o rt in g S o rt in g S o rt in g A lg o ri th m s A lg o ri th m s A lg o ri th m s A lg o ri th m s • B e tw e e n O ( n
2) a n d O ( n lo g n ) • F o r s p e c ia l in p u t, O ( n ) s o rt in g i s p o s s ib le • F o r s p e c ia l in p u t, O ( n ) s o rt in g i s p o s s ib le – E .g ., i n p u t – in te g e r b e tw e e n – O ( n ) a n d O ( n )
S e le c ti o n S o rt S e le c ti o n S o rt S e le c ti o n S o rt S e le c ti o n S o rt • F o r e a c h l o o p – F in d m a x – Sw a p m a x a n d r ig h tm o s t e le m e n t – E x c lu d e r ig h tm o s t e le m e n t • L o o p u n ti l o n e e le m e n t le ft
T h e l a rg e st i te m T h e l a rg e st i te m F in d in g t h e R e c u rs iv e F in d in g t h e R e c u rs iv e F in d in g t h e R e c u rs iv e F in d in g t h e R e c u rs iv e S tr u c tu re S tr u c tu re S tr u c tu re S tr u c tu re R unni ng t im e: ( n- 1) + ( n- 2) + ·· ·+ 2+ 1 = O ( n
2) W or st c as e A ve ra ge c as e
selectionSort(A[], n)▷Sort arrayA[1 ... n] { forforforforlast ← ndowntodowntodowntodownto2 {---① Find max A[k] among A[1 ... last];---② A[k] ↔ A[last]; ▷Swap A[k] andA[last]---③ } } Running time: —forloop in ①:n-1times —# of comparisons to find max in ②: n-1, n-2, , 2, 1 —swap in ③: constant time
( n- 1) + ( n- 2) + ·· ·+ 2+ 1 = O ( n
2)
151129206537348318 15112920657348318
Input ArrayInput Array Find maxFind max(73)(73) 731129206531548318
Swap 73 and the rightmost number (15)Swap 73 and the rightmost number (15) 731129206531548318
Find max except the rightmost number. (65)Find max except the rightmost number. (65)
3 1 1 FirstFirstlooploop
S e le c ti o n S o rt S e le c ti o n S o rt S e le c ti o n S o rt S e le c ti o n S o rt E x a m p le E x a m p le E x a m p le E x a m p le
736529201131548318Swap 65 with the rightmost number (11)Swap 65 with the rightmost number (11) 736529201131548318
Find max except the two rightmost numbers (48)Find max except the two rightmost numbers (48) 736548312920151138
Swap 8 with the rightmost number (3)Swap 8 with the rightmost number (3) 736548312920151183
Final ArrayFinal Array
. . . . . .
1 1 Second loopSecond loop
B u b b le S o rt B u b b le S o rt B u b b le S o rt B u b b le S o rt R unni ng t im e: ( n- 1) + ( n- 2) + ·· ·+ 2+ 1 = O ( n
2) W or st c as e A ve ra ge c as e
bubbleSort(A[], n)▷Sort A[1 ... n] { forforforforlast ← ndowntodowntodowntodownto2---① forforforfori ← 1totototolast-1---② ifififif(A[i] > A[i+1])thenthenthenthenA[i] ↔ A[i+1]; ▷ Swap--③ } } Running time: —①: forloop –n-1times —②:forloop
–
n-1, n-2, , 2, 1times —③: constant time( n- 1) + ( n- 2) + ·· ·+ 2+ 1 = O ( n
2)
1 56 52 92 01 187 34 83 13 1 56 52 92 01 187 34 83 13
Input arrayInput array Compare adjacent pairs from the leftCompare adjacent pairs from the left 1 56 52 92 01 17 384 83 13
Swap if the order is not rightSwap if the order is not right
B u b b le S o rt B u b b le S o rt B u b b le S o rt B u b b le S o rt E x a m p le E x a m p le E x a m p le E x a m p le
7 31 56 52 92 01 184 83 13Exclude the rightmost number (73)Exclude the rightmost number (73)
1 56 52 92 07 31 184 83 13 1 56 52 97 32 01 184 83 13 7 31 56 52 92 01 184 83 13
7 31 56 52 92 01 14 883 13
Swap if the pair is not orderlySwap if the pair is not orderly 7 31 56 52 92 04 81 183 13 7162421833
731565292011848313
Starting from the left, compare adjacent pairsStarting from the left, compare adjacent pairs 7 31 56 52 94 82 01 183 13 7 31 56 54 82 92 01 183 13 7 31 56 54 82 92 01 183 13 7 36 51 54 82 92 01 183 13 7 36 51 54 82 92 01 183 13
ExclureExclurethe rightmost value (65)the rightmost value (65)
837 36 54 83 12 92 01 51 1
Keep excluding the values by repeating the loopKeep excluding the values by repeating the loop 7 36 54 83 12 92 01 51 183
Process the final two elementsProcess the final two elements
7 36 54 83 12 92 01 51 183 35819051
In s e rt io n S o rt In s e rt io n S o rt In s e rt io n S o rt In s e rt io n S o rt R unni ng t im e: O ( n
2)
Worst case: 1+2+···+(n-2)+(n-1) Average case: ½ (1+2+···+(n-2)+(n-1))insertionSort(A[], n)▷Sort A[1 ... n] { forforforfori ← 2totototon---① Insert A[i] into the right position in A[1 ... i];----② } Running time: —①:forloop –n-1times —②: i-1 times comparison in the worst case
W or st c as e: 1+ 2+ ·· ·+ ( n- 2) + ( n- 1)
=O (n
2) A ve ra ge c as e: ½ ( 1+ 2+ ·· ·+ ( n- 2) + ( n- 1) )
=O (n
2)
In d u c ti v e V e ri fi c a ti o n o f In s e rt io n In d u c ti v e V e ri fi c a ti o n o f In s e rt io n In d u c ti v e V e ri fi c a ti o n o f In s e rt io n In d u c ti v e V e ri fi c a ti o n o f In s e rt io n S o rt S o rt S o rt S o rt • A [1 ] – So rt e d • If A [1 … k ] s o rt e d B y t h e i n s e rt io n i n
②, A [1 … k + 1 ] a re s o rt e d
mergeSort(A[ ], p, r) ▷Sort A[p ... r] { ifififif(p < r) thenthenthenthen{ q ← (p+q)/2;------------①▷Midpoint of p, q mergeSort(A, p, q);--------②▷Sort the left mergeSort(A, q+1, r); ------③▷Sort the right merge(A, p, q, r);---------④
M e rg e s o rt M e rg e s o rt M e rg e s o rt M e rg e s o rt
merge(A, p, q, r);---------④▷Merge } } merge(A[ ], p, q, r) { Two sorted array A[p ... q] andA[q+1 ... r] Merge them into one array A[p ... r] }313657381120294815 313657381120294815
Input array givenInput array given Partition the arrayPartition the array
11
M e rg e s o rt M e rg e s o rt M e rg e s o rt M e rg e s o rt E x a m p le E x a m p le E x a m p le E x a m p le
Sort them independentlySort them independently 383165731115202948 MergeMerge 38111520293148657311 22 33 44
383 16 57 31 11 52 02 94 8 iijj tt 83 16 57 31 11 52 02 94 8 iijj
ppqq rr
M e rg e M e rg e M e rg e M e rg e E x a m p le E x a m p le E x a m p le E x a m p le
3iijj tt 3 16 57 31 11 52 02 94 8 38
iijj tt
3 16 57 31 52 02 94 8 381 1iijj tt 3 16 57 32 02 94 8 iijj 381 11 5 tt 3 16 57 32 94 8 381 11 52 0
iijj tt
3 16 57 34 8 381 11 52 02 9
iijj tt 6 57 34 8 iijj 381 11 52 02 93 1 tt 6 57 3 381 11 52 02 93 14 8
iijj tt
381 11 52 02 93 14 86 57 3
iijj tt
7 2 9 43 8 6 11 3 6 82 4 7 91 2 3 4 6 7 8 9
A n im a ti o n A n im a ti o n A n im a ti o n A n im a ti o n (M e rg e s o rt ) (M e rg e s o rt ) (M e rg e s o rt ) (M e rg e s o rt )
9 | 47 2 |9 4 7 |2 7
7 2
22 7
2 7 94
944 9
4 92 4 7 9
R u n n in g t im e : R u n n in g t im e : OO ((nn lo g lo gnn ))
Q u ic k s o rt Q u ic k s o rt Q u ic k s o rt Q u ic k s o rt
quickSort(A[], p, r) ▷Sort A[p ... r] { ifififif(p < r) thenthenthenthen{ q = partition(A, p, r);▷Partition quickSort(A, p, q-1);▷Sort the left quickSort(A, q+1, r);▷Sort the right } } } partition(A[], p, r) { Arrange the elements in A[p ... r] according to A[r] Return the position of A[r]; }5 1
9
426 8
3314259 6 8
123459 6 8
1234 56 8 9
A n im a ti o n A n im a ti o n A n im a ti o n A n im a ti o n (Q u ic k s o rt ) (Q u ic k s o rt ) (Q u ic k s o rt ) (Q u ic k s o rt )
1121
314 22134 1 2 11
124412
12341234
9 6 8 8 6 6
8 6 9 6 8 6 6 8 6 8
6 8 9 6 8 9 A ve ra g e r u n n in g t im e : A ve ra g e r u n n in g t im e : OO ((nn lo g lo gnn )) W o rst r u n n in g t im e : W o rst r u n n in g t im e : OO ((nn
22))
318487311320296515
In the input array, set the first value as a pivotIn the input array, set the first value as a pivot Partition the input array so that smaller elements on the left, Partition the input array so that smaller elements on the left,
Q u ic k s o rt Q u ic k s o rt Q u ic k s o rt Q u ic k s o rt E x a m p le E x a m p le E x a m p le E x a m p le
811315314820296573Partition the input array so that smaller elements on the left, Partition the input array so that smaller elements on the left, and bigger elements on the rightand bigger elements on the right Sort the left and the right independentlySort the left and the right independently 381115202931486573
(a ) (a ) (b ) (b )
318487311320296515 318487311320296515 831487311320296515
pp rr
iijj iijjP a rt it io n P a rt it io n P a rt it io n P a rt it io n E x a m p le E x a m p le E x a m p le E x a m p le
831487311320296515 831487311320296515 811487331320296515 iijjiijj iijj iijj
(a ) (a ) (b ) (b ) (c)(c)
811373314820296515 811373314820296515
iijj iijj 811373314820296515 811373314820296515 811315314820296573
iijj ii ii
(d ) (d ) (e ) (e )
H e a p s o rt H e a p s o rt H e a p s o rt H e a p s o rt • H e a p
–Complete binary tree that satisfies the following •Each node’s value is not bigger than its children• H e a p s o rt • H e a p s o rt
–Convert the input array to a Heap, and remove top element from the Heap one by oneh e a p So rt (A [ ], n ) { b u il d H e a p (A , n ); ▷ M a ke H e a p fo r fo r fo r fo r i ← n d o w n to d o w n to d o w n to d o w n to 2 { fo r fo r fo r fo r i ← n d o w n to d o w n to d o w n to d o w n to 2 { A [1 ] ↔ A [ i ]; ▷ S wa p h e a p if y (A , 1 , i -1 ); } } OO ((nn lo g lo g nn ) ti m e i n t h e w o rst ca se ) ti m e i n t h e w o rst ca se
33 66 44
33 88 44
H e a p H e a p H e a p H e a p 66 44 88 99 77
88 44 66 99 77 H e a p H e a p N o t a H e a p N o t a H e a p
33 66 44 66 44 88 99 77 N o t a H e a p N o t a H e a p
33 11
H e a p c a n b e r e p re s e n te d i n a n a rr a y H e a p c a n b e r e p re s e n te d i n a n a rr a y H e a p c a n b e r e p re s e n te d i n a n a rr a y H e a p c a n b e r e p re s e n te d i n a n a rr a y 66 44 88 99 77 66 55 44
33 22 3 6 4 8 9 7 AA
112233445566
33 66 44 88 99 77
77 66 44 88 99
44 66 77 88 99 33 33
Remove 3Remove 3
(a ) (a ) (b ) (b ) (c)(c)
H e a p s o rt E x a m p le H e a p s o rt E x a m p le H e a p s o rt E x a m p le H e a p s o rt E x a m p le 88 99 77 88 99 88 99 33 33 99 66 77 88 44 33
Remove 4Remove 4
66 99 77 88 44 33
66 88 77 99 44 33
(f ) (f ) (e ) (e ) (d ) (d )
99 88 77 66 44 33
77 88 99 66 44 33
Remove 6Remove 6
99 88 77 66 44 33
Remove 7Remove 7
(g ) (g )
(h ) (h ) (i ) (i ) 88 99 77 66 44 33
99 88 77 66 44 33
Remove 8Remove 8
