Blog

Given an array of element and we will use Quick Sort algorithm to sort an array. Quick Sort uses last element as pivot sort an array.

Example – Program to sort an array using Quick Sort with recursion

In this approach, function takes last element as pivot, and places the pivot element at its correct position in array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot . After that recursively sort elements before partition and after partition.

public class QuickSort {

  static int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
      // If current element is smaller than or equal to pivot
      if (arr[j] <= pivot) {
        i++;

        // swap arr[i] and arr[j]
        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;
  }

  static void quickSort(int arr[], int low, int high) {
    if (low < high) {

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

      quickSort(arr, low, pi - 1);
      quickSort(arr, pi + 1, high);
    }
  }

  public static void main(String args[]) {

    int arr[] = { 5, 6, 7, 3, 2, 1 };

    quickSort(arr, 0, arr.length - 1);

    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
  }
}

Output

1 2 3 5 6 7

Example – Another way without recursion

public class QuickSort {

  static int partition(int arr[], int low, int high) {
    int pivot = arr[high];

    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
      // If current element is smaller than or
      // equal to pivot
      if (arr[j] <= pivot) {
        i++;

        // swap arr[i] and arr[j]
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }

    // swap arr[i+1] and arr[high] (or pivot)
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;
  }

  static void quickSortWithoutRecursion(int arr[], int l, int h) {
    // Create an stack
    int[] stack = new int[h - l + 1];

    // initialize top of stack
    int top = -1;

    stack[++top] = l;
    stack[++top] = h;

    // Keep popping from stack while is not empty
    while (top >= 0) {
      // Pop h and l
      h = stack[top--];
      l = stack[top--];

      // Set pivot element at its correct position
      // in sorted array
      int p = partition(arr, l, h);

      // If there are elements on left side of pivot,
      // then push left side to stack
      if (p - 1 > l) {
        stack[++top] = l;
        stack[++top] = p - 1;
      }

      // If there are elements on right side of pivot,
      // then push right side to stack
      if (p + 1 < h) {
        stack[++top] = p + 1;
        stack[++top] = h;
      }
    }
  }

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

    quickSortWithoutRecursion(arr, 0, arr.length - 1);

    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
  }
}

Output

1 2 3 5 6 7