Quick Sort in Java

Quick sort is an efficient, general-purpose, comparison-based sorting algorithm. It works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Here is an example of how you might implement quick sort in Java:

class QuickSort {

  public static void sort(int[] array) {

    sort(array, 0, array.length - 1);

  }

  private static void sort(int[] array, int low, int high) {

    if (low < high) {

      int pivotIndex = partition(array, low, high);

      sort(array, low, pivotIndex - 1);

      sort(array, pivotIndex + 1, high);

    }

  }

  private static int partition(int[] array, int low, int high) {

    int pivot = array[high];

    int i = low - 1;

    for (int j = low; j < high; j++) {

      if (array[j] < pivot) {

        i++;

        swap(array, i, j);

      }

    }

    swap(array, i + 1, high);

    return i + 1;

  }

  private static void swap(int[] array, int i, int j) {

    int temp = array[i];

    array[i] = array[j];

    array[j] = temp;

  }

}

You can then use the sort method to sort an array as follows:

int[] array = {4, 3, 2, 1};

QuickSort.sort(array);

System.out.println(Arrays.toString(array)); // Outputs [1, 2, 3, 4]