Quick Sort Algorithm :

Quick sort Algorithm :

Time Complexity : O(n*log(n))

Space Complexity : O(1)

Not a stable algorithm, Relative ordering of the elements is not guaranteed.

import java.util.*;

public class Main {
    public static void main(String[] args) {
      int[] arr = {3,7,1,2,5,6,4};

      int low = 0;
      int high = arr.length-1;

      quicksort(arr, low, high);

      for(int n : arr) {
        System.out.println(n);
      }
  }

  public static void quicksort(int[] arr, int low, int high) {

    if(low > high) {
      return ;
    }

    int partition = partitionArray(arr, low, high);

    quicksort(arr, low, partition-1);
    quicksort(arr, partition+1, high);
  }

  public static int partitionArray(int[] arr, int low, int high) {

    //This index is to tell that till here it was sorted. 
    // Why we are taking low -1 because first index in the array may be higher that 
    // the pivot
    int i = low-1;
    int pivot = arr[high];
    for(int j=low; j<high; j++) {
      if(arr[j] <= pivot) {

        i++;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }

    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;

    return i+1;
  }
}