what's problem with this kind of sorting ??

This is a discussion on what's problem with this kind of sorting ?? within the C Programming forums, part of the General Programming Boards category; I was trying to sort a linked list by a method described below - original- 5 98 45 32 65 ...

  1. #1
    Team Bring It rajarshi's Avatar
    Join Date
    Nov 2011
    Location
    India
    Posts
    79

    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");
    }
    Last edited by rajarshi; 11-23-2011 at 08:35 AM.

    " I failed in some subjects in exam , but my friend passed in all . Now he is an engineer in Microsoft and I am the owner of Microsoft !! "

    - Bill Gates .

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  3. #3
    Team Bring It rajarshi's Avatar
    Join Date
    Nov 2011
    Location
    India
    Posts
    79
    Quote Originally Posted by Adak View Post
    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 :\

    " I failed in some subjects in exam , but my friend passed in all . Now he is an engineer in Microsoft and I am the owner of Microsoft !! "

    - Bill Gates .

  4. #4
    Registered User
    Join Date
    Nov 2011
    Posts
    26
    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:

    Code:
    void swap(Node *previous, Node *first)
    {
         previous->next = first->next;
         first->next = previous->next->next;
         previous->next->next = first;
    }
    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.

  5. #5
    Team Bring It rajarshi's Avatar
    Join Date
    Nov 2011
    Location
    India
    Posts
    79
    Quote Originally Posted by dan_paul View Post
    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 ??

    " I failed in some subjects in exam , but my friend passed in all . Now he is an engineer in Microsoft and I am the owner of Microsoft !! "

    - Bill Gates .

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.
    Last edited by Adak; 11-23-2011 at 09:27 AM.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,296
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Kind of a little problem (HW)
    By PureMotive in forum C Programming
    Replies: 2
    Last Post: 02-16-2011, 01:28 PM
  2. kind of problem bothering me ( pow or * ? )
    By nick2 in forum C Programming
    Replies: 10
    Last Post: 06-27-2009, 11:33 PM
  3. Problem with sorting
    By preeengles in forum C Programming
    Replies: 35
    Last Post: 04-22-2009, 07:45 PM
  4. Kind of logic problem,could use some help :)
    By yrostran in forum C Programming
    Replies: 11
    Last Post: 09-11-2006, 06:48 PM
  5. some kind of problem with .find
    By Rubiks14 in forum C++ Programming
    Replies: 7
    Last Post: 12-05-2005, 09:27 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21