//Quicksort using singly linked list.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct LinkList
{
int data;
struct LinkList *next;
}List;
void Insert(List **Head,int value)
{
List *ptr=*Head;
List *newnode;
newnode=(List*)malloc(sizeof(List));
newnode->data=value;
newnode->next=NULL;
if(ptr==NULL)
*Head=newnode;
else
{
while(ptr->next!=NULL)
ptr=ptr->next;
ptr->next=newnode;
}
}
void Quicksort(List *Head,List *end)
{ if(Head==end)return;
int count=0,count1=0,count2=0,temp=0;
List *front=Head,*back=end,pf,bf,*ptr=Head,*pivot=Head;
while(ptr!=end)
{
count++;
ptr=ptr->next;
}
while(count>=0&&front->next!=back)
{
while(front->next&&front->next->data<pivot->data)
front=front->next;
while(count>0&&front->next!=back)
{
back=Head;
count1=--count;
while(count1)
{
back=back->next;
count1--;
}
if(back->data<pivot->data)
{
temp=front->next->data;
front->next->data=back->data;
back->data=temp;
front=front->next;
count;
break;
}
}
}
temp=front->data;
front->data=pivot->data;
pivot->data=temp;
// Display(Head);
Quicksort(Head,front);
Quicksort(front->next,end);
}
void Display(List *Head)
{
if(!Head)return ;
printf("%d ",Head->data);
Display(Head->next);
}
int main(void)
{
List *Head=NULL;
int i,value;
for(i=0;i<10;i++)
{
scanf("%d",&value);
Insert(&Head,value);
}
Display(Head);printf("\n");
Quicksort(Head,NULL);
printf("\n");
Display(Head);
return 0;
}
// Input could be like... 9 8 11 2 15 4 13 1 17 5
No comments:
Post a Comment