Categories
Class 12

Quick Sort Program in Java

Quick Sort is a popular sorting algorithm that is based on divide-and-conquer strategy. It is also known as the partition exchange sort. The average case complexity of Quick Sort is O(n log n).

Following are the main steps involved in quick sort:

  1. Pick an element from the list. We call this element the pivot element.
  2. Partition the list in such a way that all elements less than pivot appear before pivot and all the elements greater than the pivot appear after the pivot.
  3. Repeat the steps with the sub-lists recursively until the entire array is sorted.
import java.io.*;
class QuickSort{
    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.print("Array size: ");
        int n = Integer.parseInt(br.readLine());
        int a[] = new int[n];
        System.out.println("Enter array elements:");
        for(int i = 0; i < a.length; i++)
            a[i] = Integer.parseInt(br.readLine());
        quickSort(a, 0, a.length - 1);
        System.out.println("Sorted elements:");
        for(int i = 0; i < a.length; i++)
            System.out.print(a[i] + "\t");
        System.out.println();
    }
    public static void quickSort(int a[], int low, int high){
        int index;
        if(high > low){
            index = split(a, low, high);
            quickSort(a, low, index - 1);
            quickSort(a, index + 1, high);
        }
    }
    public static int split(int a[], int low, int high){
        int pivot = a[low];
        int p = low + 1;
        int q = high;
        int temp;
        while(q >= p){
            while(a[p] < pivot){
                p++;
                if(q < p)
                    break;
            }
            while(a[q] > pivot){
                q--;
                if(q < p)
                    break;
            }
            if(q > p){
                temp = a[p];
                a[p] = a[q];
                a[q] = temp;
            }
        }
        temp = a[low];
        a[low] = a[q];
        a[q] = temp;
        return q;
    }
}

Leave a Reply