Friday, August 16, 2013

Quicksort using singly linked list

//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