Algorithms / Arrays / Quick Sort

quicksort.java

package org.joeltong.test;

import java.util.Arrays;

public class QuickSort {


  private static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length-1);
  }


  private static void quickSort(int[] arr, int l, int r) {
    if (l >= r) {
      return;
    }
    int i = partition(arr, l, r);
    quickSort(arr, l, i - 1);
    quickSort(arr, i + 1, r);
  }


  private static int partition(int[] arr, int l, int r) {

    // Pivot
    int p = arr[r];

    // Index of elements lesser than pivot
    int i = l - 1;

    for (int j = l; j < r; j++) {
      if (arr[j] < p) {
        i++;
        swap(arr, i, j);
      }
    }

    swap(arr, i + 1, r);
    return i + 1;
  }


  private static void swap(int[] arr, int i, int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
  }


  public static void main(String[] args) {
    int[] arr = {34,2,34,34,7,5,4,2,6,8,5,443,22,5,7,8,75,10};
    quickSort(arr);
    System.out.println(Arrays.toString(arr));
  }

}