Transcript chap10

Chapter 10
Sorting Algorithms
Data Structures Using C++
1
Chapter Objectives
• Learn the various sorting algorithms
• Explore how to implement the selection,
insertion, quick, merge, and heap sorting
algorithms
• Discover how the sorting algorithms
discussed in this chapter perform
Data Structures Using C++
2
Selection Sort
•
Sorts list by
1. Finding smallest (or equivalently largest)
element in the list
2. Moving it to the beginning (or end) of the list
by swapping it with element in beginning (or
end) position
Data Structures Using C++
3
Smallest Element in List
Function
template<class elemType>
int orderedArrayListType<elemType>::minLocation(int
first, int last)
{
int loc, minIndex;
minIndex = first;
for(loc = first + 1; loc <= last; loc++)
if(list[loc] < list[minIndex])
minIndex = loc;
return minIndex;
}//end minLocation
Data Structures Using C++
4
Swap Function
template<class elemType>
void orderedArrayListType<elemType>::swap(int first, int
second)
{
elemType temp;
temp = list[first];
list[first] = list[second];
list[second] = temp;
}//end swap
Data Structures Using C++
5
Selection Sort Function
template<class elemType>
void orderedArrayListType<elemType>::selectionSort()
{
int loc, minIndex;
for(loc = 0; loc < length - 1; loc++)
{
minIndex = minLocation(loc, length - 1);
swap(loc, minIndex);
}
}
Data Structures Using C++
6
Selection Sort Example:
Array-Based Lists
Data Structures Using C++
7
Selection Sort Example:
Array-Based Lists
Data Structures Using C++
8
Selection Sort Example:
Array-Based Lists
Data Structures Using C++
9
Selection Sort Example:
Array-Based Lists
Data Structures Using C++
10
Analysis: Selection Sort
By analyzing the number of key comparisons, we
see that selection sort is an O(n2) algorithm:
Data Structures Using C++
11
Insertion Sort
• Reduces number of key comparisons made
in selection sort
• Can be applied to both arrays and linked
lists (examples follow)
• Sorts list by
– Finding first unsorted element in list
– Moving it to its proper position
Data Structures Using C++
12
Insertion Sort: Array-Based Lists
Data Structures Using C++
13
Insertion Sort: Array-Based Lists
Data Structures Using C++
14
Insertion Sort: Array-Based Lists
Data Structures Using C++
15
Insertion Sort: Array-Based Lists
Data Structures Using C++
16
Insertion Sort: Array-Based Lists
for(firstOutOfOrder = 1; firstOutOfOrder < length; firstOutOfOrder++)
if(list[firstOutOfOrder] is less than list[firstOutOfOrder - 1])
{
copy list[firstOutOfOrder] into temp
initialize location to firstOutOfOrder
do
{
a. move list[location - 1] one array slot down
b. decrement location by 1 to consider the next element
of the sorted portion of the array
}
while(location > 0 && the element in the upper sublist at
location - 1 is greater than temp)
}
copy temp into list[location]
Data Structures Using C++
17
Insertion Sort: Array-Based Lists
Data Structures Using C++
18
Insertion Sort: Array-Based Lists
Data Structures Using C++
19
Insertion Sort: Array-Based Lists
template<class elemType>
void orderedArrayListType<elemType>::insertionSort()
{
int firstOutOfOrder, location;
elemType temp;
for(firstOutOfOrder = 1; firstOutOfOrder < length;
firstOutOfOrder++)
if(list[firstOutOfOrder] < list[firstOutOfOrder - 1])
{
temp = list[firstOutOfOrder];
location = firstOutOfOrder;
do
{
list[location] = list[location - 1];
location--;
} while(location > 0 && list[location - 1] > temp);
list[location] = temp;
}
}//end insertionSort
Data Structures Using C++
20
Insertion Sort: Linked List-Based
Data Structures Using C++
21
Insertion Sort: Linked List-Based
if(firstOutOfOrder->info is less than first->info)
move firstOutOfOrder before first
else
{
set trailCurrent to first
set current to the second node in the list
//search the list
while(current->info is less than firstOutOfOrder->info)
{
advance trailCurrent;
advance current;
}
if(current is not equal to firstOutOfOrder)
{
//insert firstOutOfOrder between current and trailCurrent
lastInOrder->link = firstOutOfOrder->link;
firstOutOfOrder->link = current;
trailCurrent->link = firstOutOfOrder;
}
else
//firstOutOfOrder is already at the first place
lastInOrder = lastInOrder->link;
}
Data Structures Using C++
22
Analysis: Insertion Sort
What are worst case complexities of each? Best case?
Data Structures Using C++
23
Lower Bound on ComparisonBased Sort Algorithms
• Trace execution of comparison-based algorithm by using
graph called comparison tree
• Let L be a list of n distinct elements, where n > 0. For any j
and k, either L[j] < L[k] or L[j] > L[k]
• Each comparison of the keys has two outcomes;
comparison tree is a binary tree
• Each comparison is a node
• Node is labeled as j:k, representing comparison of L[j] with
L[k]
• If L[j] < L[k], follow the left branch; otherwise, follow the
right branch
Data Structures Using C++
24
Lower Bound on ComparisonBased Sort Algorithms
Data Structures Using C++
25
Lower Bound on ComparisonBased Sort Algorithms
• Each leaf represents a different final ordering of the input
– n inputs implies n! leaves
• Since any initial ordering of inputs is possible, all paths
through comparison tree are possible
– Worst-case number of comparisons = length of longest path from
root to any leaf
• Binary tree of height h has at most 2h nodes, so 2h > n!
• Thus h > log2 n! > log2 (n/3)n = n log2 (n/3) = Ω(n log n)
• Theorem: Let L be a list of n distinct elements. Any
sorting algorithm that sorts L by comparison of the keys
only, in the worst case, makes at least Ω(n log n) key
comparisons
Data Structures Using C++
26
Quick Sort
• Recursive algorithm
• Uses “divide-and-conquer”
• List L is partitioned into two sublists, and the two
sublists are then sorted and combined into one list
in such a way so that the combined list is sorted
– Choose a pivot element to partition the list such that
everything in the “lower” list is < pivot and everything
in the “upper” list is > pivot
– Once lower and upper lists are sorted, L is sorted
trivially
Data Structures Using C++
27
Quick Sort: Array-Based Lists
Data Structures Using C++
28
Quick Sort: Array-Based Lists
1.
Start with pivot=0 (first position), smallIndex=0, index=1
2.
Loop index through the list
a.
3.
If L[index] < L[pivot], increment smallIndex and swap
L[index] with L[smallIndex]
Swap L[pivot] with L[smallIndex]
Data Structures Using C++
29
Quick Sort: Array-Based Lists
pivot
smallIndex index
Data Structures Using C++
30
Quick Sort: Array-Based Lists
Data Structures Using C++
31
Quick Sort: Array-Based Lists
Data Structures Using C++
32
Quick Sort: Array-Based Lists
Data Structures Using C++
33
Quick Sort: Array-Based Lists
template<class elemType>
int orderedArrayListType<elemType>::partition(int
first, int last)
{
elemType pivot;
int index, smallIndex;
swap(first, (first + last)/2);
pivot = list[first];
smallIndex = first;
for(index = first + 1; index <= last; index++)
if(list[index] < pivot)
{
smallIndex++;
swap(smallIndex, index);
}
swap(first, smallIndex);
return smallIndex;
}
Data Structures Using C++
34
Quick Sort: Array-Based Lists
template<class elemType>
void orderedArrayListType<elemType>::swap(int first,int
second)
{
elemType temp;
temp = list[first];
list[first] = list[second];
list[second] = temp;
} //end swap
Data Structures Using C++
35
Quick Sort: Array-Based Lists
template<class elemType>
void orderedArrayListType<elemType>::recQuickSort(int
first, int last)
{
int pivotLocation;
if(first <last)
{
pivotLocation = partition(first, last);
recQuickSort(first, pivotLocation - 1);
recQuickSort(pivotLocation + 1, last);
}
} //end recQuickSort
template<class elemType>
void orderedArrayListType<elemType>::quickSort()
{
recQuickSort(0, length - 1);
}//end quickSort
Data Structures Using C++
36
Quick Sort Analysis
Data Structures Using C++
37
Merge Sort
• Uses the divide-and-conquer technique to
sort a list
• Merge sort algorithm also partitions the list
into two sublists, sorts the sublists, and then
combines the sorted sublists into one sorted
list
– Merging two sorted lists into a single sorted list
is easy and fast
Data Structures Using C++
38
Merge Sort Algorithm
Data Structures Using C++
39
Divide
Data Structures Using C++
40
Divide
Data Structures Using C++
41
Merge
Data Structures Using C++
42
Merge
Data Structures Using C++
43
Analysis of Merge Sort
Suppose that L is a list of n elements, where n > 0.
Let A(n) denote the number of key comparisons in
the average case, and W(n) denote the number of key
comparisons in the worst case to sort L. It can be
shown that:
A(n) = n log2 n – 1.26 n = O(n log n)
W(n) = n log2 n – (n – 1) = O(n log n)
Data Structures Using C++
44
Heap Sort
• Definition: A heap is a list in which each element
contains a key, such that the key in the element at
position k in the list is at least as large as the key
in the element at position 2k + 1 (if it exists), and
2k + 2 (if it exists)
– Can also represent as a binary tree where a node is >
than both its children
• Heap sort builds a heap out of a list (bottom-up),
then pulls (max) items off the top, one at a time
Data Structures Using C++
45
Heap Sort: Array-Based Lists
Data Structures Using C++
46
Heap Sort: Array-Based Lists
Check if
heap
Data Structures Using C++
47
Heap Sort: Array-Based Lists
Data Structures Using C++
48
Heap Sort: Array-Based Lists
Data Structures Using C++
49
Heap Sort: Array-Based Lists
Data Structures Using C++
50
Heap Sort: Array-Based Lists
Data Structures Using C++
51
Heapsort
1. Start with array A of size n, and “heapify”
it
a. Where is A’s max value now?
2. Swap max with last element
3. Return to step 1, using only the first n-1
elements
Data Structures Using C++
52