Quick Sort Program in Java. Quick sort is a highly efficient sorting algorithm that follows the divide and conquer approach. It is widely favored for its performance in sorting large data sets, thanks to its impressive average and worst-case time complexity of O(n logn) and O(n^2) respectively. In this article, we will write a Java program to perform sorting by using a quick sort algorithm.
Table of Contents
How Quick Sort Works
Quick sort works by selecting a pivot element from the array and partitioning the other element into two sub-arrays, According to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This process continues until the best case of an array with 0 or 1 element is reached, at which point the array is considered sorted.
Quick Sort Program in Java
public class quicksort {
public 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++;
int temp = array[i];
array[i]=array[j];
array[j]=temp;
}
}
int temp = array[i+1];
array[i+1]=array[high];
array[high]=temp;
return i + 1;
}
public static void quickSort(int array[], int low, int high)
{
if (low < high)
{
int partitionIndex = partition(array, low, high);
quickSort(array, low, partitionIndex - 1);
quickSort(array, partitionIndex + 1, high);
}
}
public static void main(String[] args) {
int array[] = {6, 7, 8, 4, 2, 67, 23, 56};
int n = array.length;
System.out.println("Array before sorting");
for (int i = 0; i < n; i++)
{
System.out.print(array[i]+" ");
}
quickSort(array, 0, n - 1);
System.out.println("\nArray After sorting");
for (int i = 0; i < n; i++)
{
System.out.print(array[i]+" ");
}
}
}
Output
Happy Coding & Learning
4 thoughts on “Quick Sort Program in Java”