Description

-> Based on divide and conquer strategy.
-> This is in-place sorting algorithm.

Steps for Quick Sort
1) Select any element from array as pivot.
2) Rearrange array element in such a way that all elements lesser than pivot should be 
present in left side and all elements greater than pivot should be right side. 
Elements equal to pivot can be placed in any side. This rearrangement will put 
pivot element to its final position.
3) Recursively sort the two sub-arrays thus obtained.

Time Complexity
	Average case - O(nlogn)
	Worst case - O(n2)

C/C++

/* C program of Quick sort */
//Save it as QuickSort.c

#include<stdio.h>
int main(){

    int i,n;

    printf("Enter the size of array : ");
    scanf("%d",&n);

    int arr[n];

    printf("\nEnter element : ");
    for(i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }

    quickSort(arr,0,n);


    //Finally printing the sorted array
    printf("\nThe Sorted array is : ");
    for(i=0;i<n;i++){
        printf("%d ",arr[i]);
    }

    return 0;
}

void quickSort(int arr[],int start, int end){

    if(start<end){
        int partitionIndex=partitionArray(arr,start,end);
        quickSort(arr,start,partitionIndex-1);
        quickSort(arr,partitionIndex+1,end);
    }
}

int partitionArray(int arr[], int start, int end){

    int i;
    int pivot = arr[end];
    int partitionIndex = start;

    for(i=start;i<end;i++){
        if(arr[i]<=pivot){
            swapElement(&arr[i],&arr[partitionIndex]);
            partitionIndex++;
        }
    }

    swapElement(&arr[partitionIndex],&arr[end]);
    return partitionIndex;
}

void swapElement(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

Input:
Enter the size of array : 
5
Enter element : 
34
19
64
57
24

Output:
The Sorted array is : 
19 24 34 57 64

Java

/* Java program of Quick sort */
//Save it as QuickSort.java

import java.io.*;
import java.util.Scanner;

class QuickSort {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int i, n;

        System.out.println("Enter the size of array : ");
        n = scanner.nextInt();

        int arr[] = new int[n];

        System.out.println("Enter element : ");
        for (i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        quickSort(arr, 0, n - 1);

        // Finally printing the sorted array
        System.out.println("The Sorted array is : ");
        for (i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    private static void quickSort(int arr[], int start, int end) {
        if (start < end) {
            int partitionIndex = partitionArray(arr, start, end);
            quickSort(arr, start, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, end);
        }
    }

    static int partitionArray(int[] arr, int start, int end) {

        int pivot = arr[end];
        int i = (start - 1);

        for (int j = start; j <= end - 1; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, end);
        return (i + 1);
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Input:
Enter the size of array : 
5
Enter element : 
34
19
64
57
24

Output:
The Sorted array is : 
19 24 34 57 64

Related programs