CpE 300
Design and Analysis
of Algorithms
SORTING IN LINEAR TIME
1
Comparison Sort Algorithms
• Insertion sort, heapsort, merge sort, and Quicksort are comparison sort
algorithms.
• Comparison sorts are sorting algorithms that are based only on comparison
between the input elements.
• Heapsort and merge sort have 𝜪(𝒏 𝐥𝐠 𝒏) while quicksort and BST sort has on
average 𝜪(𝒏 𝒍𝒈 𝒏) .
• Can they do better?
• Answer: No!!
• We will show a lower bound 𝛀(𝒏 𝐥𝐠 𝒏) for the sorting problem.
• Any comparison-based sorting algorithm must do at least 𝒏 𝐥𝐠 𝒏 amount
of work in the worst-case
2
Lower Bounds for Sorting
• Comparison sorts can be viewed in terms of a decision trees.
• A decision tree is a full binary tree that represents the
comparisons between elements that are performed by a
particular sorting algorithm operating on an input of a given
size.
• Here we assume without loss of generality that elements are
distinct, so we only care about these comparison between two
elements 𝑎 and 𝑎 :
• 𝑎 ≤𝑎
• 𝑎 ≥𝑎
3
Decision Tree Model
Example:
• The decision tree for insertion sort
• Input: Array of three elements
4
Decision Tree
𝑎 :𝑎 A = [𝑎 , 𝑎 , 𝑎 ]
𝑎 :𝑎 𝑎 :𝑎
[𝑎 , 𝑎 , 𝑎 ] 𝑎 :𝑎 [𝑎 , 𝑎 , 𝑎 ] 𝑎 :𝑎
[𝑎 , 𝑎 , 𝑎 ] [𝑎 , 𝑎 , 𝑎 ] [𝑎 , 𝑎 , 𝑎 ] [𝑎 , 𝑎 , 𝑎 ]
5
Decision Tree
7: 10 sort A = [7,10,5]
Using Insertion sort
10: 5 7: 5
[𝑎 , 𝑎 , 𝑎 ] 7: 5 [𝑎 , 𝑎 , 𝑎 ] 10: 5
[𝑎 , 𝑎 , 𝑎 ] [𝑎 , 𝑎 , 𝑎 ] [𝑎 , 𝑎 , 𝑎 ] [𝑎 , 𝑎 , 𝑎 ]
6
Decision Tree
7: 10 sort A = [7,10,5]
Using Insertion sort
10: 5 7: 5
[𝑎 , 𝑎 , 𝑎 ] 7: 5 [𝑎 , 𝑎 , 𝑎 ] 10: 5
[𝑎 , 𝑎 , 𝑎 ] [5,7,10] [𝑎 , 𝑎 , 𝑎 ] [𝑎 , 𝑎 , 𝑎 ]
7
Decision Tree
• The decision tree shows the required number of
comparisons required to reach a solution.
• The decision tree covers all possibilities.
• The height of the decision tree depends on the of
the comparison algorithm.
• for insertion and for heapsort.
• A decision tree has leaves, which are all possible
permutations.
8
Theorem:
Any comparison sort algorithm requires comparisons in
Lower the worst case
Proof:
Bounds • A decision tree has at least Leaves that are all possible
Using permutation.
Decision • Any binary tree with height has at most leaves
Trees
– taken at chapter 3
9
Lower Corollary:
Heapsort and merge sort are
Bounds asymptotically optimal comparison sorts.
Using
Decision Proof:
Trees • Minimum height for a decision tree is
• Worst case for a comparison sort is the height of its decision tree.
minimum worst case for a comparison sort algorithm is
• Since heapsort and merge sort have worst case of , they
reach the lowest value possible for a worst case.
• They are asymptotically optimal.
10
Lower bounds for Algorithms
• Lower bounds are useful in that they would tell us what is the
absolute best we can achieve using ANY algorithm.
• We do not need to look for “better” algorithms if we have one
that achieves this lower bound.
• We call an algorithm with a worst-case upper bound (Big-O)
that matches the worst-case lower bound, an asymptotically
optimal algorithm.
• E.g. merge sort, heapsort
11
Tightness vs. Optimality
• Tightness refers to whether the lower bound Ω and upper bound 𝑂 of an algorithm’s
(worst/average/expected) running time are equal.
• If they are equal, we say the analysis is tight and we represent it with 𝚯
• This indicates how good your proof/analysis is – you want to make these bounds equal so
that we do not have any gaps.
• E.g. the worst-case running time of insertion sort is Ω 𝑛 and Ο 𝑛 . This implies that
the running time is Θ 𝑛
• Optimality refers to whether the upper bound 𝑂 of the algorithm is equal to the lower bound Ω
of the problem.
• If they are equal we say the algorithm is asymptotically optimal.
• This indicates whether your algorithm can be further improved or not. If it is optimal, you
cannot improve it further.
• E.g. merge sort is asymptotically optimal because its worst-case running time is
Ο 𝑛 lg 𝑛 which is equal to the sorting lower bound Ω 𝑛 lg 𝑛
12
Sorting in Linear Time
• We showed that any comparison-based sorting algorithm
must make at least amount of work.
• Is there any way to sort without doing comparisons?
• And if there is, how fast can they get?
13
Counting Sort
• It takes elements in the range to , for some integer
• Input: , where
• Output: Input: , which is sorted.
• Advantages:
• It takes Ο(𝑛) when k = Ο(𝑛)
• It is a stable sorting algorithm.
• Equal numbers appear in the output array in the same order as they
do in the input array.
14
Counting Sort
• Basic Idea:
• Count the number of elements less than x
• Place x accordingly.
• The algorithm takes input array , uses
temporarily and gives the result in
15
Initial Call:
Example
1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
16
Initial Call:
Example 1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
Step1: Initializing 𝑪[𝟎. . 𝒌] with 𝟎, 𝒌 = 𝟓
0 1 2 3 4 5
0 0 0 0 0 0
17
Initial Call:
Example 1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
Step2: counting each element 𝐀[𝒋] and update 𝑪[𝑨 𝒋 ] accordingally/
0 1 2 3 4 5
2 0 2 3 0 1
18
Initial Call:
Example 1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
Step3: update 𝑪 such that each 𝑪 𝒊 contains the number of elements
less than or equal to 𝒊
0 1 2 3 4 5
2 2 4 7 7 8
19
Initial Call:
Example 1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
Step4: find the correct position of each element of 𝑨 starting from the
end of the array, using info from 𝑪 and place it in its correct position at 𝑩
0 1 2 3 4 5
2 2 4 7 7 8
1 2 3 4 5 6 7 8
20
Initial Call:
Example 1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
Step4: find the correct position of each element of 𝑨 starting from the
end of the array, using info from 𝑪 and place it in its correct position at 𝑩
0 1 2 3 4 5
2 2 4 7 7 8
1 2 3 4 5 6 7 8
21
Initial Call:
Example 1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
Step5: update the value of 𝑪[𝑨 𝒋 ]
0 1 2 3 4 5
2 2 4 6 7 8
1 2 3 4 5 6 7 8
22
Initial Call:
Example 1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
Repeat Step4: find the correct position of each element of 𝑨 starting
from the end of the array, using info from 𝑪 and place it in its correct
position at 𝑩
0 1 2 3 4 5
2 2 4 6 7 8
1 2 3 4 5 6 7 8
0 3
23
Initial Call:
Example 1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
Repeat Step5: update the value of 𝑪[𝑨 𝒋 ]
0 1 2 3 4 5
1 2 4 6 7 8
1 2 3 4 5 6 7 8
0 3
24
Initial Call:
Example 1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
Repeat Step4: find the correct position of each element of 𝑨 starting
from the end of the array, using info from 𝑪 and place it in its correct
position at 𝑩
0 1 2 3 4 5
1 2 4 6 7 8
1 2 3 4 5 6 7 8
0 3 3
25
Initial Call:
Example 1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
Repeat Step5: update the value of 𝑪[𝑨 𝒋 ]
0 1 2 3 4 5
1 2 4 5 7 8
1 2 3 4 5 6 7 8
0 3 3
26
Initial Call:
Example 1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
Repeat Step4: find the correct position of each element of 𝑨 starting
from the end of the array, using info from 𝑪 and place it in its correct
position at 𝑩
0 1 2 3 4 5
1 2 4 5 7 8
1 2 3 4 5 6 7 8
0 2 3 3
27
Initial Call:
Example 1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
Repeat Step5: update the value of 𝑪[𝑨 𝒋 ]
0 1 2 3 4 5
1 2 3 5 7 8
1 2 3 4 5 6 7 8
0 2 3 3
28
Initial Call:
Example 1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
Repeat Step4: find the correct position of each element of 𝑨 starting
from the end of the array, using info from 𝑪 and place it in its correct
position at 𝑩
0 1 2 3 4 5
1 2 3 5 7 8
1 2 3 4 5 6 7 8
0 0 2 3 3
29
Initial Call:
Example 1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
Repeat Step5: update the value of 𝑪[𝑨 𝒋 ]
0 1 2 3 4 5
0 2 3 5 7 8
1 2 3 4 5 6 7 8
0 0 2 3 3
30
Initial Call:
Example 1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
Repeat Step4: find the correct position of each element of 𝑨 starting
from the end of the array, using info from 𝑪 and place it in its correct
position at 𝑩
0 1 2 3 4 5
0 2 3 5 7 8
1 2 3 4 5 6 7 8
0 0 2 3 3 3
31
Initial Call:
Example 1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
Repeat Step5: update the value of 𝑪[𝑨 𝒋 ]
0 1 2 3 4 5
0 2 3 4 7 8
1 2 3 4 5 6 7 8
0 0 2 3 3 3
32
Initial Call:
Example 1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
Repeat Step4: find the correct position of each element of 𝑨 starting
from the end of the array, using info from 𝑪 and place it in its correct
position at 𝑩
0 1 2 3 4 5
0 2 3 4 7 8
1 2 3 4 5 6 7 8
0 0 2 3 3 3 5
33
Initial Call:
Example 1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
Repeat Step5: update the value of 𝑪[𝑨 𝒋 ]
0 1 2 3 4 5
0 2 3 4 7 7
1 2 3 4 5 6 7 8
0 0 2 3 3 3 5
34
Initial Call:
Example 1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
Repeat Step4: find the correct position of each element of 𝑨 starting
from the end of the array, using info from 𝑪 and place it in its correct
position at 𝑩
0 1 2 3 4 5
0 2 3 4 7 7
1 2 3 4 5 6 7 8
0 0 2 2 3 3 3 5
35
Initial Call:
Example 1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
Repeat Step5: update the value of 𝑪[𝑨 𝒋 ]
0 1 2 3 4 5
0 2 2 4 7 7
1 2 3 4 5 6 7 8
0 0 2 2 3 3 3 5
36
Analyzing Counting Sort
Ο(1)
Ο(𝑘)
Ο(𝑛)
Ο(𝑘)
Ο(𝑛)
37
An Issue with Counting Sort
• Suppose we want to sort the following array using counting
sort.
329 457 657 839 436 720 355
• We need to create a HUGE auxiliary storage array to count
them since the range is large.
1 0 0 0 …….. 0 1
38
General Notes
• The counting sort is not sorting in place
• The output of the sort is placed in a new array 𝐵.
• Counting sort is a stable sort.
• Counting sort has linear time complexity.
• Counting sort is not a comparison sorting
algorithm.
39
Radix Sort
• Radix sort is the algorithm used by the card-sorting
machines you now find only in computer museums.
• Sorts numbers by sorting on the least significant digit
first.
• The algorithm used for sorting at digit level should be
stable.
• The algorithm takes the array to be sorted, and the
constant which is the max number of digits in the
input values.
40
Example
Initial Call:
329 457 657 839 436 720 355
41
Example
329 720 720 329
457 355 329 355
Counting Sort Counting Sort Counting Sort
657 436 436 436
839 457 839 457
436 657 355 657
720 329 457 720
355 839 657 839 42
Analyzing Radix Sort
• Each pass in the for loop takes
• We have passes
• When
Assuming is a constant
43
Summary of Sorting Algorithms
Algorithm Worst-Case Running Average-Case In-Place Stable
Time Running Time
Insertion Sort Θ 𝑛 Θ 𝑛 Y Y
Merge sort Θ 𝑛 lg 𝑛 Θ 𝑛 lg 𝑛 N Y
Comparison-
Quicksort Θ(𝑛 ) Θ(𝑛 lg 𝑛) Y N
based Sorts Randomized Quicksort Expected: Θ 𝑛 lg 𝑛 - Y N
BST-Sort Θ(𝑛 ) Θ(𝑛 lg 𝑛) Y Y
Heapsort 𝑂(𝑛 lg 𝑛) 𝑂(𝑛 lg 𝑛) Y N
Counting Sort Θ(𝑘 + 𝑛) Θ(𝑘 + 𝑛) N Y
Distribution- Radix Sort Θ 𝑑 𝑘+𝑛 Θ 𝑑 𝑘+𝑛 N Y
based Sorts
Bucket Sort Θ 𝑛 Θ 𝑛 N Y
44
Other Sorting Algorithms
• Bubble Sort
• Selection Sort
• Shell Sort
• Bitonic Sort
• Timsort
45
