Example: Java Program to Implement Quick Sort Algorithm
// Quick sort in Java
import java.util.Arrays;
class Main {
// divide the array on the basis of pivot
int partition(int array[], int low, int high) {
// select last element as pivot
int pivot = array[high];
// initialize the second pointer
int i = (low - 1);
// Put the elements smaller than pivot on the left and
// greater than pivot on the right of pivot
for (int j = low; j < high; j++) {
// compare all elements with pivot
// swap the element greater than pivot
// with element smaller than pivot
// to sort in descending order
// if (array[j] >= pivot)
if (array[j] <= pivot) {
// increase the second pointer if
// smaller element is swapped with greater
i++;
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
// put pivot in position
// so that element on left are smaller
// element on right are greater than pivot
int temp = array[i + 1];
array[i + 1] = array[high];
array[high] = temp;
return (i + 1);
}
void quickSort(int array[], int low, int high) {
if (low < high) {
// Select pivot position and put all the elements smaller
// than pivot on the left and greater than pivot on right
int pi = partition(array, low, high);
// sort the elements on the left of the pivot
quickSort(array, low, pi - 1);
// sort the elements on the right of pivot
quickSort(array, pi + 1, high);
}
}
// Driver code
public static void main(String args[]) {
// create an unsorted array
int[] data = { 8, 7, 2, 1, 0, 9, 6 };
int size = data.length;
// create an object of the Main class
Main qs = new Main();
// pass the array with the first and last index
qs.quickSort(data, 0, size - 1);
System.out.println("Sorted Array: ");
System.out.println(Arrays.toString(data));
}
}
Output 1
Unsorted Array: [8, 7, 2, 1, 0, 9, 6] Sorted Array: [0, 1, 2, 6, 7, 8, 9]
Here, the elements of the array are sorted in ascending order. If we want to sort the elements in descending order, then inside the for loop of the partition()
method, we can change the code as:
// the less than sign is changed to greater than
if (array[j] >= pivot) {
If you want to learn more about the quick sort algorithm, visit Quick Sort Algorithm.