## Algorithm :

Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.

The steps are:

1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

The base case of the recursion are lists of size zero or one, which never need to be sorted.

 An example of quicksort thanks Wikipedia

Java version of the QuickSort  is given below :

``` * To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package sort.quicksort;

/**
*
* @author ACHCHUTHAN
*/
public class Quicksort {
int array[];
int size;

public Quicksort(int n){
size=n;
//create array with size n+1
array=new int[n+1];
//asign value into the array
for (int i=0;i<n;i++){
array[i]=(int) Math.round(Math.random()*89+10);
}
//set the last element as big value
array[n]=99999;
}
public int partition(int p, int q) {
int i = p;
int j = q + 1;
// Get the pivot element from the middle of the list
int pivot = array[p];
// Divide into two lists
do {
// If the current value from the left list is smaller then the pivot
// element then get the next element from the left list
do {
i++;// As we not get we can increase i
} while (array[i] < pivot);
// If the current value from the right list is larger then the pivot
// element then get the next element from the right list
do {
j--;// As we not get we can increase j
} while (array[j] > pivot);
// If we have found a values in the left list which is larger then
// the pivot element and if we have found a value in the right list
// which is smaller then the pivot element then we exchange the values.
if (i <j) {
swap(i, j);
}

} while (i <j);
//swap the pivote element and j th element
swap(p, j);
return j;
}

private void swap(int p, int j) {
//exachage the elements
int temp = array[p];
array[p] = array[j];
array[j] = temp;
}

public void quicksort(){
// Recursion
quicksort(0, size-1);
}

public void quicksort(int p, int q) {
int j;
if (p < q) {
// Divide into two lists
j = partition(p, q);
// Recursion
quicksort(p, j - 1);
quicksort(j + 1, q);
}
}
public void print(){
//print the elements of array
for(int i=0;i<size;i++){
System.out.print(array[i]+" | ");
}
System.out.println();

}

public static void main(String args[]) {
Quicksort q = new Quicksort(15);
System.out.println("Before Sort <<<<<<<<<<<<<<<<<<<<<");
q.print();
q.quicksort();
System.out.println("After Sort > > > > > > > > > > > >");
q.print();
System.out.println("=======+============+=======+============+=======+============");
Quicksort q2=new Quicksort(125);
System.out.println("Before Sort <<<<<<<<<<<<<<<<<<<<<");
q2.print();
q2.quicksort();
System.out.println("After Sort > > > > > > > > > > > >");
q2.print();
System.out.println("=======+============+=======+============+=======+============");
Quicksort q3=new Quicksort(5);
System.out.println("Before Sort <<<<<<<<<<<<<<<<<<<<<");
q3.print();
q3.quicksort();
System.out.println("After Sort > > > > > > > > > > > >");
q3.print();

}
}```

Output of this program
run:
Before Sort <<<<<<<<<<<<<<<<<<<<<
85 | 61 | 48 | 78 | 68 | 57 | 15 | 36 | 80 | 54 | 83 | 17 | 69 | 53 | 70 |
After Sort > > > > > > > > > > > >
15 | 17 | 36 | 48 | 53 | 54 | 57 | 61 | 68 | 69 | 70 | 78 | 80 | 83 | 85 |
=======+============+=======+============+=======+============
Before Sort <<<<<<<<<<<<<<<<<<<<<
60 | 92 | 42 | 63 | 70 | 60 | 92 | 29 | 37 | 95 | 89 | 27 | 57 | 49 | 14 | 19 | 41 | 18 | 71 | 46 | 80 | 48 | 36 | 34 | 65 |
After Sort > > > > > > > > > > > >
14 | 18 | 19 | 27 | 29 | 34 | 36 | 37 | 41 | 42 | 46 | 48 | 49 | 57 | 60 | 60 | 63 | 65 | 70 | 71 | 80 | 89 | 92 | 92 | 95 |
=======+============+=======+============+=======+============
Before Sort <<<<<<<<<<<<<<<<<<<<<
32 | 92 | 75 | 52 | 56 |
After Sort > > > > > > > > > > > >
32 | 52 | 56 | 75 | 92 |
BUILD SUCCESSFUL (total time: 1 second)