Transcript Sorting

Chapter 7 Sorting
•
•
•
•
•
Sort is a very useful and frequently used operation
Require fast algorithm
Easy algorithms sort in O(N2)
Complicate algorithms sort in O(N log N)
Any general-purpose sorting algorithm requires
W(N log N) comparisons
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
1
Sorting
What is covered in this chapter:
• Sort array of integers
• Comparison-based sorting
main operations are compare and swap
• Assume that the entire sort can be done in main
memory
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
2
Sorting Algorithms
•
•
•
•
•
•
Insertion Sort
Shellsort
Heapsort
Mergesort
Quicksort
Bucket Sort
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
3
Insertion Sort
• Sort N elements in N-1 passes ( pass 1 to N-1 )
• In pass p
– insertion sort ensures that the elements in positions
0 through p are in sorted order
– elements in positions 0 through p-1 are already in
sorted order
– move the element in position p to the left until its
correct place is found
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
4
Insertion Sort
Original
34 8 64 51 32 21
positions
moved
After p = 1
8 34 64 51 32 21
1
After p = 2
8 34 64 51 32 21
0
After p = 3
8 34 51 64 32 21
1
After p = 4
8 32 34 51 64 21
3
After p = 5
8 21 32 34 51 64
4
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
5
Insertion Sort
• The element in position p is saved in tmp
• All larger elements prior to position p are
moved one spot to the right
• Then tmp is placed in the correct spot
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
6
public static void insertionSort( Comparable [ ] a )
{
int j;
for( int p = 1; p < a.length; p++ )
{
Comparable tmp = a[ p ];
for( j = p; j > 0 &&
tmp.compareTo( a[ j - 1 ] ) < 0; j-- )
a[ j ] = a[ j - 1 ];
a[ j ] = tmp;
}
}
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
7
Analysis
• Insertion sort has nested loops. Each loop can
have N iterations. So, insertion sort is O(N2).
• The inner loop can be executed at most p+1 times
for each value of p.
• For all p = 1 to N-1, the inner loop can be
executed at most 2 + 3 + 4 + . . . + N = q(N2)
• Input in reverse order can achieve this bound.
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
8
Analysis
• If the input is presorted, the running time is O(N)
because the test in the inner for loop always fails
immediately.
• The average case is q(N2)
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
9
Shellsort
• Sort N element in t passes
• Each pass k has an associated value hk
• The t passes use a sequence of h1 , h2 , . . . , ht
(called increment sequence)
• The first pass uses ht and the last pass uses h1
• ht > . . . > h2 > h1 and h1 = 1
• In each pass, all elements spaced hk apart are
sorted
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
10
Shellsort
Original
81 94 11 90 12 35 17 95 28 58 41 75 15
After 5-sort 35 17 11 28 12 41 75 15 96 58 81 94 95
After 3-sort 28 12 11 35 15 41 58 17 94 75 81 96 95
After 1-sort 11 12 15 17 28 35 41 58 75 81 94 95 96
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
11
Shellsort
• A sequence that is sorted using hk is said to be
hk-sorted
• An hk-sorted sequence that is then hk-1 sorted
remains hk-sorted
• An hk-sort performs an insertion sort on hk
independent subarrays
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
12
Shellsort
• Any increment sequence works, as long as h1 = 1
• Some choices are better than others
• A popular (but poor) increment sequence is
1, 2, 4, 8, . . . , N/2
ht = N/2 , and hk =
hk+1/2
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
13
Shellsort v.s. Insertion Sort
• The last pass of shellsort performs an insertion
sort on the whole array (h1-sort).
• But shellsort is better than insertion sort because
shellsort perform insertion sorts on presorted
arrays
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
14
public static void shellsort( Comparable [ ] a )
{
int j;
for( int gap = a.length / 2; gap > 0; gap /= 2 )
for( int i = gap; i < a.length; i++ )
{
Comparable tmp = a[ i ];
for( j = i;
j >= gap && tmp.compareTo(a[j-gap]) < 0;
j -= gap )
a[ j ] = a[ j - gap ];
a[ j ] = tmp;
}
}
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
15
A Bad Case of Shellsort
• N is a power of 2
• All the increments are even, except the last
increment, which is 1.
• The N/2 largest numbers are in the even
positions and the N/2 smallest numbers are in
the odd positions
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
16
A Bad Case of Shellsort
1 9 2 10 3 11 4 2 5 13 6 14 7 15 8 16
After 8-sort 1 9 2 10 3 11 4 2 5 13 6 14 7 15 8 16
After 4-sort 1 9 2 10 3 11 4 2 5 13 6 14 7 15 8 16
After 2-sort 1 9 2 10 3 11 4 2 5 13 6 14 7 15 8 16
After 1-sort 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
17
A Bad Case of Shellsort
• No sorting is performed until the last pass
• i th smallest number (i ฃ N/2) is in position 2i-1
• Restoring the i th element to its correct place
requires moving it i-1 spaces
• Restoring N/2 smallest numbers requires i 1
= W(N2) work
N/2
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
i 1
18
Worst-Case Analysis
• A pass with increment hk consists of hk insertion
sorts of about N/hk elements
• Since insertion sort is quadratic, the total cost of a
pass is O(hk(N/hk)2) = O(N 2/hk)
• Summing over all passes gives
O ( i 1 N / hi )  O (N
t
2
2
2
1
/
h
)

O
(
N
)
i 1 i
t
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
19
Hibbard’s Increments
• Increment sequence 1, 3, 7, 15, . . . , 2k - 1
• hk+1= 2 hk + 1
• Consecutive increments have no common
factors
• Worst case running time of Shellsort using
Hibbard’s increment is Q(N3/2)
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
20
Analysis of Hibbard’s Increments
• Input of hk-sort is already hk+1-sorted and hk+2sorted (e.g. input of 3-sort is already 7-sorted and
15-sorted)
• Let i be the distance between two elements. If i is
expressible as a linear combination of hk+1 and hk+2,
then a[p-i] ฃ a[p]
• For example, 52 = 1*7 + 3*15, so a[100] ฃ a[152]
because a[100] ฃ a[107] ฃ a[122] ฃ a[137] ฃ a[152]
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
21
Analysis of Hibbard’s Increments
• All integers ณ (hk+1 -1)(hk+2 -1) = 8hk2 + 4hk can be
expressed as a linear combination of hk+1 and hk+2
• Proof:
i
= x*hk+1 + y*hk+2
i+1 = x*hk+1 + y*(2*hk+1+1) +1
i+1 = x*hk+1 + y*(2*hk+1+1) - 2*hk+1 + 2*hk+1 + 1
i+1 = (x-2)*hk+1 + (y+1)*hk+2
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
22
Analysis of Hibbard’s Increments
• So, a[p-i] ฃ a[p] if i ณ 8hk2 + 4hk
• In each pass, a[p] is never moved further than
a[p-i] or 8hk2 + 4hk elements to the left
• The innermost for loop is executed at most
8hk + 4 = O(hk) times for each position. So,
each pass has O(Nhk) running time.
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
23
Analysis of Hibbard’s Increments
• For hk > N1/2, use the bound O(N2/hk).
• For hk ฃ N1/2 use the bound O(Nhk)
• About half of the increment sequence satisfy
hk < N1/2
• The total time is
t /2
O (  Nhk 
k 1
t
t /2
2
2
N
/
h
)

O
(
N
h

N

 k
k
k t / 21
k 1
t
1 / h
k t / 21
k
N2
 O (Nht / 2 )  O (
)  O (N 3 / 2 )
ht / 2
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
24
Sedgewick’s Increments
• Sedgewick’s increments is {1, 5, 19, 41, 109, . .
.} which can be term as 9*4i - 9*2i + 1 or 4i -3*2i
+1
• O(N4/3) worst-case time and O(N7/6) average time
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
25
Heap Sort
• Build a binary heap of N elements and then
perform N deleteMin operations
• Building a heap takes O(N) time and N
deleteMin operations take O(N log N) time
• The total running time is O(N log N)
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
26
Heap Sort
• The sorted elements, which are taken out of the
heap, can be place in another array.
• To avoid using extra array to keep result,
replace the last element in the heap with the
element taken out of the heap.
• To get the result in increasing order, use maxheap instead.
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
27
9
7
53
26
59
58
41
31
97 53 59 26 41 58 31
5
9
53
26
After one
deleteMax
58
41
31
97
59 53 58 26 41 31 97
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
28
5
8
53
26
31
59
41
After two
deleteMax
97
58 53 31 26 41 59 97
5
3
41
26
31
58
59
After three
deleteMax
97
53 41 31 26 58 59 97
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
29
public static void heapsort( Comparable [ ] a )
{
for( int i = a.length / 2; i >= 0; i-- )
percDown( a, i, a.length );
for( int i = a.length - 1; i > 0; i-- )
{
swapReferences( a, 0, i );
percDown( a, 0, i );
}
}
private static int leftChild( int i )
{ return 2 * i + 1; }
// array begins at index 0
public static final void swapReferences( Object [ ] a,
int index1, int index2 )
{
Object tmp = a[ index1 ];
a[ index1 ] = a[ index2 ];
a[ index2 ] = tmp;
}
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
30
private static void percDown( Comparable [ ] a, int i, int n )
{
int child;
Comparable tmp;
for( tmp = a[ i ]; leftChild( i ) < n; i = child )
{
child = leftChild( i );
if( child != n - 1 &&
a[ child ].compareTo( a[ child + 1 ] ) < 0 )
child++;
if( tmp.compareTo( a[ child ] ) < 0 )
a[ i ] = a[ child ];
else
break;
}
a[ i ] = tmp;
}
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
31
Analysis
• Building the heap uses at most 2N comparisons
• deleteMax uses at most 2N log N - O(N)
comparisons
• So, heapsort uses at most 2N log N - O(N)
comparison
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
32
Analysis
• Worst-case and average-case are only slightly
different
• Average number of comparison is
2N log N - O(N log log N)
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
33
Mergesort
• The fundamental operation is merging two
sorted lists.
• Because the lists are sorted, this can be done in
one pass through the input, if the output is put
in a third list.
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
34
Mergesort
• Mergesort takes two input arrays A and B, an
output array C, and three counters, Actr, Bctr,
and Cctr.
• The smaller of A[Actr] and B[Bctr] is copied to
the next entry in C, and appropriate counters are
advanced
• Remaining input items are copied to C
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
35
Mergesort
1 13 24 26
Actr
1 13 24 26
Actr
1 13 24 26
Actr
2 15 27 38
Bctr
Cctr
2 15 27 38
Bctr
2 15 27 38
1
Cctr
1 2
Bctr
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
Cctr
36
Mergesort
1 13 24 26
Actr
1 13 24 26
Actr
1 13 24 26
Actr
2 15 27 38
1 2 13
Bctr
Cctr
2 15 27 38
1 2 13 15
Bctr
2 15 27 38
Cctr
1 2 13 15 24
Bctr
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
Cctr
37
Mergesort
1 13 24 26
Actr
1 13 24 26
2 15 27 38
Bctr
Actr
Cctr
2 15 27 38
Actr
1 13 24 26
1 2 13 15 24 26
1 2 13 15 24 26
Bctr
2 15 27 38
Cctr
1 2 13 15 24 26 27 38
Bctr
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
Cctr
38
Mergesort
• If N > 1, recursively mergesort the first half and
the second half
• If N = 1, only one element to sort -> the base
case
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
39
Mergesort: Divide and Conquer
24 13 26 1 2 27 38 15
24 13 26 1
24 13
26 1
24 13 26
13 24
2 27 38 15
1
1 26
1 13 24 26
2 27
2
38 15
27 38 15
2 27
15 38
2 15 27 38
1 2 13 15 24 26 27 38
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
40
Analysis
• Merging two sorted lists is linear, because at
most N-1 comparisons are made
• For N = 1, the time to mergesort is constant
• Otherwise, the time to mergesort N numbers is
the time to do two recursive mergesorts of size
N/2, plus the linear time to merge
• T(N) = N log N + N
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
41
public static void mergeSort( Comparable [ ] a )
{
Comparable [ ] tmpArray = new Comparable[ a.length ];
mergeSort( a, tmpArray, 0, a.length - 1 );
}
private static void mergeSort( Comparable [ ] a,
Comparable [ ] tmpArray,
int left, int right )
{
if( left < right )
{
int center = ( left + right ) / 2;
mergeSort( a, tmpArray, left, center );
mergeSort( a, tmpArray, center + 1, right );
merge( a, tmpArray, left, center + 1, right );
}
}
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
42
private static void merge( Comparable [ ] a,
Comparable [ ] tmpArray, int leftPos,
int rightPos, int rightEnd )
{
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
while( leftPos <= leftEnd && rightPos <= rightEnd )
if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 )
tmpArray[ tmpPos++ ] = a[ leftPos++ ];
else
tmpArray[ tmpPos++ ] = a[ rightPos++ ];
while( leftPos <= leftEnd ) // Copy rest of first half
tmpArray[ tmpPos++ ] = a[ leftPos++ ];
while( rightPos <= rightEnd ) // Copy rest of right half
tmpArray[ tmpPos++ ] = a[ rightPos++ ];
for( int i = 0; i < numElements; i++, rightEnd-- )
a[ rightEnd ] = tmpArray[ rightEnd ];
}
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
43
Quicksort
Divide-and-Conquer recursive algorithm
1. If the number of elements in S is 0 or 1, then
return
2. Pick any element v in S. This is called the pivot
3. Partition the remaining elements in S ( S - {v} )
into two disjoint groups: S1 and S2. S1 contains
elements ฃ v, S2 contains elements ณ v
4. Return {quicksort(S1), v, quicksort(S2)}
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
44
13
81
92
43
65
31
57
26
75
0
select pivot
13 81 92 43 65 31 57 26 75 0
partition
13
0
26
43
57
31
92
65
quicksort
75
81
quicksort
0
13
26
31
43
57
0
13
26
31
43
57
65
65
75
75
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
81
81
92
92
45
Quicksort v.s. Mergesort
• In Quicksort, subproblems need not be of equal
size
• Quicksort is faster because partitioning step can
be performed in place and very efficiently
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
46
Picking the Pivot
• Use the first element as the pivot
– Bad choice
– If input is presorted or in reverse order, the pivot
makes poor partitioning because either all elements
go into S1 or they go into S2
– If the input is presorted, quicksort will take
quadratic time to do nothing useful
• Use the larger of the first two distinct elements
– Also bad
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
47
Picking the Pivot
• Choose the pivot randomly
– generally safe
– generating random numbers is expensive
– does not reduce the average running time
• Median-of-Three Partitioning
– The best choice would be the median of the array
– A good estimation is to use the median of the left,
right, and center elements as pivot
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
48
Partitioning Strategy
1. Swap the pivot with the last element
2. i starts at the first element and j starts at the next-to-last
element
3. Move i right, skipping over elements smaller than the pivot.
Move j left, skipping over elements larger than the pivot.
Both i and j stops if encounter an element equal to the pivot
4. When i and j stop, if i is to the left of j, swap their elements
5. Repeat 3 and 4 until i and j cross
6. Swap the pivot with i’s element
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
49
Partitioning
8
1
4
9
0
3
5
2
1
4
9
0
3
5
i
2
2
7
6
7
6
7
6
j
1
4
9
0
3
5
i
2
6
j
i
8
7
8
j
1
4
9
i
0
3
5
8
j
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
50
Partitioning
2
1
4
5
0
3
2
1
1
4
4
5
5
8
7
6
8
7
6
8
7
9
j
i
2
9
0
0
3
9
j
i
3
6
i
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
pivot
51
Small Arrays
• For very small arrays (N ฃ 20), quicksort does
not perform as well as insertion sort.
• Quicksort is recursive. So, these cases occur
frequently.
• So, use a sorting algorithm that is efficient for
small arrays, such as insertion sort.
• A good cutoff range is N = 10
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
52
public static void quicksort( Comparable [ ] a )
{ quicksort( a, 0, a.length - 1 ); }
private static void quicksort( Comparable [ ] a,
int left, int right )
{
if( left + CUTOFF <= right )
{
Comparable pivot = median3( a, left, right );
int i = left, j = right - 1;
for( ; ; )
{
while( a[ ++i ].compareTo( pivot ) < 0 ) { }
while( a[ --j ].compareTo( pivot ) > 0 ) { }
if( i < j ) swapReferences( a, i, j );
else break;
}
swapReferences( a, i, right - 1 );
quicksort( a, left, i - 1 );
quicksort( a, i + 1, right );
}
else insertionSort( a, left, right );
}
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
53
private static Comparable median3( Comparable [ ] a,
int left, int right )
{
int center = ( left + right ) / 2;
if( a[ center ].compareTo( a[ left ] ) < 0 )
swapReferences( a, left, center );
if( a[ right ].compareTo( a[ left ] ) < 0 )
swapReferences( a, left, right );
if( a[ right ].compareTo( a[ center ] ) < 0 )
swapReferences( a, center, right );
// Place pivot at position right - 1
swapReferences( a, center, right - 1 );
return a[ right - 1 ];
}
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
54
Analysis
T(N) = T(i) + T(N - i - 1) + cN
; i = |S1|
Worst-Case
T(N) = T(N - 1) + cN
T(N) = T(1) + c S i = O(N2)
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
55
Analysis
Best Case
T(N) = 2T(N/2) + cN
T(N) = cN log N + N = O(N log N)
Average Case
T(N) = 2/N ( S T(j) ) + cN
T(N) = O(N log N)
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
56
Bucket Sort
• Sort N integers in the range 1 to M
• Use M buckets, one bucket for each integer i
• Bucket i stores how many times i appears in the
input. Initially, all buckets are empty.
• Read input and increase values in buckets
• Finally, scan the buckets and print the sorted list
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
57
Bucket Sort
3, 1, 3, 5, 8, 7, 4, 2, 9, 5, 4, 10, 4
1
1
2
3
2
0
1
1
1
1
1, 2, 3, 3, 4, 4, 4, 5, 5, 7, 8, 9, 10
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
58
Bucket Sort
• Input A1, A2, . . . , AN consist of positive integer
smaller than M
• Keep an array count[ ] of size M, which is initialized
to all 0s
• When Ai is read, increment count[Ai] by 1
• After all input is read, scan the count array, printing
out the sorted list
• This algorithm takes O(M+N)
2110211 Intro. to Data Structures Chapter 7 Sorting
Veera Muangsin, Dept. of Computer Engineering,
59