QuickSort Algorithm in Java

Java program to implement Quick Sort Algorithm

Quicksort is one of the fastest sorting algorithm.

It was developed by Hoare in 1960.

Quicksort is a divide and conquer algorithm. Quicksort divides the original array into two parts and recursively sorts them.

The basic steps for quicksort are:

1. Quicksort chooses a value. This value is called pivot. There are different quicksort versions that choose pivot in different ways: to choose the first element form the array as pivot, to choose the last element from the array, to choose a random element or to choose median as pivot.

2. Swap elements from both ends of the array. All elements smaller than the pivot are placed to the left and all elements greater than the pivot are placed to the right.

3. Recursively sort both parts by applying Quicksort algorithm.

Java code for quick sort choosing middle element as pivot:

//QuickSort in Java
import java.util.Arrays;

public class QuicksortJava {

    public static void main(String[] args) {
         int [] array = {3,6,5,-1,4,0};
         System.out.println("Before sorting: " + Arrays.toString(array));
         quickSort(array,0,array.length-1);
         System.out.println("After sorting: " + Arrays.toString(array));                                          
    }

    public static void quickSort(int[] A, int low, int high) {
        //select the pivot
        int middle = low + (high - low) / 2;
        int pivot = A[middle];
       
        int i = low;  // i for positions from low to high
        int j = high; // j for positions from high to low
        int temp;    

        while (i < j) {
            while (A[i] < pivot) {
                i++;
            }
            while (A[j] > pivot) {                                                                                
                j--;        
            }
            if (i <= j) {                                             
                temp = A[i];                 
                A[i] = A[j];
                A[j] = temp;
                i++;
                j--;
            }
        }
       
        //recursion
        if (low < j) {
            quickSort(A, low, j);
        }
        if (i < high) {
            quickSort(A, i, high);
        }
    }

}//quicksort Java

Output:

Before sorting : [3, 6, 5, -1, 4, 0]

After sorting : [-1, 0, 3, 4, 5, 6]