Transcript CSC 2500 Computer Organization

CSC 2300
Data Structures & Algorithms
March 20, 2007
Chapter 7. Sorting
Today – Sorting

Heapsort –




Mergesort –



Algorithm
Analysis
Lower bound
Algorithm
Worst case
Quicksort –

Algorithm
Heapsort – Algorithm










What time bound can we get if we use a heap?
We want to sort N integers.
We build a binary heap of N elements.
How much time does buildHeap take?
We then perform N deleteMin operations.
The elements leave the heap smallest first, in sorted order.
By recording these elements in a second array and then
copying them back, we sort N elements.
How much time does each deleteMin take?
What is the total running time?
What is a problem with Heapsort?
Heapsort – Space




The algorithm uses an extra array.
Thus, the memory requirement is doubled.
What about the work to copy the second array back to the first?
How do we solve the problem of space?
Heapsort – Saving Space





After each deleteMin, the heap shrinks by 1.
Thus, the cell that was last in the heap can be used to store the
element that was just deleted.
If we use this strategy, the array will contain the elements in
what sorted order?
We usually want the elements in increasing sorted order.
What should we do?
Max Heap



Use a max heap.
Build the heap in linear time.
Then perform N – 1 deleteMax operations.
Heapsort

Note: the array for
heapsort contains
data in position 0,
unlike before, where
the index starts at 1.
Heapsort – Performance






Experiments show that the performance of heapsort is
extremely consistent.
On average, heapsort uses only slightly fewer comparisons
than suggested by the worst-case bound.
Why?
It appears that successive deleteMax operations destroy the
randomness of the heap.
Can you suggest another O(N log N) sorting scheme?
What do you think about when you see O(N log N)?
Mergesort





A recursive algorithm!
O(N log N) worst-case running time.
We can show that the number of comparisons is nearly optimal.
The fundamental operation is to merge two sorted lists.
Since the lists are sorted, the merging can be done in one pass
through the input, if the output is put in a third list.
Mergesort – Example





We will go through an example in class.
Try this:
A:
1, 13, 24, 26, 35, 44, 52, 68
B:
2, 15, 27, 28, 47, 66, 72, 75
C:
Merging two sorted lists with a total of N elements takes
at most N – 1 comparisons.
Why only N – 1?
Every comparison adds an element to C, except the last
comparison, which adds at least two elements.
Mergesort – Routines

No base case in
recursive routine?
Merge – Routine
Mergesort – Analysis





Assume that N is a power of 2.
For N = 1, the time to mergesort is constant, which we denote by 1.
Otherwise, the time to mergesort N numbers is equal to the time to
do two recursive mergesorts of size N/2, plus the time to merge,
which is linear.
Hence
T(1) = 1
T(N) = 2T(N/2) + N
Does anyone remember how to solve this recurrence?
Mergesort – Recurrence

Recurrence:
T(N) = 2T(N/2) + N




Divide by N:
T(N)/N = T(N/2)/(N/2) + 1
What do we assume about the value of N?
We get:
T(N)/N = T(1)/1 + log N
Thus,
T(N) = N log N + N = O(N log N)
Quicksort – Description





Fastest generic sorting algorithm in practice.
Average running time is O(N log N).
What is worst-case running time bound?
O(N2).
We may make the O(N2) bound very unlikely with just
a little effort on choosing the pivot.
Quicksort – Algorithm
1.
2.
3.
4.
If the number of elements in S is 0 or 1, then return.
Pick any element v in S. This is called the pivot.
Partition S – {v} into two disjoint groups:
S1 = { x ε S – {v} | x ≤ v}
and
S2 = { x ε S – {v} | x ≥ v}.
Return { quicksort(S1) followed by v followed by quicksort(S2)}.
Quicksort – Example
Quicksort – Partition Strategy








Example. Input: 8, 1, 4, 9, 6, 3, 5, 2, 7, 0. Say 6 is chosen as pivot.
8
1
4
9
0
3
5
2
7
6
i
j
pivot
8
1
4
9
0
3
5
2
7
6
i
j
2
1
4
9
0
3
5
8
7
6
i
j
2
1
4
9
0
3
5
8
7
6
i
j
2
1
4
5
0
3
9
8
7
6
i
j
2
1
4
5
0
3
9
8
7
6
j
i
pivot
2
1
4
5
0
3
6
8
7
9
pivot
i