Merge sort, Insertion sort Sorting I / Slide 2 Sorting Selection sort or bubble sort Find the minimum value in the list 2. Swap it with the value in the first position 3. Repeat the steps above for remainder of the list (starting at the second position) 1.
Insertion sort Merge sort Quicksort Shellsort Heapsort Topological sort Sorting I / Slide 3 Bubble sort and analysis for (i=0; i
Worst-case analysis: N+N-1+ +1= N(N+1)/2, so O(N^2) Sorting I / Slide 4 Insertion: Incremental algorithm principle Mergesort: Divide and conquer principle
Sorting I / Slide 5 Insertion sort 1) Initially p = 1 2) Let the first p elements be sorted. 3) Insert the (p+1)th element properly in the list (go inversely from right to left) so that now p+1 elements are sorted. 4) increment p and go to step (3) Sorting I / Slide 6 Insertion Sort Sorting I / Slide 7 Insertion Sort http://www.cis.upenn.edu/~matuszek/cse121-2003/Applets/Chap03/Insertion/InsertSort.html
Consists of N - 1 passes For pass p = 1 through N - 1, ensures that the elements in positions 0 through p are in sorted order elements in positions 0 through p - 1 are already sorted move the element in position p left until its correct place is found among the first p + 1 elements Sorting I / Slide 8 Extended Example To sort the following numbers in increasing order: 34 8 64 51 32 21 p = 1; tmp = 8; 34 > tmp, so second element a[1] is set to 34: {8, 34} We have reached the front of the list. Thus, 1st position a[0] = tmp=8 After 1st pass: 8 34 64 51 32 21
(first 2 elements are sorted) Sorting I / Slide 9 P = 2; tmp = 64; 34 < 64, so stop at 3rd position and set 3rd position = 64 After 2nd pass: 8 34 64 51 32 21 (first 3 elements are sorted) P = 3; tmp = 51; 51 < 64, so we have 8 34 64 64 32 21, 34 < 51, so stop at 2nd position, set 3rd position = tmp, After 3rd pass: 8 34 51 64 32 21 (first 4 elements are sorted) P = 4; tmp = 32, 32 < 64, so 8 34 51 64 64 21, 32 < 51, so 8 34 51 51 64 21, next 32 < 34, so 8 34 34, 51 64 21, next 32 > 8, so stop at 1st position and set 2nd position = 32, After 4th pass: 8 32 34 51 64 21 P = 5; tmp = 21, . . . After 5th pass: 8 21 32 34 51
64 Analysis: worst-case running time Sorting I / Slide 10 Inner loop is executed p times, for each p=1..N Overall: 1 + 2 + 3 + . . . + N = O(N2) Space requirement is O(N) Sorting I / Slide 11 The bound is tight
The bound is tight (N2) That is, there exists some input which actually uses (N2) time Consider input as a reversed sorted list When a[p] is inserted into the sorted a[0..p-1], we need to compare a[p] with all elements in a[0..p-1] and move each element one position to the right (i) steps the total number of steps is (1N-1 i) = (N(N-1)/2) = (N2) Sorting I / Slide 12 Analysis: best case
The input is already sorted in increasing order When inserting A[p] into the sorted A[0..p-1], only need to compare A[p] with A[p-1] and there is no data movement For each iteration of the outer for-loop, the inner for-loop terminates after checking the loop condition once => O(N) time If input is nearly sorted, insertion sort runs fast Sorting I / Slide 13 Summary on insertion sort
Simple to implement Efficient on (quite) small data sets Efficient on data sets which are already substantially sorted More efficient in practice than most other simple O(n2) algorithms such as selection sort or bubble sort: it is linear in the best case Stable (does not change the relative order of elements with equal keys) In-place (only requires a constant amount O(1) of extra memory space) It is an online algorithm, in that it can sort a list as it receives it. Sorting I / Slide 14
An experiment Code from textbook (using template) Unix time utility Sorting I / Slide 15 Sorting I / Slide 16 Mergesort Based on divide-and-conquer strategy Divide the list into two smaller lists of about equal sizes Sort each smaller list recursively
Merge the two sorted lists to get one sorted list Sorting I / Slide 17 Mergesort Divide-and-conquer strategy recursively mergesort the first half and the second half merge the two sorted halves together Sorting I / Slide 18 http://www.cosc.canterbury.ac.nz/people/mukundan/dsal/MSort.html Sorting I / Slide 19
How do we divide the list? How much time needed? How do we merge the two sorted lists? How much time needed? Sorting I / Slide 20 How to divide? If an array A[0..N-1]: dividing takes O(1) time we can represent a sublist by two integers left and right: to divide A[left..Right], we compute center=(left+right)/2 and obtain A[left..Center] and A[center+1..Right] Sorting I / Slide 21
How to merge? Input: two sorted array A and B Output: an output sorted array C Three counters: Actr, Bctr, and Cctr initially set to the beginning of their respective arrays (1) The smaller of A[Actr] and B[Bctr] is copied to the next entry in C, and the appropriate counters are advanced (2) When either input list is exhausted, the remainder of the other list is copied to C Sorting I / Slide 22 Example: Merge
Sorting I / Slide 23 Example: Merge... Running time analysis: Clearly, merge takes O(m1 + m2) where m1 and m2 are the sizes of the two sublists. Space requirement: merging two sorted lists requires linear extra memory additional work to copy to the temporary array and back
Sorting I / Slide 24 Sorting I / Slide 25 Analysis of mergesort Let T(N) denote the worst-case running time of mergesort to sort N numbers. Assume that N is a power of 2. Divide step: O(1) time Conquer step: 2 T(N/2) time Combine step: O(N) time Recurrence equation: T(1) = 1 T(N) = 2T(N/2) + N Sorting I / Slide 26
Analysis: solving recurrence N )N 2 N N 2(2T ( ) ) N 4 2 N 4T ( ) 2 N 4 N N 4(2T ( ) ) 2 N 8 4 N 8T ( ) 3 N 8 N
k 2 T ( k ) kN 2 T ( N ) 2T ( Since N=2k, we have k=log2 n N T ( N ) 2 T ( k ) kN 2 N N log N O( N log N ) k Sorting I / Slide 27 Dont forget: We need an additional array for merge! So its not in-place! Quicksort
Sorting I / Slide 29 Introduction Fastest known sorting algorithm in practice Average case: O(N log N) (we dont prove it) Worst case: O(N2) But, the worst case seldom happens. Another divide-and-conquer recursive algorithm, like mergesort Sorting I / Slide 30
Quicksort Divide step: v Pick any element (pivot) v in S Partition S {v} into two disjoint groups S1 = {x S {v} | x <= v} S2 = {x S {v} | x v} S Conquer step: recursively sort S1 and S2 v
Combine step: the sorted S1 (by the time returned from recursion), followed by v, followed by the sorted S2 (i.e., nothing extra needs to be done) S1 S2 To simplify, we may assume that we dont have repetitive elements, So to ignore the equality case! Sorting I / Slide 31 Example Sorting I / Slide 32 Sorting I / Slide 33
Pseudo-code Input: an array a[left, right] QuickSort (a, left, right) { if (left < right) { pivot = Partition (a, left, right) Quicksort (a, left, pivot-1) Quicksort (a, pivot+1, right) } } Compare with MergeSort: MergeSort (a, left, right) { if (left < right) { mid = divide (a, left, right) MergeSort (a, left, mid-1) MergeSort (a, mid+1, right) merge(a, left, mid+1, right) } } Sorting I / Slide 34
Two key steps How to pick a pivot? How to partition? Sorting I / Slide 35 Pick a pivot Use the first element as pivot if the input is random, ok if the input is presorted (or in reverse order)
all the elements go into S2 (or S1) this happens consistently throughout the recursive calls Results in O(n2) behavior (Analyze this case later) Choose the pivot randomly generally safe random number generation can be expensive Sorting I / Slide 36 In-place Partition If use additional array (not in-place) like MergeSort
Straightforward to code like MergeSort (write it down!) Inefficient! Many ways to implement Even the slightest deviations may cause surprisingly bad results. Not stable as it does not preserve the ordering of the identical keys. Hard to write correctly Sorting I / Slide 37 An easy version of in-place partition to understand,
but not the original form int partition(a, left, right, pivotIndex) { pivotValue = a[pivotIndex]; swap(a[pivotIndex], a[right]); // Move pivot to end // move all smaller (than pivotValue) to the begining storeIndex = left; for (i from left to right) { if a[i] < pivotValue swap(a[storeIndex], a[i]); storeIndex = storeIndex + 1 ; } swap(a[right], a[storeIndex]); // Move pivot to its final place return storeIndex; } Look at Wikipedia Sorting I / Slide 38 quicksort(a,left,right) { if (right>left) {
pivotIndex = left; select a pivot value a[pivotIndex]; pivotNewIndex=partition(a,left,right,pivotIndex); quicksort(a,left,pivotNewIndex-1); quicksort(a,pivotNewIndex+1,right); } } Sorting I / Slide 39 A better partition Want to partition an array A[left .. right] First, get the pivot element out of the way by swapping it with the last element. (Swap pivot and A[right]) Let i start at the first element and j start at the next-to-last element (i = left, j = right 1)
swap 5 6 4 6 pivot 3 12 19 5 i 6 4 19 3 12
j 6 Sorting I / Slide 40 Want to have A[x] <= pivot, for x < i A[x] >= pivot, for x > j <= pivot When i < j >= pivot
j i Move i right, skipping over elements smaller than the pivot Move j left, skipping over elements greater than the pivot When both i and j have stopped A[i] >= pivot A[j] <= pivot 5 i 6 4 19 3 12
j 6 5 6 i 4 19 3 12 j 6 Sorting I / Slide 41 When i and j have stopped and i is to the left of j
Swap A[i] and A[j] The large element is pushed to the right and the small element is pushed to the left After swapping A[i] <= pivot A[j] >= pivot Repeat the process until i and j cross swap 5
6 i 4 19 3 12 j 6 5 3 i 4 19 6 12 j
6 Sorting I / Slide 42 When i and j have crossed 5 4 19 6 12 6 Swap A[i] and pivot
Result: 3 A[x] <= pivot, for x < i A[x] >= pivot, for x > i j i 5 5 3 3 4 19 6 12
6 j i 4 6 6 12 19 j i (put the pivot on the leftmost Sorting I Implementation / Slide 43 void quickSort(int array[], int start, int end) instead of rightmost)
{ int i = start; // index of left-to-right scan int k = end; // index of right-to-left scan if (end - start >= 1) // check that there are at least two elements to sort { int pivot = array[start]; // set the pivot as the first element in the partition while (k > i) // while the scan indices from left and right have not met, { while (array[i] <= pivot && i <= end && k > i) i++; // from the left, look for t // element greater than the while (array[k] > pivot && k >= start && k >= i) // from the right, look for t k--; if (k > i) // element not greater than // if the left seekindex is
swap(array, i, k); // the right index, // swap the corresponding el } swap(array, start, k); // after the indices have cr // swap the last element in // the left partition with t quickSort(array, start, k - 1); // quicksort the left partit quickSort(array, k + 1, end); // quicksort the right parti }
else // if there is only one element in the partition, do not do any sorting Adapted from http://www.mycsresource.net/articles/programming/sorting_algo { return; // the array is sorted, so exit Sorting I / Slide 44 void quickSort(int array[]) // pre: array is full, all elements are non-null integers // post: the array is sorted in ascending order { quickSort(array, 0, array.length - 1); // quicksort all the elements in the arr } void quickSort(int array[], int start, int end) { } void swap(int array[], int index1, int index2) {} // pre: array is full and index1, index2 < array.length
// post: the values at indices 1 and 2 have been swapped Sorting I / Slide 45 With duplicate elements Partitioning so far defined is ambiguous for duplicate elements (the equality is included for both sets) Its randomness makes a balanced distribution of duplicate elements When all elements are identical: both i and j stop many swaps but cross in the middle, partition is balanced (so its n log
n) Sorting I / Slide 46 A better Pivot Use the median of the array Partitioning always cuts the array into roughly half An optimal quicksort (O(N log N)) However, hard to find the exact median (chickenegg?) e.g., sort an array to pick the value in the middle Approximation to the exact median:
Sorting I / Slide 47 Median of three We will use median of three Compare just three elements: the leftmost, rightmost and center Swap these elements if necessary so that A[left] A[right] A[center] = =
= Smallest Largest Median of three Pick A[center] as the pivot Swap A[center] and A[right 1] so that pivot is at second last position (why?) median3 Sorting I / Slide 48 2 5 6 4 13 3 12 19 6
A[left] = 2, A[center] = 13, A[right] = 6 2 5 6 4 6 3 12 19 13 Swap A[center] and A[right] 2 5
6 4 6 3 12 19 13 Choose A[center] as pivot pivot 2 5 6 4 19 3 12 6 13 Swap pivot and A[right 1]
pivot Note we only need to partition A[left + 1, , right 2]. Why? Sorting I / Slide 49 Works only if pivot is picked as median-of-three. A[left] <= pivot and A[right] >= pivot Thus, only need to partition A[left + 1, , right 2] j will not run past the beginning
because a[left] <= pivot i will not run past the end because a[right-1] = pivot The coding style is efficient, but hard to read Sorting I / Slide 50 i=left; j=right-1; while (1) { do i=i+1; while (a[i] < pivot); do j=j-1; while (pivot < a[j]); if (i
} Sorting I / Slide 51 Small arrays For very small arrays, quicksort does not perform as well as insertion sort how small depends on many factors, such as the time spent making a recursive call, the compiler, etc Do not use quicksort recursively for small arrays
Instead, use a sorting algorithm that is efficient for small arrays, such as insertion sort Sorting I / Slide 52 A practical implementation Choose pivot Partitioning Recursion For small arrays Sorting I / Slide 53 Quicksort Analysis Assumptions:
Running time A random pivot (no median-of-three partitioning) No cutoff for small arrays pivot selection: constant time, i.e. O(1) partitioning: linear time, i.e. O(N) running time of the two recursive calls T(N)=T(i)+T(N-i-1)+cN where c is a constant i: number of elements in S1
Sorting I / Slide 54 Worst-Case Analysis What will be the worst case? The pivot is the smallest element, all the time Partition is always unbalanced Sorting I / Slide 55 Best-case Analysis What will be the best case?
Partition is perfectly balanced. Pivot is always in the middle (median of the array) Sorting I / Slide 56 Average-Case Analysis Assume Each of the sizes for S1 is equally likely This assumption is valid for our pivoting (median-of-three) strategy On average, the running time is O(N log N)
(covered in comp271) Sorting I / Slide 57 Quicksort is faster than Mergesort Both quicksort and mergesort take O(N log N) in the average case. Why is quicksort faster than mergesort? The inner loop consists of an increment/decrement (by 1, which is fast), a test and a jump. There is no extra juggling as in mergesort. inner loop
COMP171 Lower bound for sorting, radix sort Sorting I / Slide 59 Lower Bound for Sorting Mergesort and heapsort worst-case running time is O(N log N) Are there better algorithms? Goal: Prove that any sorting algorithm based on only comparisons takes (N log N)
comparisons in the worst case (worse-case input) to sort N elements. Sorting I / Slide 60 Lower Bound for Sorting Suppose we want to sort N distinct elements How many possible orderings do we have for N elements? We can have N! possible orderings (e.g., the sorted output for a,b,c can be a b c, b a c, a c b, c a b, c b a, b c a.) Sorting I / Slide 61 Lower Bound for Sorting
Any comparison-based sorting process can be represented as a binary decision tree. Each node represents a set of possible orderings, consistent with all the comparisons that have been made The tree edges are results of the comparisons Sorting I / Slide 62 Decision tree for Algorithm X for sorting three elements a, b, c Sorting I / Slide 63
Lower Bound for Sorting A different algorithm would have a different decision tree Decision tree for Insertion Sort on 3 elements: There exists an input ordering that corresponds to each root-to-leaf path to arrive at a sorted order. For decision tree of insertion sort, the longest path is O(N2). Sorting I / Slide 64 Lower Bound for Sorting The worst-case number of comparisons used by the sorting algorithm is equal to the depth of the deepest leaf
A decision tree to sort N elements must have N! leaves The average number of comparisons used is equal to the average depth of the leaves a binary tree of depth d has at most 2d leaves a binary tree with 2d leaves must have depth at least d the decision tree with N! leaves must have depth at least log2 (N!) Therefore, any sorting algorithm based on only comparisons between elements requires at least log2(N!) comparisons in the worst case. Sorting I / Slide 65
Lower Bound for Sorting Any sorting algorithm based on comparisons between elements requires (N log N) comparisons. Sorting I / Slide 66 Linear time sorting Can we do better (linear time algorithm) if the input has special structure (e.g., uniformly distributed, every number can be represented by d digits)? Yes. Counting sort, radix sort
Sorting I / Slide 67 Counting Sort Assume N integers are to be sorted, each is in the range 1 to M. Define an array B[1..M], initialize all to 0 Scan through the input list A[i], insert A[i] into B[A[i]] O(M) O(N) Scan B once, read out the nonzero integers O(M) Total time: O(M + N)
if M is O(N), then total time is O(N) Can be bad if range is very big, e.g. M=O(N 2) N=7, M = 9, Want to sort 8 1 9 1 2 3 5 5 2 6 3 6 Output: 1 2 3 5 6 8 9 8 9 Sorting I / Slide 68
Counting sort What if we have duplicates? B is an array of pointers. Each position in the array has 2 pointers: head and tail. Tail points to the end of a linked list, and head points to the beginning. A[j] is inserted at the end of the list B[A[j]] Again, Array B is sequentially traversed and each nonempty list is printed out. Time: O(M + N) Sorting I / Slide 69
Counting sort M = 9, Wish to sort 8 5 1 5 9 5 6 2 7 1 2 5 6 7 5 5 Output: 1 2 5 5 5 6 7 8 9 8 9 Sorting I / Slide 70
Radix Sort Extra information: every integer can be represented by at most k digits d1d2dk where di are digits in base r d1: most significant digit dk: least significant digit Sorting I / Slide 71 Radix Sort
Algorithm sort by the least significant digit first (counting sort) => Numbers with the same digit go to same bin reorder all the numbers: the numbers in bin 0 precede the numbers in bin 1, which precede the numbers in bin 2, and so on sort by the next least significant digit continue this process until the numbers have been sorted on all k digits Sorting I / Slide 72 Radix Sort
Least-significant-digit-first Example: 275, 087, 426, 061, 509, 170, 677, 503 170 061 503 275 426 087 677 509 Sorting I / Slide 73 170 061 503 275 426 087 677 509 503 509 426 061 170 275 677 087 061 087 170 275 426 503 509 677 Sorting I / Slide 74 Radix Sort
Does it work? Clearly, if the most significant digit of a and b are different and a < b, then finally a comes before b If the most significant digit of a and b are the same, and the second most significant digit of b is less than that of a, then b comes before a. Sorting I / Slide 75 Radix Sort Example 2: sorting cards 2 digits for each card: d1d2
d1 = : base 4 d2 = A, 2, 3, ...J, Q, K: base 13 A 2 3 ... J Q K 2 2 5 K Sorting I / Slide 76 A=input array, n=|numbers to be sorted|,
d=# of digits, k=the digit being sorted, j=array index // base 10 // FIFO // d times of counting sort // scan A[i], put into correct slot // re-order back to original array Sorting I / Slide 77 Radix Sort Increasing the base r decreases the number of passes Running time
k passes over the numbers (i.e. k counting sorts, with range being 0..r) each pass takes 2N total: O(2Nk)=O(Nk) r and k are constants: O(N) Note: radix sort is not based on comparisons; the values are used as array indices If all N input values are distinct, then k = (log N) (e.g., in binary digits, to represent 8 different numbers, we need at least 3 digits). Thus the running time of Radix Sort also become (N log N).
Heaps, Heap Sort, and Priority Queues Sorting I / Slide 79 Trees A tree T is a collection of nodes T can be empty (recursive definition) If not empty, a tree T consists of a (distinguished) node r (the root), and zero or more nonempty subtrees T1, T2, ...., Tk
Sorting I / Slide 80 Some Terminologies Child and Parent Leaves Every node except the root has one parent A node can have an zero or more children Leaves are nodes with no children
Sibling nodes with same parent Sorting I / Slide 81 More Terminologies Path Length of a path number of edges on the path
Depth of a node A sequence of edges length of the unique path from the root to that node Height of a node length of the longest path from that node to a leaf all leaves are at height 0 The height of a tree = the height of the root = the depth of the deepest leaf Ancestor and descendant
If there is a path from n1 to n2 n1 is an ancestor of n2, n2 is a descendant of n1 Proper ancestor and proper descendant Sorting I / Slide 82 Example: UNIX Directory Sorting I / Slide 83 Example: Expression Trees Leaves are operands (constants or variables) The internal nodes contain operators Will not be a binary tree if some operators are not binary
Sorting I / Slide 84 Background: Binary Trees root Has a root at the topmost Parent(x) level Each node has zero, one or two children x A node that has no child is
called a leaf For a node x, we denote the left(x)right(x) left child, right child and the parent of x as left(x), leaf right(x) and parent(x), respectively. leaf leaf Sorting I / Slide 85 Struct Node { double element; // the data Node* left; // left child Node* right; // right child // Node* parent; // parent A binary tree can be naturally
implemented by pointers. } class Tree { public: Tree(); // constructor Tree(const Tree& t); ~Tree(); // destructor bool empty() const; double root(); // decomposition (access functions) Tree& left(); Tree& right(); // Tree& parent(double x); // update void insert(const double x); // compose x into a tree
void remove(const double x); // decompose x from a tree private: Node* root; } Sorting I / Slide 86 Height (Depth) of a Binary Tree The number of edges on the longest path from the root to a leaf. Height = 4 Sorting I / Slide 87 Background: Complete Binary Trees A complete binary tree is the tree
Where a node can have 0 (for the leaves) or 2 children and All leaves are at the same depth height 0 no. of nodes 1 1 2 2 4 3
8 d 2d No. of nodes and height A complete binary tree with N nodes has height O(logN) A complete binary tree with height d has, in total, 2d+1-1 nodes Sorting I / Slide 88 Proof: O(logN) Height Proof: a complete binary tree with N nodes has height of O(logN) 1. 2.
3. 4. Prove by induction that number of nodes at depth d is 2d Total number of nodes of a complete binary tree of depth d is 1 + 2 + 4 + 2d = 2d+1 - 1 Thus 2d+1 - 1 = N d = log(N+1)-1 = O(logN) Side notes: the largest depth of a binary tree of N nodes is O(N) Sorting I / Slide 89 (Binary) Heap Heaps are almost complete binary trees
All levels are full except possibly the lowest level If the lowest level is not full, then nodes must be packed to the left Pack to the left Sorting I / Slide 90 1 4 2 4 5 3
A heap 6 2 1 5 3 6 Not a heap Heap-order property: the value at each node is less than or equal to the values at both its descendants --- Min Heap
It is easy (both conceptually and practically) to perform insert and deleteMin in heap if the heap-order property is maintained Sorting I / Slide 91 Structure properties Has 2h to 2h+1-1 nodes with height h The structure is so regular, it can be represented in an array and no links are necessary !!! Use of binary heap is so common for priority queue implementations, thus the word heap is usually assumed to be the implementation of the data structure
Sorting I / Slide 92 Heap Properties Heap supports the following operations efficiently Insert in O(logN) time Locate the current minimum in O(1) time Delete the current minimum in O(log N) time Sorting I / Slide 93 Array Implementation of Binary Heap A B C D
H E I F G A B C D E F G H I J 0 1 2 3 4 5 6 7 8 J For any element in array position i The left child is in position 2i The right child is in position 2i+1 The parent is in position floor(i/2)
A possible problem: an estimate of the maximum heap size is required in advance (but normally we can resize if needed) Note: we will draw the heaps as trees, with the implication that an actual implementation will use simple arrays Side notes: its not wise to store normal binary trees in arrays, because it may generate many holes Sorting I / Slide 94 class Heap { public: Heap(); // constructor Heap(const Heap& t);
~Heap(); // destructor bool empty() const; double root(); // access functions Heap& left(); Heap& right(); Heap& parent(double x); // update void insert(const double x); // compose x into a heap void deleteMin(); // decompose x from a heap private: double* array; int array-size; int heap-size; } Sorting I / Slide 95 Insertion
Algorithm 1. 2. Add the new element to the next available position at the lowest level Restore the min-heap property if violated General strategy is percolate up (or bubble up): if the parent of the element is larger than the element, then interchange the parent and child. 1 1 2 4
5 3 6 1 2 4 5 3 6 Insert 2.5 2.5 2
2.5 4 3 6 swap 5 Percolate up to maintain the heap property Sorting I / Slide 96 Insertion Complexity 7 9 17 20
8 16 14 A heap! 10 18 Time Complexity = O(height) = O(logN) Sorting I / Slide 97 deleteMin: First Attempt Algorithm 1. 2.
3. 4. 5. 6. 7. Delete the root. Compare the two children of the root Make the lesser of the two the root. An empty spot is created. Bring the lesser of the two children of the empty spot to the empty spot. A new empty spot is created. Continue Sorting I / Slide 98 Example for First Attempt 1 2 4
2 5 3 6 4 3 2 3 6 1 5
4 5 6 3 4 5 6 Heap property is preserved, but completeness is not preserved! Sorting I / Slide 99 deleteMin 1. 2. Copy the last number to the root (i.e. overwrite the
minimum element stored there) Restore the min-heap property by percolate down (or bubble down) Sorting I / Slide 100 Sorting I / Slide 101 An Implementation Trick (see Weiss book) Implementation of percolation in the insert routine by performing repeated swaps: 3 assignment statements for a swap. 3d assignments if an element is percolated up d levels An enhancement: Hole digging with d+1 assignments (avoiding swapping!)
7 9 17 7 8 16 4 14 9 4 10 20 18 Dig a hole Compare 4 with 16 17 7 8
14 4 8 10 20 18 16 Compare 4 with 9 17 9 14 10 20 18 16 Compare 4 with 7
Sorting I / Slide 102 Insertion PseudoCode void insert(const Comparable &x) { //resize the array if needed if (currentSize == array.size()-1 array.resize(array.size()*2) //percolate up int hole = ++currentSize; for (; hole>1 && x
2 2 4 5 3 6 5 4 1. create hole tmp = 6 (last element) 3 2. Compare children and tmp bubble down if necessary 2
2 5 3 4 6 6 3. Continue step 2 until reaches lowest level 5 3 4 6 4. Fill the hole
Sorting I / Slide 104 deleteMin PseudoCode void deleteMin() { if (isEmpty()) throw UnderflowException(); //copy the last number to the root, decrease array size by 1 array[1] = array[currentSize--] percolateDown(1); //percolateDown from root } void percolateDown(int hole) //int hole is the root position { int child; Comparable tmp = array[hole]; //create a hole at root for( ; hold*2 <= currentSize; hole=child){ //identify child position child = hole*2; //compare left and right child, select the smaller one if (child != currentSize && array[child+1]
if(array[child]
Heapsort (1) Build a binary heap of N elements the minimum element is at the top of the heap (2) Perform N DeleteMin operations the elements are extracted in sorted order (3) Record these elements in a second array and then copy the array back Sorting I / Slide 107 Build Heap
Input: N elements Output: A heap with heap-order property Method 1: obviously, N successive insertions Complexity: O(NlogN) worst case Sorting I / Slide 108 Heapsort Running Time Analysis (1) Build a binary heap of N elements repeatedly insert N elements O(N log N) time (there is a more efficient way, check textbook p223 if interested) (2) Perform N DeleteMin operations Each DeleteMin operation takes O(log N) O(N log N) (3) Record these elements in a second array and then copy the
array back O(N) Total time complexity: O(N log N) Memory requirement: uses an extra array, O(N) Sorting I / Slide 109 Heapsort: in-place, no extra storage Observation: after each deleteMin, the size of heap shrinks by 1
We can use the last cell just freed up to store the element that was just deleted after the last deleteMin, the array will contain the elements in decreasing sorted order To sort the elements in the decreasing order, use a min heap To sort the elements in the increasing order, use a max heap the parent has a larger element than the child Sorting I / Slide 110 Sort in increasing order: use max heap Delete 97
Sorting I / Slide 111 Delete 16 Delete 10 Delete 9 Delete 14 Delete 8 Sorting I / Slide 112 Sorting I / Slide 113 One possible Heap ADT Template
BinaryHeap(int capacity=100); explicit BinaryHeap(const vector
for the explanation of explicit declaration for conversion constructors in http://www.glenmccl.com/tip_023.htm Sorting I / Slide 114 Priority Queue: Motivating Example 3 jobs have been submitted to a printer in the order A, B, C. Sizes: Job A 100 pages Job B 10 pages Job C -- 1 page Average waiting time with FIFO service: (100+110+111) / 3 = 107 time units Average waiting time for shortest-job-first service: (1+11+111) / 3 = 41 time units A queue be capable to insert and deletemin? Priority Queue Sorting I / Slide 115 Priority Queue
Priority queue is a data structure which allows at least two operations insert deleteMin: finds, returns and removes the minimum elements in the priority queue deleteMin Priority Queue insert Applications: external sorting, greedy algorithms Sorting I / Slide 116
Possible Implementations Linked list Binary search tree (AVL tree, to be covered later) Insert in O(1) Find the minimum element in O(n), thus deleteMin is O(n) Insert in O(log n) Delete in O(log n)
Search tree is an overkill as it does many other operations Eerr, neither fit quite well Sorting I / Slide 117 Its a heap!!!