The Quick Sort Algorithm

The quick sort algorithm is slower than merge sort algorithm, but requires less space, since it does not copy the array being searched into a temporary array, but performs all operations on the initial array.

The hart of the quick sort is the partitioning process. The algorithm picks a place in the array (usually the last element) and considers it to be a pivot. Then it throws every value that is less than that pivot to the left, and a value greater than the pivot to the right. After that the pivot is placed in the correct position of where it belongs in the array. Then the partitioning process begins in the right part of the array, and in the left part of the array until all elements of the array are sorted.

Code in Java:

public static void main(String[] args) {
  int[] inputArray = {9,8,3,13,87,12,99};
  quickSort(inputArray, 0, inputArray.length-1);
  System.out.println(Arrays.toString(inputArray));
}
	
public static void quickSort(int[] inputArray, int start, int end) {
  if (start < end) {
    int partition = partition(inputArray, start, end); // index position 
    // of the corrected placed element
    quickSort(inputArray, start, partition - 1); // sorts the left half of the range
    quickSort(inputArray, partition + 1, end); // sorts the right half of the range
    }
  }
private static int partition(int[] inputArray, int start, int end) {
  int pivot = inputArray[end]; // pivot at the end of the array
  int i = start - 1;  // the place before the start point (-1)
  for (int j = start; j <= (end - 1); j++) {
    if (inputArray[j] <= pivot) {
      i++;
      // swapping
      int temp = inputArray[i];			
      inputArray[i] = inputArray[j];
      inputArray[j] = temp;
    }
  }
  // put the pivot value in the correct slot next
  int temp = inputArray[i + 1];
  inputArray[end] = temp;
  inputArray[i + 1] = pivot;
  return i + 1;
}