CS201: Elementary Data Structures

QuickSort is based on divide-and-conquer approach. QuickSort is an in-place sorting algorithm. A sorting algorithm is said to be in-place if it requires very little additional space besides the initial array holding the elements that are to be sorted.

The key to the Algorithm is the Partition Procedure, which rearranges the subarray a[p..r] in place. Partition selects an element x as a pivot element around which to partition the subarray a[p..r].

#include <iostream>
using namespace std;
 
void swap(int *a,int *b)
{
    int temp = *a;
    *a=*b;
    *b = temp;
}
int partition (int A[], int p, int r)
{
    int x = A[r];
    int i = p - 1;
 
    for (int j = p; j <= r- 1; j++)
    {
        if (A[j] <= x)
        {
            i++;
            swap (&A[i], &A[j]);
        }
    }
    swap (&A[i + 1], &A[r]);
    return (i + 1);
}
 
void quickSort(int A[], int p, int r)
{
    if (p < r)
    {
        int q = partition(A, p,r);
        quickSort(A, p, q - 1);
        quickSort(A, q + 1, r);
    }
}
int main()
{
    int a[] = {2,6,5,1,3,4};
    int n = sizeof(a)/sizeof(a[0]);
    quickSort(a,0,n-1);
    for(int i=0;i<n;i++)
    cout<<a[i]<<" ";
    return 0;
}

Time Complexity : Average case O(nlogn) When the array is balanced partitoned.Worst case O(n^2), worst-case behavior for quicksort occurs when the partition method produces one subproblem with n-1 elements and one with 0 elements.

Source: Crazy for Code, http://www.crazyforcode.com/quicksort/
 This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 2.5 India License.