Quick Sort

• Quick sort is a widely used sorting algorithm developed by C. A. R. Hoare that makes O(n log n) comparisons in the average case to sort an array of n elements. However, in the worst case, it has a quadratic running time given as O(n2). Basically, the quick sort algorithm is faster than other O(n log n) algorithms, because its efficient implementation can minimize the probability of requiring quadratic time. Quick sort is also known as partition exchange sort.
• Like merge sort, this algorithm works by using a divide-and-conquer strategy to divide a single unsorted array into two smaller sub-arrays.

The quick sort algorithm works as follows :-

1.) Select an element pivot from the array elements.
2.) Rearrange the elements in the array in such a way that all elements that are less than the pivot appear before the pivot and all elements greater than the pivot element come after it (equal values can go either way). After such a partitioning, the pivot is placed in its final position. This is called the partition operation.
3.) Recursively sort the two sub-arrays thus obtained. (One with sub-list of values smaller than
that of the pivot element and the other having higher value elements.)

• Like merge sort, the base case of the recursion occurs when the array has zero or one element because in that case the array is already sorted. After each iteration, one element (pivot) is always in its final position. Hence, with every iteration, there is one less element to be sorted in the array.
• Thus, the main task is to find the pivot element, which will partition the array into two halves. To understand how we find the pivot element, follow the steps given below.

Quick sort works as follows :-

1.) Set the index of the first element in the array to loc and left variables. Also, set the index of
the last element of the array to the right variable.
That is, loc = 0, left = 0, and right = n–1 (where n in the number of elements in the array)

2.) Start from the element pointed by right and scan the array from right to left, comparing each
element on the way with the element pointed by the variable loc.
That is, a[loc] should be less than a[right].
(a) If that is the case, then simply continue comparing until right becomes equal to loc. Once
right = loc, it means the pivot has been placed in its correct position.
(b) However, if at any point, we have a[loc] > a[right], then interchange the two values and
jump to Step 3.
(c) Set loc = right.

3.) Start from the element pointed by left and scan the array from left to right, comparing each
element on the way with the element pointed by loc.
That is, a[loc] should be greater than a[left].
(a) If that is the case, then simply continue comparing until left becomes equal to loc. Once
left = loc, it means the pivot has been placed in its correct position.
(b) However, if at any point, we have a[loc] < a[left], then interchange the two values and
jump to Step 2.
(c) Set loc = left.

Sort the elements given in the following array using quick sort algorithm.

** Write an algorithm to implement quick sort **
        
        QuickSort(low,high)
	1.	If (low > high):
			a.  Return
	2.	Set pivot = arr[low]
	3.	Set i = low + 1
	4.	Set j = high
	5.	Repeat step 6 until i > high or arr[i] > pivot // Search for an					 
	6.	Increment i by 1
	7.	Repeat step 8 until j < low or arr[j] < pivot // Search for an element	
        8.	Decrement j by 1
	9.	If i < j: // If greater element is on the left of smaller element
		 	  a.  Swap arr[i] with arr[j]
	10.	If i <= j:
			  a.  Go to step 5 // Continue the search
	11.	If low < j:
			  a.  Swap arr[low] with arr[j] // Swap pivot with last element in
	12.	QuickSort(low, j – 1) // Apply quicksort on list left to pivot
	13.	QuickSort(j + 1, high) // Apply quicksort on list right to pivot

Complexity of Quick Sort

In the average case, the running time of quick sort can be given as O(n log n). The partitioning of
the array which simply loops over the elements of the array once uses O(n) time.

In the best case, every time we partition the array, we divide the list into two nearly equal pieces. That is, the recursive call processes the sub-array of half the size. At the most, only log n
nested calls can be made before we reach a sub-array of size 1. It means the depth of the call tree is O(log n). And because at each level, there can only be O(n), the resultant time is given as O(n log n) time.

Practically, the efficiency of quick sort depends on the element which is chosen as the pivot.
Its worst-case efficiency is given as O(n2). The worst case occurs when the array is already sorted (either in ascending or descending order) and the left-most element is chosen as the pivot.

However, many implementations randomly choose the pivot element. The randomized version
of the quick sort algorithm always has an algorithmic complexity of O(n log n)

					*******************
					Programming Example
					*******************

1. Write a program to implement quick sort algorithm.

#include<stdio.h>
#include<conio.h>

void quicksort(int a[],int first, int last)
{
	int pivotindex,tmp,i,j;
	if(first<last)
	{
		pivotindex=first;
		i=first;
		j=last;
		while(i<j)
		{
			while(a[i]<=a[pivotindex] && i<last)
			{
				i++;
			}
			while(a[j]>a[pivotindex])
			{
				j--;
			}
			if(i<j)
			{
			      tmp=a[i];
			      a[i]=a[j];
			      a[j]=tmp;
			}
		}
	      tmp=a[pivotindex];
	      a[pivotindex]=a[j];
	      a[j]=tmp;
	      quicksort(a,first,j-1);
	      quicksort(a,j+1,last);
	}
}

int main()
{
	int a[100],n,i;
	clrscr();
	printf("\n\n\t Enter the number...>");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		printf("\n\t Enter element in the list...>");
		scanf("%d",&a[i]);
	}
	quicksort(a,0,n-1);
	for(i=0;i<n;i++)
	{
		printf("\n\t sorted element...>%d",a[i]);
	}
	getch();
	return 0;
}