//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;
}
#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;
}