Lecture 07 Sorting and

Selection Algorithms

1
Learning Outcome
Merge-Sort
Summary of Sorting Algorithms
Radix-Sort
Quick-Select

2
In-Place Algorithms
An in-place algorithm produces its result by
overwriting the input data structure. It does not
require an additional temporary data structure
to store the result.
A not-in-place algorithm writes its temporary
result to an additional temporary data structure,
then use the temporary result to obtain the final
result and store the final result back to the
original data structure.
All sorting algorithms studied before this chapter
are in-place. They do not need a separate array
to store result.

3
Merge-Sort
Merge-Sort is a sorting algorithm based on the
divide-and-conquer paradigm
Like heap-sort
n It has O(n log n) running time
Unlike heap-sort
n It accesses data in a sequential manner (suitable to
sort data on a disk)
n It is stable
n It is not-in-place

4
Merge-Sort (cont.)
Merge-Sort on an input sequence S with n elements
consists of three steps:
n Divide: partition S into two sequences S1 and S2 of about
n/2 elements each
n Recur: recursively sort S1 and S2
n Conquer: merge S1 and S2 into a unique sorted sequence
Implementation of Merge-Sort that is performance
efficient requires a temporary data structure to
store the merged sequence in the Conquer step,
therefore making it a not-in-place algorithm.

5
Algorithm Merge-Sort
Algorithm Mergesort (a, p, r) {
Input Parameters: array a, start index p, end index r.
Output Parameter: array a sorted.
// continue if has more than one element.
if (p < r) {
// Divide: divide a into two nearly equal parts.
m = (p + r) / 2
// Recur: sort each half.
Mergesort (a, p, m)
Mergesort (a, m + 1, r)
// Conquer: merge the two sorted halves.
Merge (a, p, m, r)
}
}

6
Merging Two Sorted Sequences
The conquer step of Algorithm Merge (a, p, m, r)
merge-sort consists Input sequences A = a[p]…a[m] and
of merging two B = a[m+1]…a[r] with
sorted sequences A Output sorted sequence a[p]…a[r]
and B into a sorted
sequence S S  empty sequence
containing the while [Link]()  [Link]()
union of the if [Link]().element() <
elements of A and [Link]().element()
B
[Link]([Link]([Link]()))
Merging two sorted
else
sequences, each
with n/2 elements [Link]([Link]([Link]()))
and implemented while [Link]()
by means of a [Link]([Link]([Link]()))
doubly linked list, while [Link]()
takes O(n) time [Link]([Link]([Link]()))
return S
7
Merge-Sort Tree
An execution of merge-sort is depicted by a binary tree
n each node represents a recursive call of merge-sort and stores
w unsorted sequence before the execution and its partition
w sorted sequence at the end of the execution
n the root is the initial call
n the leaves are calls on subsequences of size 0 or 1

8
Merge-Sort Tree Example
Divide (Why not 7 2 9|4 3 8 6?)
7 2 9 43 8 6

9
Merge-Sort Tree Example (cont): step: recursive left for root, divide
7 2 9 43 8 6

7 29 4 3 8|6

10
Merge-Sort Tree Example (cont): step: recursive left for 7 2 | 9 4, divide
7 2 9 43 8 6

7 29 4 3 8|6

72 9|4

11
Merge-Sort Tree Example (cont): step: recursive left for 7, base case
7 2 9 43 8 6

7 29 4 3 8|6

72 9|4

12
Merge-Sort Tree Example (cont): step: recursive right for 2, base case
7 2 9 43 8 6

7 29 4 3 8|6

72 9|4

7 2

13
Merge-Sort Tree Example (cont): step: merge
7 2 9 43 8 6

7 29 4 3 8|6

72 9|4

7 2

2 7

14
Merge-Sort Tree Example (cont): step: recursive right for 9|4, divide
7 2 9 43 8 6

7 29 4 3 8|6

72 9|4

7 2 9 4

2 7

15
Merge-Sort Tree Example (cont): step: recursive left for 9, …, merge
7 2 9 43 8 6

7 29 4 3 8|6

72 9|4

7 2 9 4

2 7 4 9

16
Merge-Sort Tree Example (cont): step: merge
7 2 9 43 8 6

7 29 4 3 8|6

72 9|4

7 2 9 4

2 7 4 9

2 4 7 9

17
Merge-Sort Tree Example (cont): step: recursive right for 3 8 | 6, divide,
recursive left 3|8, divide 7 2 9 4  3 8 6

7 29 4 3 8|6

72 9|4 3|8 6

7 2 9 4 3 8

2 7 4 9

2 4 7 9

18
Merge-Sort Tree Example (cont): step: recursive left for 3, base case, …,
merge
7 2 9 43 8 6

7 29 4 3 8|6

72 9|4 3|8 6

7 2 9 4 3 8

2 7 4 9 3 8

2 4 7 9

19
Merge-Sort Tree Example (cont): step: recursive right for 6, base case,
merge
7 2 9 43 8 6

7 29 4 3 8|6

72 9|4 3|8 6

7 2 9 4 3 8

2 7 4 9 3 8

3 6 8
2 4 7 9

20
Merge-Sort Tree Example (final): step: merge
7 2 9 43 8 6

7 29 4 3 8|6

72 9|4 3|8 6

7 2 9 4 3 8

2 7 4 9 3 8

3 6 8
2 4 7 9

2 3 4 6 7 8 9
21
Array Output
The previous Merge-Sort tree and the following
array intermediate results are equivalent.
1. 7 2 9 4 3 8 6
2. 2 7 9 4 3 8 6
3. 2 7 4 9 3 8 6
4. 2 4 7 9 3 8 6
5. 2 4 7 9 3 8 6
6. 2 4 7 9 3 6 8
7. 2 3 4 6 7 8 9

22
Analysis of Merge-Sort
The height h of the merge-sort tree is O(log n)
n at each recursive call we divide in half the sequence,
The overall amount or work done at the nodes of depth i is O(n)
n we partition and merge 2i sequences of size n/2i
n we make 2i+1 recursive calls
Thus, the total running time of merge-sort is O(n log n)

dept #se size

1 2 n/2

i 2i n/2i

… … …
23
 Summary of Sorting Algorithms
Algorithm Time Notes
selection-sort O(n2) in-place, unstable
slow (good for small
inputs)
quick-sort O(n log n) in-place, unstable
fastest (good for large
O(n2) for worst case if inputs)
not randomized
heap-sort O(n log n) in-place, unstable
fast (good for large inputs)

merge-sort O(n log n) not in-place, stable

24
Bucket-Sort and Radix-Sort

1, c 3, a 3, b 7, d 7, g 7, e

B       
0 1 2 3 4 5 6 7 8 9

25
Bucket-Sort
Let S be a sequence of n (key, Algorithm bucketSort(S, N)
element) items with keys in the
Input sequence S of (key,
range [0, N-1]
element)
Bucket-sort uses the keys as items with keys in the range
indices into an auxiliary array B [0, N-1]
of sequences (buckets) Output sequence S sorted by
Phase 1: Empty sequence S by increasing keys
moving each item (k, o) into B  array of N empty sequences
its bucket B[k]
Phase 2: For i = 0, …, N-1, while [Link]()
move the items of bucket f  [Link]()
B[i] to the end of sequence (k, o)  [Link](f)
S
B[k].insertLast((k, o))
Analysis:
for i  0 to N-1
n Phase 1 takes O(n) time
while B[i].isEmpty()
n Phase 2 takes O(n + N) time
f  B[i].first()
Bucket-sort takes O(n + N)
time (k, o) 
B[i].remove(f)
26
[Link]((k, o))
Example
7, d 1, c 3, a 7, g 3, b 7, e
Key range [0, 7]
Phase 1

1, c 3, a 3, b 7, d 7, g 7, e

B     
0 1 2 3 4 5 6 7

Phase 2

1, c 3, a 3, b 7, d 7, g 7, e
27
Radix-Sort
Radix-sort is a
specialization of
lexicographic-sort that Algorithm radixSort(S, N)
uses bucket-sort as Input sequence S of d-tuples such
the stable sorting that (0, …, 0)  (x1, …, xd) and
algorithm in each (x1, …, xd)  (N-1, …, N-1)
dimension for each tuple (x1, …, xd) in S
Radix-sort is applicable to Output sequence S sorted in
tuples where the keys lexicographic order
in each dimension i for i  d downto 1
are integers in the bucketSort(S, N)
range [0, N-1]
Radix-sort runs in time
O(d( n + N))

28
Radix-Sort for
Binary Numbers
Consider a sequence of
binary numbers n of b-bit
x = xb - 1 … x1x0
We represent each element Algorithm binaryRadixSort(S)
as a b-tuple of numbers in Input sequence S of b-bit
numbers
the range [0, 1] and apply Output sequence S sorted
radix-sort with N = 2
replace each element x
This application of the radix- of S with the item (0, x)
sort algorithm runs in for i  0 to b - 1
O(bn) time replace the key k of
For example, we can sort a each item (k, x) of
sequence of 32-bit S with bit xi of x
integers in linear time bucketSort(S, 2)

29
Example
Sorting a sequence of 4-bit integers

1001 0010 1001 1001 0001

0010 1110 1101 0001 0010

1101 1001 0001 0010 1001

0001 1101 0010 1101 1101

1110 0001 1110 1110 1110

30
The Selection Problem
Given an integer k and n elements x1, x2, …, xn,
taken from a total order, find the k-th smallest
element in this set.
n Smallest, k = 0
Of course, we can sort the set in O(n log n) time
and then index the k-th element.
k=2 (3rd smallest) 77 44 99 22 66  22 44 66 77 99
Can we solve the selection problem faster? Let’s
say O(n).

31
Quick-Select
Quick-select is a randomized
selection algorithm based on
x
the prune-and-search
paradigm:
n Prune: pick a random element
x (called pivot) and partition
S into x
w L elements less than x
w E elements equal x
L E G
w G elements greater than x
k < |L| k > |L|+|E|
n Search: depending on k, either
answer is in E, or we need k’ = k - |L| - |E|
to recurse in either L or G
|L| < k < |L|+|E|
(done)
32
Algorithm Quick-Select
Input Parameters: array a, start index p, end index r,
target smallest k.
Output Parameter: a[pi] at the correct position.
QuickSelect (a, p, r, k) {
if (p <= r) {
pi = Partition (a, p, r) // pivot index.
if (k == pi)
return a[pi]
if (k < pi)
QuickSelect (a, p, pi-1, k)
else
QuickSelect (a, pi+1, r, k)
}
}

33
Partition
The partition step of Quick-Select is the same
partition in Quick-Sort which takes O(n) time.
Based on Probabilistic Facts, Quick-Select runs in
time O(n).
Quick-Select has the same worst case as Quick-Sort
which takes O(n2) time.

34
Quick-Select Visualization
Find 5th smallest number, hence k = 4
In this example, pivot is always the last element.

S=(77 99 22 66 55 44 11 88 33), call partition

pi=2, S=(22 11 33 77 99 66 55 44 88), k>pi, call partition on right

pi=7, S=(22 11 33 77 66 55 44 88 99), k<pi, call partition on left

pi=3, S=(22 11 33 44 77 66 55 88 99), k>pi, call partition on right

pi=4, S=(22 11 33 44 55 77 66 88 99), k=pi, stop

5th smallest = 55
35
 The End
Thank You

36