CS计算机代考程序代写 decision tree algorithm Introduction

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, i0
Modify the algorithm to sort n integers in the range i-j, i1, not [0,1)?

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
0i
to k
2
0][ic

3 for
1j
to length[A]
4
1]][[]][[  jAcjAc

5 ► c[i] now contains the number
of elements equal to i

6 for
1i
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
1i
to n
3 insert
Ai[]
into
list
 
BnAi[]

4 for
0i
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