Click here to hide categories Click here to show left categories

User: Home          welcome : Guest          Log In / Register here     




QUICK SORT algorithm implementation in C++

Download Attachment
/*******************************/
/*PROGRAM TO PREFORM QUICK SORT*/
/*******************************/

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

#define SIZE 50
int quick_sort(int [],int,int);

void main()
{
    int a[SIZE],top=-1,lower[SIZE],upper[SIZE],beg,end,n,loc,i;

    clrscr();

    printf("Enter the size of array: ");
    scanf("%d",&n);
    printf("\nEnter the elements of array:\n");
    for(i=0;i    {
        scanf("%d",&a[i]);
    }
    if(n>1)
    {
        top=top+1;
        lower[0]=0;
        upper[0]=n-1;
    }
    else
    {
        printf("\nNo need of sorting as there is only one element");
        getch();
        exit(1);
    }
    while(top!=-1)
    {
        beg=lower[top];
        end=upper[top];
        top=top-1;
        loc=quick_sort(a,beg,end);
        if(beg        {
            top=top+1;
            lower[top]=beg;
            upper[top]=loc-1;
        }
        if(loc+1        {
            top=top+1;
            lower[top]=loc+1;
            upper[top]=end;
        }
    }
    printf("\nAfter sorting the elements of array are:\n");
    for(i=0;i    {
        printf("%d ",a[i]);
    }
    getch();
}

int quick_sort(int a[],int beg,int end)
{
    int left,right,loc,temp;
    left=beg;
    right=end;
    loc=beg;

    again:
    while((a[loc]<=a[right])&&(loc!=right))
    {
        right=right-1;
    }
    if(loc==right)
    {
        return(loc);
    }
    if(a[loc]>a[right])
    {
        temp=a[loc];
        a[loc]=a[right];
        a[right]=temp;
        loc=right;
    }

    while((a[left]<=a[loc])&&(left!=loc))
    {
        left=left+1;
    }
    if(loc==left)
    {
        return(loc);
    }
    if(a[left]>a[loc])
    {
        temp=a[loc];
        a[loc]=a[left];
        a[left]=temp;
        loc=left;
    }
    goto again;
}

 

Share this article   |    Print    |    Article read by 2691 times
Author:
Rohit kakria
I am software developer
Related Articles:
Related Interview Questions: No related interview question