# CSCI6370: Topics in Computer Science Advanced Topics in ... Sorting Sorting includes internal sorting and external sorting Internal sorting: the entire sort can be done in main memory, i.e., all elements needed to be sorted can be stored entirely in main memory. External sorting: Sorts that cannot be performed in main memory and must be done on disk or tape are known as external sorting. We will focus on internal sorting. Several simple algorithms, such as insertion sort, perform in O(N 2) time. Shellsort that is very simple to code, first breaks ( N2 ) barrier, and is efficient in practice. Slightly more complicated sorting algorithms, such as heap sort, merge sort, quick sort, take O(NlogN) time. Linear time sorting algorithms, such as bucket sort. Preliminaries The efficiency of data handling can often be substantially increased if the data are sorted according to some criteria of order. We assume: The objects being sorted are elements of an array. The objects being sorted are of type Comparable, which is just a synonym for whatever class of object we wish to place in the array. If necessary, the Comparable class overloads the standard C++ operators =, > and < that used by the sort algorithms. That is, = is used for copying elements, while > and < compare two elements with respect to the defined criteria. This enables sort criteria to vary from one element type to another. Insertion Sort Insertion sort is one of the simplest sorting algorithms. The algorithm Insertion sort consists of N-1 passes. For pass p = 1 through N-1, insertion sort ensures that the elements in positions 0 through p are in sorted order. Insertion sort makes use of the fact that elements in positions 0 through p-1 are already known to be in sorted order, and move the element in position p left until its correct place is found among the first p+1 elements. Insertion Sort Examples Sort 34, 8, 64, 51, 32, and 21 position: 0 1 2

3 34 8 4 5 64 51 32 21 First pass: 34 8 64 51 32 21 p=1 8 34 64 51 32 21 second pass: p=2 8 8 34 64 51 32 21 34 64 51 32 21 third pass: 8 34 64 51 32 21 p=3 8 34 51 64 32 21 8 34 51 64 32 21 fourth pass:8 p=4 8 8 34 8 32 8 32 34 34 32 34 34 51 51 51 51 51 64 32 64 64 64 32 21 64 21 21 21 21

Insertion Sort Examples Sort 34, 8, 64, 51, 32, and 21 (cont.) position: fifth pass: p=5 8 8 8 8 8 8 32 32 21 21 0 1 2 3 4 32 32 34 21 32 32 34 34 21 34 34 34 51 51 51 51 51 51 64 21 21 64 64 64

64 64 5 Insertion Sort C++ code template void InsertionSort (vector & a) { int j; for (int p=1; p < a. size( ); p++) // perform N-1 passes { // for each iteration p, a[0 .. p-1] in sorted order. comparable tmp = a[p]; move the element in for (j = p; j > 0 && tmp < a[j-1]; j--) position p left until its correct place is found a[j] = a[j-1]; among the first p+1 elements. a[j] = tmp; } } 8 34 64 51 32 21 j p Insertion Sort Performance InsertionSort() includes two nested loops. The inner loop can be executed at most p+1 times for each value of p. p iterates from 1 to N-1 The number of iterations of the inner loop is given by: 2+3+ +N = N(N+1)/2 - 1 The running time of InsertionSort is O(N2). Insertion Sort Best Cases If the input data elements are in increasing order, the inner loop is terminated immediately and thus the running time is O(N). For example: sort 8 21 32 34 51 64 position: 0 1

2 3 8 4 5 21 32 34 51 64 First pass: 8 p=1 8 21 32 34 51 64 21 32 34 51 64 second pass: p=2 8 8 21 32 34 51 64 21 32 34 51 64 third pass: 8 p=3 8 21 32 34 51 64 21 32 34 51 64 fourth pass:8 p=4 8 21 32 34 51 64 21 32 34 51 64 fifth pass: p=5 21 32 34 51 64 21 32 34 51 64 8 8 Insertion Sort Worst Cases If the input data elements are in decreasing order, the inner loop is executed p+1 times for each value of p and thus the running time is O(N2). For example: sort 64 51 34 32 21 8 position:

0 1 2 3 4 5 64 51 34 32 21 8 fourth pass:32 34 p=4 32 34 32 34 21 32 21 34 21 32 34 21 32 34 51 51 51 51 51 51 64 21 64 64 64 64 21 8 j=4 64 8 j=3 8 j=2 8 j=1 8 j=0 8 Shellsort Shellsort was one of the first algorithms to break the quadratic barrier. Shellsort works by comparing elements that are distant; the distance

between comparisons decreases as the algorithm runs until the last phase, in which adjacent elements are compared. Basic ideas Choose a sequence, h1=1, h2, , ht, called the increment sequence. For each hk = ht , , h2, h1, sort all elements spaced hk apart. (After a phase, using some increment hk, for every i, we have a[i] <= a[i+hk]; all elements spaced hk apart are in sorted order. The file is then said to be hk-sorted.) In each phase, use insertion sort to sort all elements spaced h k apart. For example, Original: 80 93 60 12 42 30 68 85 10 after 3-sort: 12 42 10 68 85 30 80 93 60 Shellsort Example Suppose we have an array containing the following integers: 80 93 60 12 42 30 68 85 10 Choose {3, 2, 1} as the increment sequence. For each hk = 3, 2, 1, sort all elements spaced hk apart using insertion sort. For hk = 3, divide the original array into three segments (all elements in each segment are spaced hk apart in the original array). 80 12 68 segment 1 93 42 85 segment 2 60 30 10 segment 3 (80 93 60 12 42 30 68 85 10) and sort each segment using insertion sort: 12 68 80 42 85 93 10 30 60 The original array, partially sorted, now appears as 12 42 10 68 85 30 80 93 60 Shellsort Example For each hk = 3, 2, 1, sort all elements spaced hk apart using insertion sort. (After 3-sort: 12 42 10 68 85 30 80 93 60) For hk = 2, divide the 3-sorted array into two segments (all elements in each segment are spaced hk apart in the 3-sorted array). 12 10 85 80 60 segment 1 42 68 30 93 segment 2 (12 42 10 68 85 30 80 93 60) and sort each segment using insertion sort: 10 12 60 80 85 30 42 68 93 The array takes the form: 10 30 12 42 60 68 80 93 85 (after 2-sort) For hk = 1, sort the 2-sorted array using insertion sort. 10 12 30 42 60 68 80 85 93 How to Choose the Increment Sequence Any increment sequence will do as long as h 1 = 1, but some choices are better than others. Shells increments: ht = N/2 and hk = hk+1/2 Ex. N = 9: 1, 2, 4 N = 21: 1, 2, 5, 10

Hibbards increments: 1, 3, 7, , 2k-1 (such that 2k-1 <= N and 2k+1-1 > N) Ex. N = 9: 1, 3, 7 N = 21: 1, 3, 7, 15 Sedgewicks increments: 1, 5, 19, 41, 109 , in which the terms are either of the form 9*4i-9*2i+1 or 4i-3*2i+1. Ex. N = 9: 1, 5 N = 21: 1, 5, 19 C++ code for Shellsort /** * Shellsort, using Shells (poor) increments. */ template void shellsort( vector & a ) { int j; } for ( int gap = a.size() / 2; gap > 0; gap /= 2 ) //Shells increments for ( int i = gap; i < a.size(); i ++) Use insertion sort to sort { elements in each segments Comparable tmp = a[ i ]; in sorted order. That is, for for ( j = i; j >= gap && tmp < a[ j gap ]; j -= gap ) each position, i, in gap, a [j ] = a[ j gap ]; gap+1, , N-1, place the element in the correct spot a [ j ] = tmp; among i, i-gap, i-2*gap, } i-3*gap, , etc. Shellsort Using Shells Increments - Example Original : 81 99 11 96 12 98 17 95 i Place the element at i in the gap = 4 : 81 99 11 96 12 98 17 95 81 99 11 96 12 98 17 95 the correct spot among the i elements in the same segmen 12 99 11 96 81 98 17 95 and at the positions before i. i 12 98 11 96 81 99 17 95 i 12 98 11 96 81 99 17 95 12 98 11 95 81 99 17 96

i gap = 2 : 12 98 11 95 81 99 17 96 11 98 12 95 81 99 17 96 i 11 98 12 95 81 99 17 96 i 11 95 12 98 81 99 17 96 i 11 95 12 98 81 99 17 96 i 11 95 12 98 81 99 17 96 i 11 95 12 98 17 99 81 96 11 95 12 96 17 98 81 99 Shellsort Running Time The running time of Shellsort depends on the choice of increment sequence. The worst-case running time of Shellsort, using Shells increments, is O(N2). The worst-case running time of Shellsort using Hibbards increments is O(N3/2). The worst-case running time of Shellsort using Sedgewicks increments is O(N4/3). The average-case running time of Shellsort, using Hibbards increments, is thought to be O(N5/4), based on simulations, but nobody has been able to prove this. The average running time is conjectured to be O(N7/6). Heapsort Binary heaps can be used to sort in O(NlogN) time. Basic ideas Step 1: Build a binary heap of N elements Step 2: Remove the root and reheap (perform the deleteMin operation) Step 3: Repeat step 2 until empty. Binary heaps (review) What is a binary heap? Complete binary tree: a binary tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right. Heap-order property: for every node x, the key in the parent of x is smaller than (or equal to) the key in x, with the exception of the root.

How to build a binary heap for N elements? build a complete binary tree first ignore the heap-order property at the moment apply percolate-down for each node starting at the last non-leaf node. 26 97 53 26 0 41 59 41 58 97 53 59 26 41 58 31 1 2 3 4 5 6 7 53

31 8 9 10 31 0 97 58 26 41 31 53 97 58 59 1 2 3 4 5 6 7 59 8 9 10 Binary heaps (review) deleteMin: Remove the element in the root and create a hole in the root. Percolate the hole down so that the last element in the heap can be

placed in the hole. 26 41 31 53 0 97 41 58 59 26 41 31 53 97 58 59 1 2 3 4 5 6 7 8 9 31 53 10

97 1 0 58 41 31 53 97 58 59 2 3 4 5 6 31 0 97 1 2 8 3 9 10 58 41 53 41

7 31 41 31 59 58 53 97 58 59 4 5 6 7 59 8 9 10 53 0 59 97 31 41 58 53 97 59

1 2 3 4 5 6 7 8 9 10 Heapsort Example Sort 97 53 59 26 41 58 31 Build a binary heap for 97 53 59 26 41 58 31 26 41 31 53 58 26 41 31 53 97 58 59 1 2 3 4 5

6 0 97 59 7 Remove root 26 and reheap: 31 58 41 53 0 59 97 31 41 58 53 97 59 1 2 3 4 5 6 26

7 0 1 2 3 4 5 6 7 Heapsort Example Sort 97 53 59 26 41 58 31 Remove root 31 and reheap: 41 58 53 59 0 97 41 53 58 59 97 1 2 3 4 5

6 0 7 26 31 1 2 3 26 31 41 1 2 3 4 5 6 7 4 5 6 7 Remove root 41 and reheap: 53 58 59 97

0 53 59 58 97 1 2 3 4 5 6 7 0 Heapsort Example Sort 97 53 59 26 41 58 31 Remove root 53 and reheap: 58 97 59 0 58 59 97 1 2 3 4 5

6 7 0 26 31 41 53 1 2 3 4 5 26 31 41 53 58 1 2 3 4 5 6 7 6 7 Remove root 58 and reheap:

59 97 0 59 97 1 2 3 4 5 6 7 0 Heapsort Example Sort 97 53 59 26 41 58 31 Remove root 59 and reheap: 97 97 0 1 2 3 4 5 6 7 0 26

31 41 53 58 59 1 2 3 4 5 6 7 26 31 41 53 58 59 97 1 2 3 4 5 6 7 Remove root 97:

0 1 2 3 4 5 6 7 0 Heapsort Running Time To build a binary heap takes O(N) time. Performing N deleteMin operations takes O(NlogN) time. Total running time is O(NlogN). Drawback: need to use an extra array. Heapsort Improving Space Efficiency A clever way to avoid using a second array makes use of the fact that after each deleteMin, the heap shrinks by 1. 31 58 41 53 59 97 31 41

58 53 97 59 1 2 3 4 5 6 0 After remove the smallest element 26. 26 0 7 1 2 3 4 5 6 7 The cell that was last in the heap can be used to store the element that was just deleted. 31 58 41 53

0 59 97 31 41 58 53 97 59 26 1 2 3 4 5 6 7 Improving Space Efficiency Example Sort 97 53 59 26 41 58 31 Build a binary heap for 97 53 59 26 41 58 31 26 41 31 53 97 58 59

26 41 31 53 97 58 59 1 2 3 4 5 6 0 7 Remove root 26 and reheap: 31 58 41 53 0 59 97 31 41 58 53 97 59

26 1 2 3 4 5 6 7 Improving Space Efficiency Example Sort 97 53 59 26 41 58 31 Remove root 31 and reheap: 41 58 53 59 0 97 41 53 58 59 97 31 26 1 2 3 4

5 7 6 Remove root 41 and reheap: 53 58 59 97 0 53 59 58 97 41 31 26 1 2 3 4 5 6 7 Improving Space Efficiency Example Sort 97 53 59 26 41 58 31 Remove root 53 and reheap: 58 97 59

0 58 59 97 53 41 31 26 1 2 3 4 6 7 5 Remove root 58 and reheap: 59 97 0 59 97 58 53 41 31 26 1 2

3 4 5 6 7 Improving Space Efficiency Example Sort 97 53 59 26 41 58 31 Remove root 59 and reheap: 97 0 97 59 58 53 41 31 26 1 2 3 4 5 6 7 Remove root 97 and reheap: 0 97

59 58 53 41 31 26 1 2 3 4 5 6 7 The resulting array contains the elements in decreasing sorted order. If we want the elements in the more typical increasing sorted order, how to solve? (max)Heap In the original heap, the parent has a smaller element than its children. (max)Heap A complete binary tree Heap order property: for every node x, the key in the parent of x is larger than (or equal to) the key in x, with the exception of the root. Heapsort Using (max)Heap Example Sort 97 53 59 26 41 58 31 Build a (max)heap for 97 53 59 26 41 58 31 97 53 59 26

41 58 31 97 53 59 26 41 58 31 1 2 3 4 5 6 0 7 Remove root 97 and reheap: 59 58 53 26 0 31 41 59 53 58

26 41 31 97 1 2 3 4 5 6 7 Heapsort Using (max)Heap Example Sort 97 53 59 26 41 58 31 Remove root 59 and reheap: 58 31 53 26 0 41 58 53 31 26 41 59 97

1 2 3 4 5 6 7 Remove root 58 and reheap: 53 31 41 26 0 53 41 31 26 58 59 97 1 2 3 4 5 6 7 Heapsort Using (max)Heap Example

Sort 97 53 59 26 41 58 31 Remove root 53 and reheap: 41 31 26 0 41 26 31 53 58 59 97 1 2 3 4 5 6 7 Remove root 41 and reheap: 31 26 0 31 26 41 53

58 59 97 1 2 3 4 5 6 7 Heapsort Using (max)Heap Example Sort 97 53 59 26 41 58 31 Remove root 31 and reheap: 26 0 26 31 41 53 58 59 97 1 2 3 4 5

6 7 Remove root 26 and reheap: 0 26 31 41 53 58 59 97 1 2 3 4 5 6 7 Mergesort Mergesort runs in O(NlogN) worst-case running time. The number of comparisons used is nearly optimal. Mergesort is a fine example of a recursive algorithm. We give two implementations: recursive one and nonrecursive one. Merging Two Sorted Lists The fundamental operation in this algorithm is merging two sorted lists. Basic ideas Takes two input arrays A and B in sorted order, and an output array C. Three counters, Actr, Bctr, and Cctr, which are initially set to the

beginning of their respective arrays. The smaller of A[Actr] and B[Bctr] is copied to the next entry in C (i.e., C[Cctr]), and the appropriate counters are advanced. When either input list is exhausted, the remainder of the other list is copied to C. A 1 13 Actr 24 26 B 2 15 Bctr 27 38 C Cctr Merging Two Sorted Lists Example Suppose we want to merge array A containing 1, 13, 24, 26, and array B containing 2, 15, 27, 38 A 1 13 24 26 B Actr A

1 15 2 1 13 24 26 B 2 1 C 13 24 13 24 1 Cctr 15 27 38 C 1 Bctr 26 B 2 Actr

A 38 Bctr Actr A 27 15 2 Cctr 27 38 C 1 2 Bctr 26 Actr B 2 15 27 Bctr 13 Cctr 38 C 1

2 13 15 Cctr Merging Two Sorted Lists Example Suppose we want to merge array A containing 1, 13, 24, 26, and array B containing 2, 15, 27, 38 (cont.) A 1 13 24 B 26 15 2 Actr A 1 13 24 1 13 24 38 C 1 2 13

15 Bctr B 26 15 2 Actr A 27 26 27 38 24 Cctr C 1 2 13 15 24 Bctr B 15 2 Actr 27 38

26 Cctr C 1 2 13 15 24 26 Bctr Cctr Now the array A is exhausted. Then the remainder of the array B is copied to C A 1 13 24 26 B Actr 2 15 27 38 C Bctr 1 2 13

15 24 26 27 38 Cctr Merging Two Sorted Lists C++ Code B A a leftPos rightPos rightEnd leftEnd points to the last position of subarray A; tmpPos is the next available position in array tmpArray to place the merged result. One pass traversal of A and B; make sure not to go Beyond the end position of A or B. If current element in A is no larger than current element In B, place the current element in A into tmpArray, and advance leftPos and tmpPos by one. If we exhaust array B, copy the remainder of array A to tmpArray. If we exhaust array A, copy the remainder of array B to tmpArray. Recursive Mergesort The basic idea If N = 1, there is only one element to sort, and the answer is at hand. Otherwise, Recursively mergesort the first half; Recursively mergesort the second half; This gives two sorted halves, which can then be merged together using the merging algorithm. For instance, suppose to sort the eight-element array 24 13 26 1 2 27 38 15 Recursively sort the first four elements: 24 13 26 1 1 13 24 16 Recursively sort the second four elements:

2 27 38 15 2 15 27 38 Merge the two halves 1 2 13 15 24 26 27 38 Recursive Mergesort C++ Code a left center right Execution of the Recursive mergeSort Suppose to sort the following integers 1 2 3 4 5 6 7 24 13 26 1 2 27 38 15 0 a 1 2 13 15 24 26 27 38 mS(a, 0, 7)

24 13 26 1 2 27 38 15 2 15 27 38 1 13 24 26 mS(a, 0, 3) mS(a, 4, 7) 24 13 26 1 2 27 38 15 1 26 13 24 mS(a, 0, 1) mS(a, 2, 3) 24 13 26 1 24 13 15 38 2 27 mS(a, 4, 5) mS(a, 6, 7) 2 27 26 1 38 15 27 2 38 15 mS(a, 0, 0) mS(a, 1, 1) mS(a, 2, 2) mS(a, 3, 3) mS(a, 4, 4) mS(a, 5, 5) mS(a, 6, 6) mS(a, 7, 7) 24

13 26 1 2 27 38 15 Divide-and-Conquer mergeSort is a classic devide-and-conquer strategy. Basic ideas: Break the problem into several subproblems that are similar to the original problem but smaller in size, solve the subproblems recursively, and then combine these solutions to create a solution to the original problem. The divide-and-conquer paradigm involves three steps at each level of the recursion: Divide the problem into a number of subproblems. Conquer the subproblems by solving them recursively. If the subproblems sizes are small enough, however, just solve the subproblems in a straightforward manner. Combine the solutions to the subproblems into the solution for the original problem. Divide-and-Conquer mergeSort The merge sort algorithm closely follows the divide-andconquer paradigm. Divide: Divide the n-element array to be sorted into two subarrays of n/2 elements each. Conquer: Sort the two subarrays recursively using mergeSort. Combine: Merge the two sorted subarrays to produce the sorted answer. 1 2 2 3 4 5 6 6 5 2 4 6 1 3 2 6 1 3 2 6 5 2 4 6 5 2 5 2 4 4 6 1 3

6 1 2 6 3 2 1 2 3 6 2 4 5 6 6 2 5 5 2 4 4 6 1 3 6 1 2 6 3 2 6 Analysis of mergeSort mergeSort works correctly when the number of elements is not even. Our analysis is simplified. We assume that the original problem size is a power of two, so that we always split into even halves. Assume the size of the input sequence is N and the time to sort the sequence is T(N). Merge sort on just one element takes constant time. When we have N > 1 elements, we break down the running time as follows. Divide: The divide step just computes the middle of the subarray, which takes constant time. Conquer: We recursively solve two subproblems, each of size N/2, which takes 2T(N/2) time. Combine: We have already noted that merging two sorted subarrays takes time O(N). Therefore, we get the recurrence T(N) = O(1) 2T(N/2) + O(N) if N = 1,

if N > 1. How to Compute T(N)? Telescoping T(1) = 1 T(N) = 2T(N/2) + N Divide the recurrence relation through by N. This yields T ( N ) T ( N / 2) 1 N N /2 This equation is valid for any N that is a power of 2, so we may also write T ( N / 2) T ( N / 4) 1 N /2 N /4 and T ( N / 4) T ( N / 8) 1 N /4 N /8 T (2) T (1) 1 2 1 Add up all the equations (add all of the terms on the left-hand side and set the result equal to the sum of all of the terms on the There are logN equations and so all the T ( N ) T (1) log N right-hand side). N 1 1s at the end of these equations add up to logN. How to Compute T(N)? Telescoping (cont.) Multiplying through by N gives the final answer. T(N) = NlogN + N = O(NlogN) How to Compute T(N)? The iteration method

T(1) = 1 T(N) = 2T(N/2) + N Since we can substitute N/2 into the main equation, 2T(N/2) = 2(2T(N/4) + N/2) = 4T(N/4) + N we have T(N) = 4T(N/4) + 2N Again, by substituting N/4 into the main equation, we see that 4T(N/4) = 4(2T(N/8) + N/4) = 8T(N/8) + N So we have T(N) = 8T(N/8) + 3N Continuing in this manner, we obtain T(N) = 2kT(N/2k) + k.N Using k = logN, we obtain T(N) = NT(1) + NlogN = NlogN + N = O(NlogN) Non-Recursive Mergesort Basic idea Perform m = logN passes In each pass, merge pairs of sorted subarrays into bigger subarrays; at last, we get one sorted array. The base observation is that each single element of the input array can be viewed as a subarray in sorted order. 1 2 3 4 5 6 7 24 13 26 1 2 27 38 15

0 Suppose to sort the following integers a 1 2 13 15 24 26 27 38 2 15 27 38 1 13 24 26 1 26 13 24 24 13 26 15 38 2 27 1 2 27 38 15 Drawback of Mergesort Although mergesorts running time is O(NlogN), it is hardly ever used for main memory sorts. The main problem is that merging two sorted lists used linear extra memory, and the additional work spent copying to the temporary array and back, throughout the algorithm, has the effect of slowing down the sort considerably. It is theoretically possible to use less extra memory, but the resulting algorithm is complex and impractical. The copying can be avoided by judiciously switching the roles of the input

array a and tmpArray at alternate levels of the recursion. For serious internal sorting applications, the algorithm of choice is quicksort. Quicksort Quicksort is the fastest known sorting algorithm in practice. Its average running time is O(NlogN). Quicksort is a divide-and-conquer recursive algorithm. The algorithm If the number of elements in input array S is 0 or 1, then return. Pick any element v in S. This is called the pivot. Partition S-{v} (the remaining elements in S) 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 Sort 13, 81, 43, 92, 31, 65, 57, 26, 75, 0 The pivot is chosen by chance to be 65. 13 81 43 92 31 65 57 26 75 0 select pivot 13 81 43 92 31 65 57 26 75 0 partition 13 43 31 57 26 0 65 81 92 75 quicksort small quicksort large 0 13 26 31 43 57 65 75 81 92 0 13 26 31 43 57 65 75 81 92 Issues in Quicksort How to choose the pivots? The choices of pivots affect the performance of quicksort a lot! If the pivots being chosen are in sorted order, quicksort degenerates to selectionSort. For instance, sort 13, 81, 43, 92, 31, 65, 57, 26, 75, 0 Pivots we choose happen to be: 0 13 26 31 43 57 65 75 81 92 13 81 43 92 31 65 57 26 75 0 partition using 0 0 13 81 43 92 31 65 57 26 75 partition using 13

0 13 81 43 92 31 65 57 26 75 partition using 26 0 13 26 81 43 92 31 65 57 75 partition using 31 0 13 26 31 81 43 92 65 57 75 We hope that by using the pivot, we can partition the array into two subarrays with nearly equal size. Issues in Quicksort How to partition the array? Like mergesort, quicksort recursively solves two subproblems and requires linear additional work (partitioning step), but, unlike mergesort, the subproblems are not guaranteed to be of equal size, which is potentially bad. The reason that quicksort is faster is that the partitioning step can actually be performed in place and very efficiently. This efficiency more than makes up for the lack of equal-sized recursive calls. Picking the Pivot A wrong way Using the first element as the pivot The choice is acceptable if the input is random. If the input is presorted or in reverse order, then the pivot provides a poor partition, because either all the elements go into S 1 or they go into S2. 92 81 75 65 57 43 31 26 13 0 partition using 92 81 75 65 57 43 31 26 13 0 92 The poor partition happens consistently throughout the recursive calls if the input is presorted reverse 81 75 or 65in 57 43 order. 31 26 13 0 partition using 81 75 65 57 43 31 26 13 0 81 The practical effect is that if the first element is used as the pivot and the input is presorted, then quicksort will take quadratic time to do essentially nothing at all. Picking the Pivot A wrong way Using the first element as the pivot (cont.) Moreover, presorted input (or input with a large presorted section) is

quite frequent, so using the first element as pivot is an absolutely horrible idea and should be discarded immediately. Choosing the larger of the first two distinct elements as pivot This has the same bad properties as merely choosing the first elements. Do NOT use that pivoting strategy either. Picking the Pivot A safe maneuver A safe course is merely to choose the pivot randomly. This strategy is generally perfectly safe, since it is very unlikely that a random pivot would consistently provide a poor partition. However, random number generation is generally an expensive commodity and does not reduce the average running time of the rest of the algorithm at all. Using median The median of a group of N numbers is the N/2th largest number. The best choice of pivot would be the median of the array, since it gives two subarrays with nearly equal size (actually, can be different by at most 1). 13 81 43 92 31 65 57 26 75 0 partition using 57 13 43 31 26 0 57 81 92 65 75 Theoretically, the median can be found in linear time, thus would not affect the running time of quicksort; but in practice, it would slow down quicksort considerably. Picking the Pivot Median-of-Three partitioning Pick three elements randomly and use the median of these three as pivot. (Random numbers are expensive to generate.) The common course is to use as pivot the median of the left, right, and center (in position (left + right)/2)elements. Using median-of-three partitioning clearly eliminates the bad case for sorted input (the partitions become equal in this case) and actually reduces the running time of quicksort by about 5%. 92 81 75 65 57 43 31 26 13 0 partition using 57 43 31 26 13 0 57 92 81 75 65 Partitioning Strategy Objective: to move all the small elements to the left part of the array and all the large elements to the right part. Samll and large are, of course, relative to the pivot. The basic idea Swap the pivot with the last element; thus the pivot is placed at the last position of the array. i starts at the first element and j starts at the next-to-last element. While i is to left of j, we move i right, skipping over elements that are smaller than the pivot; we move j left, skipping over elements that are larger than the pivot.

When i and j have stopped, i is pointing at a large element and j is pointing at a small element. If i is to the left of j, those elements are swapped. (The effect is to push a large element to the right and a small element to the left.) 8 1 4 9 0 3 5 2 7 6 i j Partitioning Strategy Example Input: 81 13 43 92 31 65 57 26 75 0 Pivot: 57 81 13 43 92 31 65 57 26 75 0 81 13 43 92 31 65 0 26 75 57 i stopped i j move j left 81 13 43 92 31 65 0 26 75 57 i j j stopped swap 26 13 43 92 31 65 0 81 75 57 i move i right j 26 13 43 92 31 65 0 81 75 57 i stopped move i j left j 26 13 43 92 31 65 0 81 75 57 i j j stopped Partitioning Strategy Example Input: 81 13 43 92 31 65 57 26 75 0 Pivot: 57 (cont.) 26 13 43 92 31 65 0 81 75 57 i j j stopped swap

26 13 43 0 31 65 92 81 75 57 i j move i right 26 13 43 0 31 65 92 81 75 57 i stopped i move j left j 26 13 43 0 31 65 92 81 75 57 j stopped j i i and j have crossed. Swap the element at position i with the pivot. 26 13 43 0 31 57 92 81 75 65 Small Arrays For very small arrays (N <= 20), quicksort does not perform as well as insertion sort. Because quicksort is recursive, these cases will occur frequently. A common solution is not to use quicksort recursively for small arrays, but instead use a sorting algorithm that is efficient for small arrays, such as insertion sort. Using this strategy can actually save about 15% in the running time. A good cutoff range is N=10. This also saves nasty degenerate cases, such as taking the median of three elements when there are only one or two. Quicksort C++ code a left Sort elements small at positions left, right, and a center. left small center median center

a[right-1] right large right median a left center right Quicksort C++ code a left small right a[right-1] pivot a left i center j right Partition the input array into two subarrays: one contains small elements; the other contains large elements. Analysis of Quicksort We will do the analysis for a quicksort, assuming a random pivot (no median-of-three partitioning) and no cutoff for small arrays. We take T(0) = T(1) = 1. The running time of quicksort is equal to the running time of the two recursive calls plus the linear time spent in the partition (the pivot selection takes only constant time). This gives the basic quicksort relation T(N) = T(i) + T(N-i-1) + cN where i = |S1| is the number of elements in S1. Analysis of Quicksort Worst-Case Analysis The pivot is the smallest element, all the time. Then i = 0 and if we ignore T(0)

= 1, which is insignificant, the recurrence is T(N) = T(N-1) + cN, N > 1 We telescope, using equation above repeatedly. Thus T(N-1) = T(N-2) + c(N-1) T(N-2) = T(N-3) + c(N-2) .. T(3) = T(2) + c(3) T(2) = T(1) + c(2) Adding up all these equations yields N T ( N ) T (1) c i O( N 2 ) i 2 Analysis of Quicksort Best-Case Analysis In the best case, the pivot is in the middle. To simply the analysis, we assume that the two subarrays are each exactly half the size of the original. Although this gives a slight overestimate, this is acceptable because we are only interested in a Big-Oh notation. T(N) = 2T(N/2) + cN Divide both sides of the equation by N. T ( N ) T ( N / 2) We will telescope using this c equation. N N /2 T ( N / 2) T ( N / 4) c N /2 N /4 T ( N / 4) T ( N / 8) c N /4 N /8 T (2) T (1) c 2 1 T ( N ) T (1) c log N N 1

Adding up all equations, we have which yields T(N) = cNlogN + N = O(NlogN) Analysis of Quicksort Average-Case Analysis Recall that T(N) = T(i) + T(Ni1) + cN (1) The average value of T(i), and hence T(N-i-1), is Equation (1) then becomes 2 (2) T ( N ) T ( j ) cN 1 N N1 T ( j) j 0 N1 N j 0 If Equation (2) is multiplied by N, it becomes NT ( N ) 2 T ( j )(3) cN N1 j 0 2 We telescope with one more equation. ( N 1)T ( N 1) 2 T ( (4) j ) c( N 1) (3) (4), we obtain NT(N) (N-1)T(N-1) = 2T(N-1) + 2cN c We rearrange terms and drop the insignificant c on the right, obtaining NT(N) = (N+1)T(N-1) + 2cN (5) Divide Equation (5) by N(N+1): N 2 j 0

T ( N ) T ( N 1) (6)2c N 1 N N 1 2 Analysis of Quicksort Average-Case Analysis (cont.) T ( N ) T ( N 1) 2c N 1 N N 1 (6) Now we can telescope. T ( N 1) T ( N 2) 2c N N1 N T ( N 2) T ( N 3) 2c N1 N 2 N1 T (2) T (1) 2c 3 2 3 Adding them up yields N 1 T ( N ) T (1) 1 2c N 1 2 i 3 i

Thus, we have This is the sum of harmonic series, which is O(logN). T (N ) O(log N ) N 1 and so T(N) = O(NlogN) The Selection Problem The problem: Given a list S of N elements and integer k > 0, find the k th smallest element. O(NlogN)-time algorithm Sort the N elements Pick up the kth element O(N + klogN)-time algorithm Build a heap on the N elements (O(N) time) Perform k deleteMin operations (O(klogN) time) The last element extracted from the heap is the answer. A Linear-Expected-Time Algorithm The algorithm (quickselect(S, k)) If |S| = 1, then k =1 and return the element in S as the answer. If a cutoff for small arrays is being used and |S| <= CUTOFF, then sort S and return the kth smallest element. Pick a pivot element, v S Partition the remaining elements in S (i.e., S-{v}) into S1 and S2, as was done with quicksort. Each elements in S1 is no larger than the pivot v; each elements in S2 is no smaller than the pivot v. If k <= |S1|, then the kth smallest element must be in S1. In this case, return quickselect(S1, k). If k = 1 + |S1|, then the pivot is the kth smallest element and we can return it as the answer. Otherwise, the kth smallest element lies in S2, and it is the (k-|s1|-1) st smallest element in S2. We make a recursive call and return quickselect(S2, k-|S1|-1). Examples (1) Suppose we want to find the 3rd smallest element in the list of 10 elements: 13, 81, 43, 92, 31, 65, 57, 26, 75, 0 In this example, k = 3, N = 10

13 81 43 92 31 65 57 26 75 0 select pivot 13 81 43 92 31 65 57 26 75 0 partition 13 43 31 26 0 57 65 81 92 75 S1 S2 0 13 26 31 43 57 65 75 81 92 3rd smallest element Since k <= |S1|, recursively find the 3rd smallest element on S1, i.e.,call quickselect(S1, k). Examples (2) Suppose we want to find the 6th smallest element in the list of 10 elements: 13, 81, 43, 92, 31, 65, 57, 26, 75, 0 In this example, k = 6, N = 10 13 81 43 92 31 65 57 26 75 0 select pivot 13 81 43 92 31 65 57 26 75 0 partition 13 43 31 26 0 57 65 81 92 75 S1 S2 Since k = |S1|+1, we found the 6th smallest element, i.e. 57 Examples (3) Suppose we want to find the 8th smallest element in the list of 10 elements: 13, 81, 43, 92, 31, 65, 57, 26, 75, 0 In this example, k = 8, N = 10 13 81 43 92 31 65 57 26 75 0 select pivot 13 81 43 92 31 65 57 26 75 0 partition 13 43 31 26 0 57 65 81 92 75 S1 S2

0 13 26 31 43 57 65 75 81 92 8th smallest element Since k > |S1|+1, the kth smallest element lies in S2, and it is the (k-|S1|-1)st smallest element in S2. Thus, we recursively find the 2nd (8 5 1 = 2) smallest element on S2, i.e., call quickselect(S2, 2). Quickselect C++ code 0 1 2 3 4 5 6 7 8 9 10 a left right pivot After partitioning 0 1 2 3 4 5 6 7 8 9 10 a left S1 includes small elements i right S2 include large elements k-i-1 When the algorithm terminates, the k th smallest element is in position k-1 (because arrays start at index 0). Analysis of Quickselect Like quicksort, we do the analysis for a quickselect, assuming a random pivot (no median-of-three partitioning) and no cutoff for small arrays. We take T(0) = T(1) = 1. The running time of quickselect is equal to the running time of one recursive call plus the linear time spent in the partition (the pivot selection takes only constant time). This gives the basic quickselection relation T(N) = T(i) + cN where i is the number of elements in the subarray on which we need to perform a recursive call. Analysis of Quickselect Worst-Case Analysis The pivot is the smallest (resp., largest) element, all the time, and k = N (resp.,

1). Then, we need to perform a recursive call on a subarray with size of N-1. Thus, the recurrence is T(N) = T(N-1) + cN, N > 1 We telescope, using equation above repeatedly. Thus T(N-1) = T(N-2) + c(N-1) T(N-2) = T(N-3) + c(N-2) .. T(3) = T(2) + c(3) T(2) = T(1) + c(2) Adding up all these equations yields N T ( N ) T (1) c i O( N 2 ) i 2 Analysis of Quickselect Average-Case Analysis Recall that T(N) = T(i) + cN (1) where i is the number of elements in the subarray on which we need to perform a recursive call. For the average case, we assume that each of the sizes for the subarray on which we need to perform a recursive call is equally likely, and hence has probability 1/N. Thus, the average value of T(i), is 1 T ( j ) N Equation (1) then becomes 1 (2) T ( N ) T ( j ) cN N1 j 0 N1 N j 0 If Equation (2) is multiplied by N, it becomes NT ( N ) T ( j ) (3) cN N1 2 j 0 We telescope with one more equation.

( N 1)T ( N 1) T ((4) j ) c ( N 1) (3) (4), we obtain NT(N) (N-1)T(N-1) = T(N-1) + 2cN c N 2 j 0 2 Analysis of Quickselect Average-Case Analysis (cont.) We rearrange terms and drop the insignificant c on the right, obtaining NT(N) = NT(N-1) + 2cN (5) Divide Equation (5) by N: T(N) = T(N-1) + 2c(6) Now we can telescope. T(N-1) = T(N-2) + 2c T(N-2) = T(N-3) + 2c T(3) = T(2) + 2c T(2) = T(1) + 2c Adding them up yields T(N) = T(1) + 2c*(N-1) Thus, we have T(N) = O(N) Bucket Sort Although any general sorting algorithm that uses only comparisons requires (NlogN) time in the worst case, in some special cases, it is still possible to sort in linear time. For bucket sort, the input A1, A2, , AN must consist of only positive integers smaller than M. The algorithm Keep an array called count, of size M, which is initialized to all 0s. Thus, count has M cells, or buckets, which are initially empty. While Ai is read, increment count[Ai] by 1. After all the input is read, scan the count array, printing out a representation of the sorted list. Bucket Sort Example Suppose we want to sort: 3 6 4 1 3 4 1 4 0 1 3 6

3 4 5 6 7 1 3 4 1 4 2 4 0 1 count 0 0 3 4 5 6 0 0 0 0 2 0 Scan the input array and increase the corresponding bucket of count 0 1

3 6 4 0 1 count 0 0 0 1 3 6 3 4 5 6 7 0 1 1 3 4 1 4 3 6 2 2

4 0 1 count 0 0 3 4 5 6 1 0 0 0 2 0 2 4 0 1 count 0 0 3 4 5 6 7 0 1

1 3 4 1 4 3 6 2 0 3 4 5 6 1 1 0 1 3 4 5 6 7 1 3 4 1 4 2

0 2 4 0 1 count 0 1 3 4 5 6 1 0 0 1 3 4 5 6 7 1 3 4 1 4 2 0 3

4 5 6 1 1 0 1 Bucket Sort Example Suppose we want to sort: 3 6 4 1 3 4 1 4 Scan the input array and increase the corresponding bucket of count (cont.) 0 1 3 6 2 4 0 1 count 0 1 2 0 1 3 6 coun t 4 0

1 0 2 3 4 5 6 7 0 1 1 3 4 1 4 3 6 3 4 5 6 0 2 1 0 1 3

4 5 6 7 0 1 1 3 4 1 4 3 6 2 2 0 3 4 5 6 2 2 0 1 2 4 0 1

count 0 1 2 coun t 4 0 1 0 2 3 4 5 6 7 1 3 4 1 4 3 4 5 6 0 2 2 0

1 3 4 5 6 7 1 3 4 1 4 2 2 0 3 4 5 6 2 3 0 1 Bucket Sort Example Suppose we want to sort: 3 6 4 1 3 4 1 4 0 1 coun 0 t

2 2 0 3 4 5 6 2 3 0 1 Print out the sorted list (scan the array count) 0 1 0 2 0 1 0 2 0 1 coun 0 t 0 2 coun 0 t 0 2

coun t 0 2 0 1 0 2 0 1 coun 0 t 2 coun t coun t coun t 1 1 2 0 2 0 2 0 2 0 2 0 3

4 5 6 2 3 0 1 3 4 5 6 2 3 0 1 3 4 5 6 2 3 0 1 3 4 5 6

2 3 0 1 3 4 5 6 2 3 0 1 3 4 5 6 0 2 3 0 1 2 3 4 5 6 2

3 0 1 2 0 No 0s Two 1s No 2s Two 3s Three 4s No 5s One 6 0 1 2 3 4 5 6 7 output 0 1 1 1 0 1 1

1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 2 3 4 5 6 7 output 2 3 4

5 6 7 output 2 3 2 3 3 4 5 6 7 output 3 3 4 5 6 3 4 4 4 7 output 3 4 5 6 3

3 4 4 4 2 3 4 5 6 7 3 4 4 4 6 2 3 7 output output Bucket Sort Running Time Initializing array count to all 0s takes O(M) time Scanning the input array and increasing the corresponding element of count takes O(N) time Scanning array count and printing out the representation of the sorted list takes O(M+N) time Totally, bucket sort takes O(M+N) time In practice, we usually use bucket sort when we have M = O(N), in

which case the running time is O(N).