procedure for Quick sort:

Quicksort is significantly faster than other algorithms like bubble sort, because its inner loop can be efficiently implemented on most architectures. Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists. Quicksort is also known as "partition-exchange sort".

Qucik-sort logic:

· Pick an element, called a pivot, from the list (here we are choosing last element).

· Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way).

· After this partitioning, the pivot is in its final (proper) position. This is called partitioning.

· Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

· The base (terminating) case of the recursion are lists of size zero or one, which are always sorted.

Complexity: The time complexity of Selection sort is shown below in three different cases and worst-case space complexity.

Worst Case	Best Case	Average Case	Worst case Space Complexity
O(n2)	O(nlogn)	O(nlogn)	O(n)

Example: The quick sort takes the last element (9) and places it such that all the numbers in the left sub-list are smaller and all the numbers in the right sub-list are bigger. It then quick sorts the left sub-list ({1}) and then quick sorts the right sub-list ({63,72,64,58,14,27}) in similar fashion. This is a recursive algorithm, since it is defined in terms of itself. This reduces the complexity of programming.

Initial Data	27	63	1	72	64	58	14	9
1st pass	1	< 9 >	63	72	64	58	14	27
			63	72	64	58	14	27
			14	< 27 >	64	58	72	63
2nd pass	1	9	14	27	64	58	72	63
					64	58	72	63
					58	< 63 >	72	64
3rd pass	1	9	14	27	58	63	72	64
							72	64
							< 64 >	72
4th pass	1	9	14	27	58	63	64	72

Program: The following program uses Quick sort algorithm to sort the elements of the array.

import java.io.*;

class QuickSort

{

public static void qsort(int a[],int min,int max)

{

int t,v,i,j;

if (max > min)

{

v = a[max];

i=min;

j = max-1;

do

{

while ((a[i]

i++;

while ((a[j]>v) && j!=0)

j--;

t = a[i];

a[i] = a[j];

a[j] = t;

} while (j > i);

a[j] = a[i];

a[i] = a[max];

a[max] = t;

qsort(a,min,i-1);

qsort(a,i+1,max);

}

}

public static void main(String as[]) throws Exception

{

int i,n,a[]=new int[10];

InputStreamReader isr=new InputStreamReader(System.in);

BufferedReader br=new BufferedReader(isr);

System.out.println("How many values:");

n=Integer.parseInt(br.readLine());

System.out.println("Enter Values:");

for(i=0;i

a[i]=Integer.parseInt(br.readLine());

qsort(a,0,n-1);

System.out.println("After Sorting");

for(i=0;i

System.out.print("\t"+a[i]);

}

}

Output:

How many values: 4

Enter Values:

45

36

87

12

After Sorting:

12 36 45 87