Quicksort

Quicksort is a sorting algorithm that runs on average O(nlogn) and does in-place sorting. This saves space because it does not require a temporarily array to store values like in MergeSort.

The key concept behind Quicksort is the partitioning around a pivot. Choose one of the elements in the array as a pivot. Then rearrange the array so that everything less than the pivot is to its left and everything greater is to its right. Note that this rearrangement does not mean the entire array has to be sorted after this one partition. However, the pivot does end up in the "right" spot. That is, the pivot will not be moved anymore because it is already in the spot where it will be in the sorted array.

Partitioning can be done in linear time without allocating any extra memory and reduces the problem size.

QuickSort(Array a, length n)

• if n = 1 return
• p = ChoosePivot(a, n)
• Parition a around p
• QuickSort(first part)
• QuickSort(second part)

Partitioning

The easy to partition the array would be to allocate a temporary array using O(n) space. This will still partition around the pivot in O(n) time. Assuming the pivot is the first element in the array, you traverse the array and keep a partitioned part and an unpartitioned part. You use one pointer to traverse the array and another to point to the first element in the partitioned part larger than the pivot. When you find an element smaller than the pivot, you simply swap it with the pointer's element. When you are finished, swap the element one before the pointer with the pivot to finish partitioning.

Finding the Optimal Pivot

So far, we have used the first element in the array as the pivot. What if the array were already sorted, or reverse sorted? Then partitioning would leave the pivot either in the same spot or in the back. Then we'd recursively call QuickSort on the (n-1) length subarray. We do this over and over until the array is sorted. This takes O(n²) time.

What would be a better way? If we want to balance the two subarrays so that they are about equal in length, then we would want to find the median. Thus, if we are lucky enough to be able to get the median as the pivot every time, then the algorithm would be much like MergeSort without the extra memory allocation, running in O(nlogn).

What if finding the median is too hard? What other choices do we have. Well, it is established that if we are able to split the subarrays just 25%/75%, then we will still have O(nlogn) running time. If we had 100 elements, we just have to pick an element that is anywhere from 25th smallest to 75th smallest. This is half the total elements, so we have 50% chance of picking this pivot.

As a side note, this is an instance of adding randomness to our algorithm. Randomness is actually really useful in many applications because it makes things easier, more elegant, and efficient, but more on this later.

In conclusion, we have established that a randomized QuickSort has an average running time of O(nlogn), a blazingly fast algorithm without the extra space allocation.

Inversions

The first thing I've learned from Algorithms: Design and Analysis Part I is how to count inversions.

What is an inversion? An inversion is a pair of objects that are out of order. If we are given an array and our goal is to sort from low to high, an inversion would be two items a_i and a_j such that a_i > a_j, but  i < j. We can see that they are misplaced.

An array with no inversions is one that is sorted and an array with the maximum number of possible inversions would be sorted in reverse order. Thus, counting inversions is a way of checking how sorted or unsorted something is.

How do we find the number of inversions? Well, the naive and obvious way would be to traverse the array and compare each element to every other element. This algorithm would be O(n^2). Can we do it a better way? Yes. We'll use the divide and conquer method and piggyback on the MergeSort algorithm to do it in O(nlogn). By counting the number of inversions, we will also be sorting it.

By splitting the array in half, we know that:

total inversions = inversions in left + inversions in right + split inversions

A split inversion is one in which we have one element on the left half that will be an inversion with an element on the right half. To find the number of inversions in each half, we'll just recursively call the algorithm on each half. Finding the number of split inversions is the trickier task.

Say we have two halves, [2, 5, 6] and [1, 3, 8]. The number of split inversions will actually be counted when we do the merge subroutine. So the way merge works is that it will keep track of two pointers, one to the front of each half array. It will take the smaller element and increment the pointer. If an element is taken from the second array, we know that it must be smaller than the element in the first subarray, and subsequently every element thereafter. Then we can just sum up the number of elements left in the first array each time the second subarray is chosen from before the first.

Here is my code for this algorithm:

int countInversions(int[] a) { return countInversions(a, 0, a.length, new int[a.length]); } int countInversions(int[] a, int start, int end, int[] t) { if (start == end - 1) return 0; int mid = (start + end) / 2; int x = countInversions(a, start, mid, t); int y = countInversions(a, mid, end, t); int z = subroutine(a, start, mid, end, t); return x + y + z; } int subroutine(int[] a, int start, int mid, int end, int[] t) { int i = start; int j = mid; int k = i; int count = 0; while (i < mid && j < end) if (a[i] < a[j]) t[k++] = a[i++]; else { t[k++] = a[j++]; count += (mid - i); } System.arraycopy(a, i, t, k, mid - i); System.arraycopy(a, j, t, k, end - j); System.arraycopy(t, start, a, start, end - start); return count; }