09Data Structures---Sorting algorithms: Quicksort

The course is mainly covered Sorting algorithms: Quicksort.Generally covered Pseudo-code for partition in QuickSortInPlace,Performance of Quicksort,Quicksort on Linked List,Quicksort Algorithm and so on.

1.Sorting algorithms: Quicksort Numerous sorting algorithms are there. We have discussed so far about • Insertion sort • Merge sort • Heap sort We now take a look at Quicksort that on an average runs 2-3 faster that Merge sort or Heap sort.

2.Quicksort (Divide-and-conquer) The major steps: (Pivot) Given an array of numbers, choose a pivot p (Partition) Reorder the elements, so that all elements < p appear before p, and all elements > p appear after p. The elements equal to p can appear anywhere in between the smaller (than p) and the larger (than p) elements. (Recursion) Apply this to the sub-arrays in the partition, until their sizes become one, the base case. (Concatenation) Combine the sorted sub-arrays into a sorted queue

3.Any element can be chosen as the pivot, but usually the last one is picked since it gives the best performance. Assume that the initial values are in a queues S //partition the queue public static int void(quicksort Queue S){ int pivot = S.last(); // construct three queues L, G, E (not shown) while !S.isEmpty() { int element = S.dequeue(); if (element < pivot) L.enqueue (element); else if (element = pivot) E.enqueue (element) else G.enqueue (element); } // Recursive step quicksort(L); quicksort(G); //Concatenate results while (!L.isEmpty) S.enqueue(L.dequeue()); while (!E.isEmpty) S.enqueue(L.dequeue()); while (!G.isEmpty) S.enqueue(L.dequeue()); }

4.Example 85 24 63 45 12 31 96 50 L E G 24 45 12 31 50 85 63 96 L E G L E 24 12 31 45 85 63 96 E G E G 12 24 63 85 Complexity: Best case O(n log n) Why? Complexity: Worst case O(n2) Why? Can we avoid using queues and shuffle the elements in- place within the array to sort the elements? Yes.

5.Array Version: Algorithm 1 sub-array 0 p r n-1 Pseudocode for Quicksort QuicksortInPlace (A, p, r) If p < r then q = partition (A, p, r) QuicksortInPlace (A, p, q-1) QuicksortInPlace (A, q+1, r) The value of q divides the array into two parts. The initial call is QuicksortInPlace (A, 0, length(A)-1)

6.Pseudo-code for partition in QuickSortInPlace partition (A, p, r) pivot = A[r] i = p-1 for j = p to r-1 { if A(j) < pivot { i=i+1 swap (A[i], A[j]) } swap (A[i+1], A[r]) // q = i+1 divides the array

7.An example of partition

8.Performance of Quicksort Quick sort vs Merge sort Both are comparison-based sorts. Merge sort simply divides the list into two (almost) equal parts, but does some extra work before merging the parts. Quicksort does the extra work before dividing it into parts, but merging is simple concatenation. Quicksort is the fastest known comparison-based sort The link https://www.youtube.com/watch?v=YvTW7341kpA Contains an old (1980’s) but nice video on three sorting techniques

9.What if all keys equal? Such keys can go to either half. Algorithm 1 discussed earlier will lead to O(n2) time complexity i j A[] 85 85 85 85 85 85 85 85 p r i j A[] 85 85 85 85 85 85 85 85 p r What if all the keys are already sorted? i j A[] 2 7 8 17 48 60 75 85 p r i j A[] 2 7 8 17 48 60 75 85 p r Again, Algorithm 1 will lead to O(n2) time complexity.

10.Randomly choosing the pivot overcomes the second problem. Randomly choose pivot and swap it with the last item Random pivot helps (1 / 4 − 3 / 4 ) split in most cases). Also, for large arrays, Median of three (random choices) works even better. Take three randomly chosen array indices and pick the middle one to pick the pivot. Quicksort on Linked List Split into three lists L (less than) G (greater than), E (equal to pivot). Of these, sort only L, G not E. It reduces the effort, but does not work with array in-place) Sort (5, 7, 5, 0, 6, 5, 5) 0 | 5, 5, 5, 5 | 7, 6 Random pivot choice is annoying for Linked List.

11.Quicksort Algorithm 2 It is a better version of Quicksort. To sort A[p] – A[r], use two pointers i and j Initialize i= p-1 and j = r (Between i,j sandwich the items to be sorted). Move i from left to right as long as A[i]<pivot, Move j from right to left as long as A[j]>pivot. Swap (A[i], A[j])

12.i j 3 8 0 9 4 7 5 i j 3 8 0 9 4 7 5 now swap i j 3 4 0 9 8 7 5 i j 3 4 0 9 8 7 5 now swap j i 3 4 0 9 8 7 5 i > j

13.public static void quicksort(int[ ] a, int low, int high){ if (low < high) { int pivotIndex = random number from low to high; pivot = a[pivotindex]; a[pivotIndex] = a[high]; // Swap pivot with last a[high] = pivot; int i = low - 1; int j = high; do { do { i++; } while (a[i] < pivot); do { j--; } while ((a[j] > pivot)&&(j > low)); if (i < j) { swap a[i] and a[j]; } } while (i < j); a[high] = a[i]; a[i] = pivot; // Put pivot where it belongs quicksort(a, low, i - 1); // Sort left sub-array quicksort(a, i + 1, high); // Sort right sub-array } }

14.Notes Works great with both arrays containing all equal elements, and already sorted arrays, Can the "do {i++}" loop walk off the end of the array and generate an out-of- bounds exception? No, because a[high] contains the pivot, so i will stop advancing when i == high (if not sooner). There is no such assurance for j, so the "do {j--}" loop explicitly tests whether "j > low" before retreating.