Transcript Applied Combinatorics, 4th Ed. Alan Tucker

Applied Combinatorics, 4th Ed.
Alan Tucker
Section 3.4
Tree Analysis of Sorting Algorithms
Prepared by:
Nathan Rounds and
David Miller
7/20/2015
Tucker, Sec. 3.4
1
“Big O” Notation
− If we have a function f (x) defined
f (x) = 5x³ + x – 4,
we can approximate its value as a constant multiple of x³ for
large values of x, since 5x³ is the dominating term in the
function (it grows the fastest as x gets large).
− For x = 5, f (x) = 626 and the constant multiple 5(x³) = 625
which is a very close estimate.
− Therefore, we say that f (x) in “Big O” notation is O(x³).
7/20/2015
Tucker, Sec. 3.4
2
Theorem
• In the worst case, the number of binary
comparisons required to sort n items is at
least O(nlog2n).
• This number is a constant multiple of
(nlog2n) which approximates the height of a
binary testing tree (log2n!) for large values
of n.
7/20/2015
Tucker, Sec. 3.4
3
Bubble Sort
For m from 2 to n do:
For i from n (step-1) to m do:
If Ai  Ai-1, then interchange items Ai and Ai-1.
14
i=1
2416
i=2
m = 32
42613
i=3
ii ==324563
6231 i = 4
{
7/20/2015
325
i=5
52
i=6
Tucker, Sec. 3.4
This technique moves the
smallest number to the top,
then the next smallest
number below that until the
set of numbers is in
numerical order.
4
Bubble Sort Comparisons
• When m=2, I goes from n to 2, which means you have to do (n-1)
comparisons
• When m=3, I goes from n to 3, which means you have to do (n-2)
comparisons
• Continuing this trend, the total number of comparisons must be:
 n  1   n  2    1 
n 1
i 
i 1
n  n  1
2

1
2
n2  1 2 n
 
2
This shows that the Bubble Sort method will require O n comparisons, which is more
then the theoretical bound of O  n log 2 n  .
7/20/2015
Tucker, Sec. 3.4
5
Merge Sort – Setup
• Roughly splits the set in half, until only single elements are left.
54092 67138
540 92
54 0
671 38
67 1
9 2
0
2
9
3 8
1
8
3
5 4
6 7
5
4
7/20/2015
6
Tucker, Sec. 3.4
7
6
Merge Sort - Ordering
• The set then gets “merged” into numerical order.
5
4
6
0
9
45
3
1
2
29
045
7
67
8
38
167
02459
13678
Note: The root of
the tree
is on the bottom
0123456789
7/20/2015
Tucker, Sec. 3.4
7
Complexity of Merging
• Assume that every set has n = 2r elements
– There are r levels
– There are 2k vertices on level k
– On level k, each set will have 2r-k elements
n=
24
++++++++++++++++
++++++++
++++
++++
++ ++ ++ ++
Level 0
++++++++
++++
++++
++ ++ ++ ++
+ +++++++ ++++ ++ + +
7/20/2015
Tucker, Sec. 3.4
Level 1
Level 2
Level 3
Level 4
8
Merge Sort Comparisons
• In general, at each vertex on level k two ordered sublists of 2r-k-1 items
are merged into an ordered sublist of 2r-k items
• This merging requires 2r-k-1 comparisons
• The two ordered sublists on level one merge into the root
• The number of comparisons needed at level k is 2k (2r-k – 1 ) = 2r - 2k
since there are 2k different vertices
• Totaling the number of comparisons needed for a Merge Sort is:
r 1
r 1
r 1
k
r
r
2

2

2

2

r
2

2
 1


 
r
k 0
k
r
k 0
k 0
• With n = 2r this becomes:  log 2 n  n   n  1
• This shows that Merge Sort method requires O  n log 2 n 
comparisons, which achieves the theoretical bound of a binary search.
7/20/2015
Tucker, Sec. 3.4
9
QUIK Sort
• Takes the first element and compares it with the other elements to
divide the list, putting smaller elements into a set on the left and the
larger elements into a set on the right.
5407168239
76 89
401235
01234
5
67
2134
12
7/20/2015
6
89
7
8
9
Once an element is alone
there is no need to continue
to divide it
34
0
1
Puts the first element
at the end of the left list
2
3
4
Tucker, Sec. 3.4
10
Heap Sort
• A binary tree so that the parent is always
bigger than its children
Put the root at the beginning of a list,
then move up the next biggest grandchildren.
6
LIST:
5
3
4
0
7/20/2015
2
1
Tucker, Sec. 3.4
11
Class Exercise
• Sort the following set of numbers using a
bubble sort and then do it using a merge
sort.
S  5,3,8,23, 6,0,2,66
• Which sort technique is more efficient for
this set?
7/20/2015
Tucker, Sec. 3.4
12
Bubble Sort Solution
5
5
5
5
-6
-6
-6
-6
-6
3
3
3
-6
5
0
0
0
0
8
8
-6
3
3
5
5
2
2
23
-6
8
8
8
3
2
5
3
-6
23
23
23
23
2
3
3
5
0
0
0
0
0
8
8
8
8
2
2
2
2
2
23
23
23
23
66
66
66
66
66
. . . 66
66
66
66
7/20/2015
Tucker, Sec. 3.4
13
Merge Sort Solution
5 3 8 23 -6 0 2 66
5 3 8 23
7/20/2015
-6 0
8 23
5 3
5
-6 0 2 66
3
8
23
-6
Tucker, Sec. 3.4
2 66
0
2
66
14
Merge Sort Solution cont’d
3
5
23
8
35
8 23
-6
0
-6 0
3 5 8 23
66
2
2 66
-6 0 2 66
-6 0 2 3 5 8 23 66
7/20/2015
Tucker, Sec. 3.4
15
Something to Ponder
• How does one create an initial heap to
perform a heap sort on?
• This will be on the homework. 
7/20/2015
Tucker, Sec. 3.4
16