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.


• So now pivot element is exactly in middle. if we sort left and right side elements all elements will be sorted. Here recursive quick sort will take place in order to sort all elements.
• 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:

1. package quicksortjava;
2. 
   
3. public class QuickSort {
4.  
5.     private int array[];
6.     private int length;
7.  
8. public void sortElements(int[] arrayvalues) {
9.          
10.         if (arrayvalues == null || arrayvalues.length == 0) {
11.             return;
12.         }
13.         this.array = arrayvalues;
14.         length = arrayvalues.length;
15.         doQuickSort(0, length - 1);
16. }
17.  
18.   private void doQuickSort(int lowIndex, int highIndex) {
19.          
20.         int i = lowIndex;
21.         int j = highIndex;
22.         
23.         int pivot = array[lowIndex+(highIndex-lowIndex)/2];
24.         
25.         // now Divide the array into two arrays(actually we are maintaining single array only)
26.         while (i <= j) {
27.        
28.             while (array[i] < pivot) {
29.                 i++;
30.                 
31.             }
32.             while (array[j] > pivot) {
33.                 j--;
34.             }
35.             if (i <= j) {
36.                 swapElements(i, j);
37.                
38.                 //move index to next position on both sides
39.                
40.                 i++;
41.                 j--;
42.                 
43.                 
44.             }
45.         }
46.         
47.         // call quickSort() method recursively
48.         if (lowIndex < j){
49.        
50.         doQuickSort(lowIndex, j);
51.         }
52.         if (i < highIndex){
53.        
54.         doQuickSort(i, highIndex);
55.             
56.         }
57.     }
58.  
59.     
60.      
61. private void swapElements(int i, int j) {
62. 
    
63.         int temp = array[i];
64.         array[i] = array[j];
65.         array[j] = temp;
66. 
    
67.  }
68.      
69.  public static void main(String a[]){
70.          
71.     QuickSort quicksort = new QuickSort();
72.         int[] inputarray = {32,1,23,14,43,7,6,65};
73.         
74.         System.out.println("Before sorting");
75.         for(int i:inputarray){
76.             System.out.print(i);
77.             System.out.print(" ");
78.         }
79.        
80.  quicksort.sortElements(inputarray);
81. 
    
82.         System.out.println("After sorting");
83.         for(int i:inputarray){
84.             System.out.print(i);
85.             System.out.print(" ");
86.         }
87.     }
88. 
    
89. }

 Output:

2. Before sorting
3. 32 1 23 14 43 7 6 65 
4. After sorting
5. 1 6 7 14 23 32 43 65 

Execution flow explanation of quick sort algorithm