Quick Sort

QuickSort is based on divide-and-conquer approach. QuickSort is inplace 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 subaaray 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.

One Thought on “Quick Sort

  1. Pingback: Two Elements Whose Sum is Closest to Zero - Programming Questions

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation