Thread: what's problem with this kind of sorting ??

I was trying to sort a linked list by a method described below -

original-
5 98 45 32 65
[ITERATION 1]
round 1
5 greater than 98 ? no. don't interchange.
98 greater than 45 ? yes. interchange.

now-
5 45 98 32 65

round 2
45 greater than 98 ? no. don't interchange.
98 greater than 32 ? yes. interchange.

now-
5 45 32 98 65

round 3
32 greater than 98 ? no. don't interchange.
98 greater than 65 ? yes. interchange.

now-
5 45 32 65 98

So, after ITERATION 1...the greatest number moves to the end of the list...
so, after ITERATION 4..the linked list will be sorted as
5 32 45 65 98


So, after each ITERATION the greatest number moves towards the right and the smallest numbers move towards the left...and a time comes when the list is totally sorted....
I wrote this code...but it isn't working....

wut could be the possible error ??

Code:

#include <stdio.h>
#include <stdlib.h>
struct node
{  int data;
   struct node *link;
    
};


struct node *insert(struct node *p,int n)
{


    if (p==NULL)
    {
        p=(struct node *)malloc(sizeof(struct node));


        p->data=n;
        p->link=NULL;
        
    }   else 
        p->link =insert(p->link,n);
        return(p);
} 






struct node *sort(struct node *p)
{   struct node *curr;
    curr=p;
    int count=0;
    while (curr!=NULL)
    {
        count++;
        curr=curr->link;
        
    }
    int i;
    struct node *one,*two,*three;
    one=p;
    two=p->link;
    three=p->link->link;
    for (i=0;i<=count-1;i++)
    {
        for (i=0;i<count-3;i++)
        {
            if (one->data > two->data)
            {
                one->link=three;
                two->link=one;
            }


            
            if (two->data > three->data)
            {
                two->link=three->link;
                three->link=two;
                one->link=three;                
            }
            
            one=two;
            two=three;
            three=three->link;
        }
            one=p;
            two=p->link;
            three=p->link->link;
        
    }
            return (p);
}


void printlist (struct node *p)
{
    printf ("The data values in the list are \n");
    while (p!=NULL)
    {
        printf ("%d \t",p->data);
        p=p->link;
    }
}




int main ()
{
    int n,i;
    int x;int z;
    struct node *start =NULL;
    while (1)
{
    printf ("Enter the number of nodes to be created at the end of the list : \n");
    scanf ("%d",&n);
    for (i=0;i<n;i++)
    {
        printf ("Enter the data values to be placed in a node at the end of the list \n");
        scanf ("%d",&x);
        start=insert (start,x);
        
    }
   printf  ("The list is created !! \n");
   printlist (start);    
   printf ("\n");
   
   if (n==0)
   break;
   
       
}




    printf ("SORTED DATA : \n");
    start=sort(start);
    printlist (start);
    printf ("\n");
}

Originally Posted by Adak

It's a bubble sort type of algorithm, but you're cutting the passes off before they reach the end of the set of numbers, repeatedly.

sorry,couldn't get u :\

Originally Posted by dan_paul

I'm a beginner myself so not sure how much help this is but thought your code might be easier if you separate the swap function into a separate function. I haven't tested this but hopefully it illustrates the idea. You pass the node prior to the nodes to be swapped and the first node to be swapped:



After that you can repeatedly go through your list keeping track of when you call the swap function and exit the loop if swap isn't called.

ya..can build a seperate swap function..
but wut is wrong in my program ??

Code:

void bubbleSort(int A[]) {   
  int i, n, swapped,temp;
  n = MAX-1;           //MAX is a define value the size of the Array A[]
  do {
    swapped = 0;
    for(i =0; i < n; i++) {  
      if(A[i] > A[i + 1 ]) {
        swap(A, i, i + 1); //call swap function
        //or
/*     temp = A[i];
        A[i] = A[i+1];
        A[i+1]=temp;
*/
        swapped = 1;
      }
    } //end for
    --n;
  }while(swapped);
}

You're rounds are cutting short, instead of going to <n, you stop early.

If you give A[] the same values, you can have it print up after each round, and compare the values with what you have mentioned in your first post.

Whilst Bubble Sort is very easy to write for an array, it is very very hard to get right for a linked-list.
I strongly recommend writing Insertion Sort instead. It's very easy, in fact it's the shortest linked-list sorting algorithm there is.