Saturday, August 20, 2011

QuickSort using stack

//QuickSort using stack
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct stk
{
int a[50];
int top;
};
void push(struct stk *s,int item);
int pop(struct stk *s);
struct stk l;
struct stk u;
main()
{
      int i,*a,n;
      void create(int **a,int n);
      void display(int *a,int n);
      void quicksort(int *a,int n);
      extern int quick(int *s,int left,int right);
      l.top=-1;
      u.top=-1;
      a=NULL;
      printf("Enter the number of elements you want in your array : " );
      scanf("%d",&n);
      create(&a,n);
      display(a,n);
      quicksort(a,n);
      display(a,n);
     getch();
      return 0;
}
void create(int **a,int n)
{
     int i;
     int *s;
     s=(int *)malloc(n*sizeof(int));
     printf("\n Enter the value of array elements " );
     for(i=0;i<n;i++)
     {
                  scanf("%d",&s[i]);
     }
     *a=s;
}
void display(int *a,int n)
{ int i;
      printf("\n array elements " );
     for(i=0;i<n;i++)
     {
                  printf("%d ",a[i]);
     }
}
void quicksort(int *a,int n)
{
     int b,e,loc;
     push(&l,0);
     push(&u,n-1);
     while(l.top!=-1&&u.top!=-1)
     {
         b=pop(&l);
         e=pop(&u);
       
         loc=quick(a,b,e);
         if (b<loc-1)
         {
                push(&l,b);
                push(&u,loc-1);  
         }
         if(loc+1<e)  
         {
              push(&l,loc+1);
              push(&u,e);
         }  
     }                    
}
int quick(int *s,int left,int right)
{
    int loc,temp;
    loc=left;
    while(1)
    {
            while(s[loc]<=s[right]&&loc!=right)
              {
                  right=right-1;
             
              }
            if(loc==right)
              return loc;
            if(s[loc]>s[right])
            {
               temp=s[loc];
               s[loc]=s[right];
               s[right]=temp;
            }
         
            loc=right;
            while(s[left]<=s[loc]&&loc!=left)
              left=left+1;
            if(loc==left)
              return loc;
            if(s[left]>s[loc])
            {
               temp=s[loc];
               s[loc]=s[left];
               s[left]=temp;
            }
            loc=left;
    }   
}
void push(struct stk *s,int item)
{
 int c;
  s->a[++(s->top)]=item;
}
int pop(struct stk *s)
{
    int i;
    i=s->a[(s->top)--];
    return i;
}

Previous Next Home
0 Comments
Comments

Leave a Comment

:)) ;)) ;;) :D ;) :p :(( :) :( :X =(( :-o :-/ :-* :| 8-} :)] ~x( :-t b-( :-L x( =))

Twitter Delicious Facebook Favorites More