Introduction
Sorting in linear time
Chapter 8
Omit Section 8.1 and parts from other sections as stated in the slides
2
Comparison Sorts
Sorting by comparing pairs of numbers
Algorithms that sort n numbers in O(n2) time
Insertion, Selection, Bubble
Algorithms that sort n numbers in O(nlgn) time
Merge, Heap and Quick Sort
3
Comparison sort
Any comparison sort must make Ω(nlgn) comparisons.
(know this result but omit its proof in the following slides and section 8.1 of the text)
So nlgn is the most efficient they can be!
Now we will talk about three sorting algorithms – counting, radix and bucket – that are linear
So they must use a strategy other than comparing pairs of numbers.
4
Decision Trees (omit)
A representation of the comparisons a comparison sort algorithm makes
A full binary tree
Each node represents a comparison
Each child represents one of two cases of that comparison
Each leaf represents a sorted order
An execution of the algorithm: a path from the root to a leaf
5
Insertion Sort Decision Tree (omit)
The decision tree model
6
Decision Tree (omit)
Any correct sorting algorithm must be able to produce any permutation of its input…why?
So if a comparison sort is correct each of the n! permutations must be a leaf of its decision tree AND each of these leaves must be reachable by a path corresponding to an actual execution of the algorithm
7
(omit)
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
8
8.2 Counting sort
9
The operation of Counting-sort on an input array A[1..8]
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
10
Counting Sort Thinking Assignments
Modify the algorithm to sort n integers in the range i-j, i
Modify the algorithm to sort n integers in the range i-j, i
How will you modify step 3 of the algorithm with n buckets on slide 15 to accommodate real number input from some interval [i,j), not [0,1)?
a
1
:a
2
a
2
:a
3
a
1
:a
3
<1,2,3>
a
1
:a
3
<3,1,2>
<1,3,2>
a
2
:a
3
<2,1,3>
<3.2,1>
<2,3,1>
£
£
£
£
£
>
>
>
>
>
Theorem 9.1. Any decision tree that sorts n elements has
height
(log )n n
.
Proof:
).lg()!log(
,2!
nnnh
ln
h
Corollary 9.2 Heapsort and merge sort are asym ptotically
optimal comparisons.
).
lg
(
)
!
log(
,
2
!
n
n
n
h
l
n
h
W
=
³
£
£
Theorem 9.1. Any decision tree that sorts n elements has height
.
Proof:
Corollary 9.2 Heapsort and merge sort are asymptotically optimal comparisons.
_925889509.unknown
_1073737311.unknown
A
A
A
s
s
s
s
s
s
u
u
u
m
m
m
e
e
e
t
t
t
h
h
h
a
a
a
t
t
t
e
e
e
a
a
a
c
c
c
h
h
h
o
o
o
f
f
f
t
t
t
h
h
h
e
e
e
n
n
n
i
i
i
n
n
n
p
p
p
u
u
u
t
t
t
e
e
e
l
l
l
e
e
e
m
m
m
e
e
e
n
n
n
t
t
t
s
s
s
i
i
i
s
s
s
a
a
a
n
n
n
i
i
i
n
n
n
t
t
t
e
e
e
g
g
g
e
e
e
r
r
r
i
i
i
n
n
n
t
t
t
h
h
h
e
e
e
r
r
r
a
a
a
n
n
n
g
g
g
e
e
e
0
0
0
t
t
t
o
o
o
k
k
k
f
f
f
o
o
o
r
r
r
s
s
s
o
o
o
m
m
m
e
e
e
i
i
i
n
n
n
t
t
t
e
e
e
g
g
g
e
e
e
r
r
r
k
k
k
.
.
.
COUNTING_SORT( A,B,k)
1 for
0i
to k
2
0][ic
3 for
1j
to length[A]
4
1]][[]][[ jAcjAc
5 ► c[i] now contains the number
of elements equal to i
6 for
1i
to k
7
]1[][][ icicic
8 ► c[i] now contains the number of
elements less than or equal to i
9 for
][Alengthj
downto 1
10
][]]][[[ jAjAcB
11
1]][[]][[ jAcjAc
· Assume that each of the n input elements is an integer in the range 0 to k for some integer k.
0
=
i
0
]
[
=
i
c
1
=
j
1
]]
[
[
]]
[
[
+
=
j
A
c
j
A
c
COUNTING_SORT(A,B,k)
1
for
to k
2
3
for
to length[A]
4
5 ► c[i] now contains the number of elements equal to i
_1412062123.unknown
_1412062139.unknown
_1412062156.unknown
_1412062102.unknown
1
=
i
]
1
[
]
[
]
[
–
+
=
i
c
i
c
i
c
]
[
A
length
j
=
]
[
]]]
[
[
[
j
A
j
A
c
B
=
1
]]
[
[
]]
[
[
–
=
j
A
c
j
A
c
6
for
to k
7
8 ► c[i] now contains the number of elements less than or equal to i
9
for
downto 1
10
11
_1412062209.unknown
_1412062242.unknown
_1412062368.unknown
_1412062223.unknown
_1412062194.unknown
Analysis:
)( nk
Special case:
)(n
when
k On()
.
What if k ≫ n?
Counting sort is not an in-place algorithm.
Counting sort is
s
s
s
t
t
t
a
a
a
b
b
b
l
l
l
e
e
e
(numbers with the same value appear in the
output array in the same or der as they do in the input array.)
Thinking Assignment: Which other sorting algorithms that we have
discussed are stable?
)
(
n
k
+
Q
)
(
n
Q
Analysis:
Special case:
when
.
What if k ≫ n?
Counting sort is not an in-place algorithm.
Counting sort is stable (numbers with the same value appear in the output array in the same order as they do in the input array.)
Thinking Assignment: Which other sorting algorithms that we have discussed are stable?
_1284437303.unknown
_1284441375.unknown
_925895075.unknown
Why is it important that the sorting algorithm used by radix sort be
stable?
Radix sort is not an in-place algorithm. Why?
Lemma 8.3
Given n d-digit numbers in which each digit can take on up to k
possible values, RADIX -SORT correctly sorts these number in (d(n
+ k)) time if Counting Sort is used.
Omit Lemma 8.4 (p.199)
Why is it important that the sorting algorithm used by radix sort be stable?
Radix sort is not an in-place algorithm. Why?
Lemma 8.3
Given n d-digit numbers in which each digit can take on up to k possible values, RADIX-SORT correctly sorts these number in ((d(n + k)) time if Counting Sort is used.
Omit Lemma 8.4 (p.199)
BUCKET_SORT( A)
1
][Alengthn
2 for
1i
to n
3 insert
Ai[]
into
list
BnAi[]
4 for
0i
to n-1
5 sort list
Bi[]
with insertion sort
6 concatenate
B B Bn[],[],…,[ ]0 1 1
together in
order
]
[
A
length
n
=
1
=
i
0
=
i
BUCKET_SORT(A)
1
2
for
to n
3
insert
into
list
4
for
to n-1
5
sort list
with insertion sort
6
concatenate
together in
order
_925970636.unknown
_925970755.unknown
_1412062472.unknown
_1412062473.unknown
_1412062471.unknown
_925970707.unknown
_925970560.unknown
.
)
(
)
(
)
(
1
0
2
å
–
=
+
Q
=
n
i
i
n
O
n
n
T
/docProps/thumbnail.jpeg