Randomized Quick Sort

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

int n;

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

int partition(int a[],int i,int j)
{
    int l=i;
    while(i<j)
    {
        while(a[i]<=a[l])
            i++;
        while(a[j]>a[l])
            j--;
        if(i<j)
            swap(a,i,j);
    }
    swap(a,l,j);
    return j;
}

void RQS(int a[],int i,int j)
{
    int p;
    if(i<j)
    {
        if((j-1)>5)
            swap(a,random(n)%(j-i+1)+i,i);
        p=partition(a,i,j);
        RQS(a,i,p-1);
        RQS(a,p+1,j);
    }
}

void main()
{
    int a[100],i;
    clrscr();
    printf("Enter number of elements ");
    scanf("%d",&n);
    printf("Enter elements ");
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    RQS(a,0,n-1);
    printf("Sorted array is ");
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
    getch();
}

/*Output
Enter number of elements 5
Enter elements 5 4 3 2 1
Sorted array is 1 2 3 4 5
*/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s