Algorithms in C#

This is part 2 of Algorithms questions in Interviews.(Part 1| Part 3)
quick_sort

Quicksort Algorithm

public void QuickSort(int[] array, int left, int right)
{
	int i = left;
	int j = right;
	int pivot = array[(left + right) / 2];
	while (true)
	{
		while (array[i] < pivot)
			i++;
		while (pivot < array[j])
			j--;
		if (i <= j)
		{
			Swap(array, i, j);
			i++;
			j--;
		}
		if (i > j) 
			break;
		if (left < j)
			QuickSort(array, left, j);
		if (i < right)
			QuickSort(array, i, right);
	}
}

private void Swap(int[] array, int a, int b)
{
	var temp = array[a];
	array[a] = array[b];
	array[b] = temp;
}

That code is actually a fairly clear implementation of quicksort.
The key to understanding this particular program is that every recursive function call receives the same full string. So the function has to set its own boundaries, i.e., “left” and “right” and ignore the remainder of the string. Every recursive function call only deals with partitioning a small part of the string.

The original function call partitions the string into portions less than the pivot (lower portion) and greater than the pivot (upper portion), leaving any string values equal to the pivot in a “no man’s land” somewhere in between the left and right portions.

As soon as it gets to the recursive function calls, it gets a bit more murky, and it is important to understand that these lower and upper portions are different from the “left” and “right” variables. The “left” variable is the original position of the left boundary of the entire string that the function call is supposed to operate on, and similarly for the “right” variable.

The key to the algorithm is understanding that the first function call leaves nothing necessarily sorted in the upper or lower portions. However, it removes one or more partition values from consideration and ensures that they are above all lower string values, and below all upper string values, i.e., in the “middle” of the string.

This process is repeated recursively on both of the unsorted upper and lower portions of the string until eventually reaching an upper or lower portion size of two or fewer values, which must be sorted already as a result of being partitioned.

The quicksort algorithm has a worst case performance of O(N^2) if the pivot value is always an extreme value, and a best case performance of O(N log N) if the pivot value is close to the middle of the string. For instance, when sorting 31 characters and assuming a perfect median choice of pivot,

first stage:

lower 15, pivot, upper 15

second stage:

(lower 7, pivot, upper 7), pivot, (lower 7, pivot, upper 7)

third stage:

((lower 3, pivot, upper 3), pivot, (lower 3, pivot, upper 3)), pivot, ((lower 3, pivot, upper 3), pivot, (lower 3, pivot, upper 3))

fourth stage:

(((lower 1, pivot, upper 1), pivot, (lower 1, pivot, upper 1)), pivot, ((lower 1, pivot, upper 1), pivot, (lower 1, pivot, upper 1))), pivot, (((lower 1, pivot, upper 1), pivot, (lower 1, pivot, upper 1)), pivot, ((lower 1, pivot, upper 1), pivot, (lower 1, pivot, upper 1)))

Four stages is less than or equal to the base-two logarithm of 31, and at every stage the algorithm is linear (although performed in multiple distinct recursive function calls at each level), so 31 steps are performed, i.e., N steps.

So the total order of the algorithm is 4 stages times 31, or approximately N times log N.

In reality, sometimes a pivot is not the median, and may even be an extreme value, in which case the “lower” or “upper” portions are empty. The algorithm might remove only one value from consideration at each stage, resulting in a total of N-1 stages to complete the algorithm. At every stage, there would be N steps of work, so the total order would be N times (N-1), which is O(N^2) since there is a product of N with N.

All in all, quicksort is a very good algorithm, and very hard to improve, as long as one’s algorithm avoids deliberate pernicious cases which could otherwise be exploited to feed a known codebase with input which produces a pivot sequence of extreme values.

Advertisements

2 thoughts on “Algorithms in C#

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s