Quick sort with example and program

Quick Sort is also based on the concept of Divide and Conquer, just like merge sort.

Quick sort is a fast sorting algorithm used to sort a list of elements. Quick sort algorithm is invented by C. A. R. Hoare.

Quicksort uses the divide-and-conquer strategy to sort the given list of elements. This means that the algorithm breaks down the problem into sub problems until they become simple enough to solve directly.

Algorithmically this can be implemented either recursively or iteratively. However, the recursive approach is more natural for this problem.

It is also called partition-exchange sort. This algorithm divides the list into three main parts:

1. Elements less than the Pivot element
2. Pivot element(Central element)
3. Elements greater than the pivot element

Quick sort is naturally recursive. We partition the array into two sub-arrays, and then re-start the algorithm on each of these sub-arrays. The partition procedure involves choosing some object (usually, already in the array); If some other object is greater than the chosen object, it is added to one of the sub-arrays, if it is less than the chosen object, it is added to another sub-array. Thus, the entire array is partitioned into two sub-arrays, with one sub-array having everything that is larger than the chosen object, and the other sub-array having everything that is smaller. 

Example:

Quick sort java progr

class QuickSortDemo
{
public static void main(String[] args)
{
int[] arr = { 65, 35, 15, 90, 75, 45,40, 60, 95, 25, 85, 55 };
System.out.print("\n Unsorted array: ");
display( arr );
quickSort( arr, 0, arr.length-1 );
System.out.print("\n Sorted array: ");
display( arr );
}
static void quickSort(int a[], int left, int right)
{
int newleft = left, newright = right;
int amid, tmp;
amid = a[(left + right)/2]; // pivot is amid
do // do-while-loop
{
while( (a[newleft] < amid) && (newleft < right))
newleft++;
while( (amid < a[newright]) && (newright > left))
newright--;
if(newleft <= newright)
{ tmp = a[newleft];
a[newleft] = a[newright];
a[newright] = tmp;
newleft++; newright--;
}
} while(newleft <= newright); // end of do-while-loop
if(left <newright) quickSort(a, left, newright);
if(newleft < right) quickSort(a, newleft, right);
}
static void display( int a[] )
{
for( int i = 0; i < a.length; i++ )
System.out.print( a[i] + " " );
}
}

Variable a is an integer array of size, n. The left and right invoke procedure and they are initialized with 0 and n -1 respectively; and are the current lower and upper bounds of the sub-arrays. The indices newleft and newright are used to select certain elements during the processing of each sub-array. Variable amid is the element which is placed in its final location in the array.

Index left scans the list from left to right, and index right scans the list from right to left. A swap is performed when left is at an element larger than the pivot and right is at an element smaller than the

pivot. A final swap with the pivot completes the divide step. The pivot element is placed in its final proper position in the array. We take the pivot as the middle element of the array (or sub-array).