Java Buzz Forum - Quicksort algorithm in java with example program

Quick sort uses divide and conquer algorithm.
First will be divided in to two parts based on some pivot element. All elements which are less than pivot element will be placed left and and all elements which are greater than pivot will be in right part.

After than these two lists will be sorted in same manner until became one.
Quick sort will be sorting these elements without using extra space that is the reason it is called in place sorting algorithm.
Using the first or middle elements as an pivot element. it splits the arrays by re arranging the elements like every thing that is less than pivot will come left side and all elements greater than or equal to pivot will come right side.
Now pivot is in middle and correct place it left and right arrays sorted then entire array will be sorted.
Quick sort exactly will do the same it will sort left and right recursively.
If size of input is very less merge sort will be time consuming.
For smaller inputs quick sort is faster than merge sort.
Time complexity of Quicksort default case is O(n log n).
Worst case Time complexity of Quicksort is O(n²).

Steps to implement quick sort algorithm:

Create a array with some elements. Choose pivot element as middle element. we can choose first or last also.
After choosing pivot element arrange the elements like all elements which are less than pivot value comes left side and elements greater than equal to pivot come right side of pivot.
And then apply same to both sides. until it becomes one. then all elements in array will be sorted.

Program #1: Java Example program to sort elements of array using quick sort algorithm:

package quicksortjava;
public class QuickSort {
private int array[];
private int length;
public void sortElements(int[] arrayvalues) {
if (arrayvalues == null || arrayvalues.length == 0) {
return;
}
this.array = arrayvalues;
length = arrayvalues.length;
doQuickSort(0, length - 1);
}
private void doQuickSort(int lowIndex, int highIndex) {
int i = lowIndex;
int j = highIndex;
int pivot = array[lowIndex+(highIndex-lowIndex)/2];
// now Divide the array into two arrays(actually we are maintaining single array only)
while (i <= j) {
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
swapElements(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if (lowIndex < j){
doQuickSort(lowIndex, j);
}
if (i < highIndex){
doQuickSort(i, highIndex);
}
}
private void swapElements(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String a[]){
QuickSort quicksort = new QuickSort();
int[] inputarray = {32,1,23,14,43,7,6,65};
System.out.println("Before sorting");
for(int i:inputarray){
System.out.print(i);
System.out.print(" ");
}
quicksort.sortElements(inputarray);
System.out.println("After sorting");
for(int i:inputarray){
System.out.print(i);
System.out.print(" ");
}
}
}

Output:

Before sorting
32 1 23 14 43 7 6 65
After sorting
1 6 7 14 23 32 43 65

Execution flow explanation of quick sort algorithm

quick sort program in java using recursion program.png

Quicksort implementation java:

Quicksort example step by step in java

32 1 23 14 43 7 6 65
lowerIndex= 0 higherIndex=7
i=0 j=7
pivote= 14
array[j] > pivot (6 > 14 ) so decrementing j
i=0 j=6
i<=j (0 <= 6 ) so swap array[i] and array[j] (32 > 6 )
6 1 23 14 43 7 32 65 i=1 j=5
array[i] < pivot (23 < 14 ) so incrementing i
i=2 j=5
i<=j (2 <= 5 ) so swap array[i] and array[j] (23 > 7 )
6 1 7 14 43 23 32 65 i=3 j=4
array[j] > pivot (14 > 14 ) so decrementing j
i=3 j=3
i<=j (3 <= 3 ) so swap array[i] and array[j] (14 > 14 )
6 1 7 14 43 23 32 65 i=4 j=2
6 1 7 14 43 23 32 65
lowerIndex < j (0 < 2 )   call quickSort(lowerIndex, j) quickSort (0 , 2 )

6 1 7 14 43 23 32 65

lowerIndex= 0 higherIndex=2
i=0 j=2
pivote= 1
array[j] > pivot (7 > 1 ) so decrementing j
i=0 j=1
i<=j (0 <= 1 ) so swap array[i] and array[j] (6 > 1 )
1 6 7 14 43 23 32 65 i=1 j=0
1 6 7 14 43 23 32 65
i < higherIndex (1 < 2 )   call quickSort(i, higherIndex); quickSort (1 , 2 )

1 6 7 14 43 23 32 65

lowerIndex= 1 higherIndex=2
i=1 j=2
pivote= 6
array[j] > pivot (7 > 6 ) so decrementing j
i=1 j=1
i<=j (1 <= 1 ) so swap array[i] and array[j] (6 > 6 )
1 6 7 14 43 23 32 65 i=2 j=0
1 6 7 14 43 23 32 65
i < higherIndex (4 < 7 )   call quickSort(i, higherIndex); quickSort (4 , 7 )
1 6 7 14 43 23 32 65
lowerIndex= 4 higherIndex=7
i=4 j=7
pivote= 23
array[j] > pivot (65 > 23 ) so decrementing j
i=4 j=6
array[j] > pivot (65 > 23 ) so decrementing j
i=4 j=5
i<=j (4 <= 5 ) so swap array[i] and array[j] (43 > 23 )
1 6 7 14 23 43 32 65 i=5 j=4
1 6 7 14 23 43 32 65
i < higherIndex (5 < 7 )   call quickSort(i, higherIndex); quickSort (5 , 7 )

1 6 7 14 23 43 32 65

lowerIndex= 5 higherIndex=7
i=5 j=7
pivote= 32
array[j] > pivot (65 > 32 ) so decrementing j
i=5 j=6
i<=j (5 <= 6 ) so swap array[i] and array[j] (43 > 32 )
1 6 7 14 23 32 43 65 i=6 j=5
1 6 7 14 23 32 43 65
i < higherIndex (6 < 7 )   call quickSort(i, higherIndex); quickSort (6 , 7 )
1 6 7 14 23 32 43 65
lowerIndex= 6 higherIndex=7
i=6 j=7
pivote= 43
array[j] > pivot (65 > 43 ) so decrementing j
i=6 j=6
i<=j (6 <= 6 ) so swap array[i] and array[j] (43 > 43 )
1 6 7 14 23 32 43 65 i=7 j=5

1 6 7 14 23 32 43 65


	Web Artima.com