Quicksort in Java

Quicksort in Java

Quicksort  

In our earlier tutorials we have seen about Bubble sort and Insertion sort. In this tutorial we will see about one of the best divide and conquer algorithm called Quicksort. In divide and conquer sorting algorithm the original elements will be separated into two parts (divided) and then individually sorted (conquered) and then combined. Need to remember that Quciksort can be implemented in same array and no need of additional array required.

• If array contains only one element or zero element then the array is in sorted order already. 
• If array contains more than 1 element then we need to select middle element as pivot element.
• Next we need to place all smaller elements than pivot element on left side and all larger elements are placed at right side of the array. 
• Sort both the arrays recursively by applying Quicksort algorithm.
• Finally combine both the sorted arrays. 

Now lets see simple java code to sort integer array using Quicksort algorithm.

public class QuickSort {

 public static void main(String[] args) {
  
  int array[] = { 6, 3, 9, 2, 5, 7, 8, 1, 4 };
  
  System.out.print("Array before sorting : ");
  printArray(array);
  
  quickSort(array, 0, array.length - 1);
  
  System.out.print("Array after sorting : ");
  printArray(array);
 }

 public static void quickSort(int array[], int lower, int length) {

  if (lower >= length)
   return;
  int first = lower, last = length;
  int piv = array[(first + last) / 2]; // Picking pivot element

  while (first < last) {
   // Searching for smaller element than pivot element
   while (first < last && array[first] < piv)
    first++;

   // Searching for greater element than pivot element
   while (first < last && array[last] > piv)
    last--;
   if (first < last) {
    int tmp = array[first];
    array[first] = array[last];
    array[last] = tmp;
   }
  }
  if (last < first) {
   int tmp = first;
   first = last;
   last = tmp;
  }
  // Calling recursive
  quickSort(array, lower, first);
  quickSort(array, first == lower ? first + 1 : first, length);
 }

 public static void printArray(int[] array) {
  for (int i : array) {
   System.out.print(i + ", ");
  }
  System.out.println();
 }
}

OUTPUT:

Array before sorting : 6, 3, 9, 2, 5, 7, 8, 1, 4, 
Array after sorting : 1, 2, 3, 4, 5, 6, 7, 8, 9,