Quick Sort Introduction

Quick Sort's approach is to take Merge Sort's philosophy but eliminate the need for the merge. Instead, it makes sure that every data item in the first sub-list is less than every data item in the second sub-list. The procedure that accomplished that is called "partitioning" the data. After the paritioning,each of the sub-lists are sorted, which will cause the entire array to be sorted.

quickSort(first,int last) 
{
	if (first < last) /* if the part being sorted isn't empty */
	{
		mid = quickParition(first,last);
		if (mid-1 > first)
			quickSort(first,mid-1);
		if (mid+1 < last)
			quickSort(mid+1,last);
	}	
	return;
}

The hard part of Quick Sort is the partitioning. That algorithm looks at the first element of the array (called the "pivot"). It will put all of the elements which are less than the pivot in the lower portion of the array and the elements higher than the pivot in the upper portion of the array. When that is complete, it can put the pivot between those sections and Quick Sort will be able to sort the two sections separately.

The details of the partitioning algorithm depend on counters which are moving from the ends of the array toward the center. Each will move until it finds a value which is in the wrong section of the array (larger than the pivot and in the lower portion or less than the pivot and in the upper portion). Those entries will be swapped to put them into their appropriate sections and the counters will continue searching for out of place values. When the two counters cross, partitioning is complete and the pivot can be swapped to its proper place between the two sections.

QuickParition(first, last) 
{

	mid_val = data[first]; /* This is the pivot value */
	i = first+1;
	j = last;
	while (i<=j)
	{
		while ((i < last) && (data[i] <= mid_val))
			i++;	
		while ((j >= first) && (data[j] > mid_val))
			j--;	
		if (i < j)
			swap(i,j);
		else
			i++;
	}	
	if (j != first)
		swap(j,first);
	return j;
}