Solved

Sorting Linked Lists

Posted on 1998-04-27
42
314 Views
Last Modified: 2010-04-15
Has somebody got some code that I can use to sort a linked list.  Nothing special required, just something fairly simple that can save me a bit of time as it is urgent!
0
Comment
Question by:Shaley
  • 17
  • 7
  • 7
  • +4
42 Comments
 
LVL 4

Expert Comment

by:sganta
Comment Utility
Hi Shaley !
   I am giving a sample to code to sort the linked list.
                 With Regars - sganta (Sarat Kumar Ganta)

#include <stdio.h>

struct list {
                      int  num;
                      struct list *link;
               };
typedef list pointer;
void sort(pointer *linked_list);
void swap(pointer *first,pointer *second);
void main()
{
   pointer *linked_list;
  /* Create a linked list here */
  sort(linked_list);
}
void sort(pointer *linked_list)
{
   pointer *first,*ptr;*temp;
   first = linked_list;
   ptr = first;
   while (first->link != null)
   {
       second = first->link;
       while (second->link != null)
       {
            if (first->num > second-> num)
                 swap(first,second);    
            second = second->link;
       }
       first = first->link;
  }
}

void swap(pointer *first, pointer *second)
{
   pointer *temp;
   /* Swap the addresses */
   temp = second;
   second = first;
   first = temp;
 }
0
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
That won't work ..

For a start the swap function won't actually change anything, because the first and second are value parameters and so exchanging them does nothing.

Check out the C Snippets site .. they would have this sort (sic) of code.

0
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
C Snippets has source code for

  Ll_Msort.C   Linked list mergesort
  Ll_Qsort.C   Linked list quicksort

Please reject previous and accept this and I'll give you the address to download as an answer
0
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
Or I can post the code here if you prefer

0
 

Author Comment

by:Shaley
Comment Utility
Ronslow, if you wouldn't mind giving me the address for those downloads I'd be grateful.  I will also need to do the normal stuff such as deleting from front, rear and elsewhere in the list but I thought those would be relatively easy to do (I'm a C novice at the moment as you can probably tell!!).  Are there examples of these at the C Snippets site or do you want me to submit another question?

Thanks
Shaley  
0
 
LVL 3

Expert Comment

by:q2guo
Comment Utility
GO to http://www.strangecreations.com/library/snippets/index.htm
and look under "Auke Reitsma's comprehensive linked list functions".  If you have further questions please post a comment here.
0
 
LVL 11

Expert Comment

by:alexo
Comment Utility
Although I think that RONSLOW deserves the points, I oppose "blackmailing".  Information shall be freely shared.
Therefore:
  http://www.brokersys.com/snippets/LL_MSORT.C
  http://www.brokersys.com/snippets/LL_QSORT.C
0
 
LVL 11

Expert Comment

by:alexo
Comment Utility
Hillarious!
0
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
I didn't have the information on the web site available at the time (I had to go and look it up).

And I have been burnt several times lately by providing information and not getting the thanks (or points) for it.

here is the source:


0
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
BTW: I would have gone to http://www.snippets.org

/* +++Date last modified: 05-Jul-1997 */

#include    <stdlib.h>
#include    "snipsort.h"


/*
    This is a quicksort routine to be used to sort linked-lists
    by Jon Guthrie.
*/

void    *sortl(void *list, void *(*getnext)(void *),
            void (*setnext)(void *, void *),
            int (*compare)(void *, void *))
{
void    *low_list, *high_list, *current, *pivot, *temp;
int     result;

    /*
        Test for empty list.
    */
    if(NULL == list)
        return(NULL);

    /*
        Find the first element that doesn't have the same value as the first
        element.
    */
    current = list;
    do
    {
        current = getnext(current);
        if(NULL == current)
            return(list);
    }   while(0 == (result = compare(list, current)));

    /*
        My pivot value is the lower of the two.  This insures that the sort
        will always terminate by guaranteeing that there will be at least one
        member of both of the sublists.
    */
    if(result > 0)
        pivot = current;
    else
        pivot = list;

    /* Initialize the sublist pointers */
    low_list = high_list = NULL;

    /*
        Now, separate the items into the two sublists
    */
    current = list;
    while(NULL != current)
    {
        temp = getnext(current);
        if(compare(pivot, current) < 0)
        {
            /* add one to the high list */
            setnext(current, high_list);
            high_list = current;
        }
        else
        {
            /* add one to the low list */
            setnext(current, low_list);
            low_list = current;
        }
        current = temp;
    }

    /*
        And, recursively call the sort for each of the two sublists.
    */
    low_list  = sortl(low_list, getnext, setnext, compare);
    high_list = sortl(high_list, getnext, setnext, compare);

    /*
        Now, I have to put the "high" list after the end of the "low" list.  
        To do that, I first have to find the end of the "low" list...
    */
    current = temp = low_list;
    while(1)
    {
        current = getnext(current);
        if(NULL == current)
            break;
        temp = current;
    }

    /*
        Then, I put the "high" list at the end of the low list
    */
    setnext(temp, high_list);
    return(low_list);
}

0
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
Here is an alternative:

/* +++Date last modified: 05-Jul-1997 */

/*
** Here's an example of how to sort a singly-linked list.  I think it
** can be modified to sort a doubly-linked list, but it would get a bit
** more complicated.  Note that this is a recursive method, but the
** recursion depth is limited to be proportional to the base 2 log of
** the length of the list, so it won't "run away" and blow the stack.
**
**  10/21/93 rdg  Fixed bug -- function was okay, but called incorrectly.
*/

#include "snipsort.h"

/* linked list sort -- public domain by Ray Gardner  5/90 */

#include <stdio.h>              /* for NULL definition */
#include <string.h>


/* returns < 0 if *p sorts lower than *q */
int keycmp (list *p, list *q)
{
      return strcmp(p->key, q->key);
}

/* merge 2 lists under dummy head item */
list *lmerge (list *p, list *q)
{
      list *r, head;

      for ( r = &head; p && q; )
      {
            if ( keycmp(p, q) < 0 )
            {
                  r = r->next = p;
                  p = p->next;
            }
            else
            {
                  r = r->next = q;
                  q = q->next;
            }
      }
      r->next = (p ? p : q);
      return head.next;
}

/* split list into 2 parts, sort each recursively, merge */
list *lsort (list *p)
{
      list *q, *r;

      if ( p )
      {
            q = p;
            for ( r = q->next; r && (r = r->next) != NULL; r = r->next )
                  q = q->next;
            r = q->next;
            q->next = NULL;
            if ( r )
                  p = lmerge(lsort(r), lsort(p));
      }
      return p;
}

#if 0            /* Not really main(), but a fill-in-the-blanks framework      */

#ifdef __WATCOMC__
 #pragma off (unreferenced)
#endif

main (void)
{
      list *listp;                 /* pointer to start of list */

      /* first build unsorted list, then */

      listp = lsort(listp);                                 /* rdg 10/93 */

      return 0;
}

#endif

0
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
BTW: Thanks for taking my answer q2guo before I could propose it !! :-(  Maybe I can do the same for you one day ??



0
 
LVL 3

Expert Comment

by:q2guo
Comment Utility
Ronslow: I don't usually take other people's answer, but I want to let people who write things like

"      Please reject previous and accept this and I'll give you the address to download as an answer "

to learn a lesson.
0
 
LVL 4

Expert Comment

by:sganta
Comment Utility
Hi Shaley !
     Try it out this algorithm. This will work. If not come back to me.
      Why EXPERTS are for ? ....
------------------ Regards SGANTA

      #include <stdio.h>

      struct list {
                            int  num;
                            struct list *link;
                     };
      typedef list pointer;
      void sort(pointer *linked_list);
      void swap(pointer *first,pointer *second);
      void main()
      {
         pointer *linked_list;
        /* Create a linked list here */
        sort(linked_list);
      }
      void sort(pointer *linked_list)
      {
         pointer *first,*ptr;*temp,*first_prev,*second_prev;
         first = linked_list;
         first_prev = first;
         while (first->link != null)
         {
             second_prev = first;
             second = first->link;
             while (second->link != null)
             {
                  if (first->num > second-> num)
                       swap(first,first_prev,second,second_prev);    
                  second_prev = second;
                  second = second->link;
             }
             first_prev = first;
             first = first->link;
        }
      }

  void swap(pointer *first, pointer *first_prev,pointer *second,pointer *second_prev)
  {
         pointer *temp,*swp1,*swp2;
         /* Swap the addresses */
         swp1 = first;
         swp2 = second;
         if (first_prev == first)
         {
             if (second->link == NULL)
             {
                  second_prev->link = NULL;
                  second->link = first->link;
                  first->link = null;
                  second_prev->link = first;
                  first = second;
                  return;
               }
               second_prev->link = second->link;
               first_prev = first->link;
               second->link = first_prev;
               first_prev = second;
               first->link = second;
               second_prev->link = first;
               first = first_prev;
               return;
           }
            first_prev->link = first->link;
           
           if (second->link == NULL)
           {
                 second_prev->link = first;
                 first->link = NULL;
                 second->link = first_prev->link;
                 first_prev->link = second;
                 first = second;
                 return;
             }

              second_prev->link = second->link;
              second->link = first_prev->link
              first_prev->link = second;
              first->link = second_prev->link;
              second_prev->link = first;
              return;
}






0
 
LVL 11

Expert Comment

by:alexo
Comment Utility
Bubble sort???  Bleachhhh... Cough... Barf... Gasp... Choke...
0
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
q2guo: Don't try to teach me lessons !!

I have had too many cases lately of someone putting up a wrong answer, then me (and other experts) have put effort into providing extra info as coments and the points still being given to the first incorrect post.

I see nothing wrong with reminding the poster that they should reject a proposed answer so that another expert can post one.

Do you ??

BTW: Shaley .. if you wish to award me any points for suggesting the Snippets site, you'll need to reject the currently proposed answer.

0
 
LVL 3

Expert Comment

by:q2guo
Comment Utility
RONSLOW: I didn't say in my comment that I was teaching you a lesson.  But if you think I were, there is nothing I can do about it.
0
 

Expert Comment

by:bhattu
Comment Utility
Looking at the amount of *war* going on at expert-exchange, here's a comment for the maintainers of EE, they should allow anyone to propose any number of answers and comments, and the person who has asked the question can decide on which answer to accept. Linda are u listening?
0
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
q2guo: You said... (my caps)

RONSLOW: I don't usually take other people's answer, but I WANT TO let people who write things like "Please reject previous and accept this and I'll give you the address to download as an answer" to LEARN A LESSON.

That sounds like you were talking to me !!!  Perhaps I misunderstood what that meant.  Perhaps you could explain it to me?

0
 
LVL 11

Expert Comment

by:alexo
Comment Utility
Is it just me or did the thread got screwed up?  I see my comment as q2quo's answer.  Weird...
0
 
LVL 16

Expert Comment

by:imladris
Comment Utility
There appears to be a bug at work here. It is referenced in:

"Notice: Changes and Problems" in the Experts-Exchange customer service area Question #10051427.

0
Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

 
LVL 11

Expert Comment

by:alexo
Comment Utility
We are man of software; bugs do not become us :-)
0
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
Shaley hasn't responded here yet ... what's happeneing.

Will my 100 points end up 'stolen' ???

0
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
alexo .. bugs do not become us .. but do we become bugs? :-)

0
 
LVL 11

Expert Comment

by:alexo
Comment Utility
Touche!
(I was paraphrasing Wesley from "the princess bride")
0
 

Author Comment

by:Shaley
Comment Utility
Shaley hasn't responded and that's because I have had 2 weeks off in Barbados sunning myself and drinking rum - and what a brilliant time I had.

I am surprised, confused and somewhat concerned about all the crap going on around this simple request.  May I suggest that you all "chill out" a little and I recommend 2 weeks in Barbados in order to do that.  In the mean time, as I have used bits and pieces of the information given I'm not sure who to award the points to - any comments?


0
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
Lucky you .. I'll gladly take the two weeks in Barbados .. are you paying? :-)

Don't be concerned by the crap .. the smell will go away eventually, and it is all environmentally friendly :-)

Unfortunately (or not), we experts are only human .. and one does sometimes get a little 'noise' in these discussions .. ranging from humourous exchanges to minor flame wars.  Especially when a question has been open for a while.  We get lonely in here, y'know :-)


If you want to award points to more than one expert then there are a couple of things that can be done.

The easiest (but expensive for you and probably not recommended) is to accept one ansewr here and use up more of your own points to post another question that the other worthy expert(s) can answer to award them points.

Better for you is to send a message to Linda@experts-exchange.com and/or post a message in the Customer Service EE topics area asking for help in awarding points to multiple users for this question.  If you have not already graded an answer, Linda may give you some free points so you can award other expert(s) (similar to the previous example .. but costing you nothing).  Alternatively, especially if you have already accepted an anser, she may post a question herself on your behalf and award them points of her own.

This situation seems to be occuring more frequently.  I'm pretty sure the ability for a customer to split points is on the EE programmers todo list.  As it is now, this involves some work for Linda .. I'm sure she'd love to see this feature added so she could get on with other things :-)

0
 

Author Comment

by:Shaley
Comment Utility
Thanks Ronslow,

Looking at it have used more of your info than anybody else's so please "grab" this question and I will award you the points.

By the way, I can't afford to pay for you to go to Barbados - after the day I'm having (first day back) I'm busy saving for my next and already well overdue holiday!


0
 
LVL 4

Expert Comment

by:sganta
Comment Utility
#include <stdio.h>

            struct list {
                                  int  num;
                                  struct list *link;
                           };
            typedef list pointer;
            void sort(pointer *linked_list);
            void swap(pointer *first,pointer *second);
            void main()
            {
               pointer *linked_list;
              /* Create a linked list here */
              sort(linked_list);
            }
            void sort(pointer *linked_list)
            {
               pointer *first,*ptr;*temp,*first_prev,*second_prev;
               first = linked_list;
               first_prev = first;
               while (first->link != null)
               {
                   second_prev = first;
                   second = first->link;
                   while (second->link != null)
                   {
                        if (first->num > second-> num)
                             swap(first,first_prev,second,second_prev);      
                        second_prev = second;
                        second = second->link;
                   }
                   first_prev = first;
                   first = first->link;
              }
            }

        void swap(pointer *first, pointer *first_prev,pointer *second,pointer *second_prev)
        {
               pointer *temp,*swp1,*swp2;
               /* Swap the addresses */
               swp1 = first;
               swp2 = second;
               if (first_prev == first)
               {
                   if (second->link == NULL)
                   {
                        second_prev->link = NULL;
                        second->link = first->link;
                        first->link = null;
                        second_prev->link = first;
                        first = second;
                        return;
                     }
                     second_prev->link = second->link;
                     first_prev = first->link;
                     second->link = first_prev;
                     first_prev = second;
                     first->link = second;
                     second_prev->link = first;
                     first = first_prev;
                     return;
                 }
                  first_prev->link = first->link;
                 
                 if (second->link == NULL)
                 {
                       second_prev->link = first;
                       first->link = NULL;
                       second->link = first_prev->link;
                       first_prev->link = second;
                       first = second;
                       return;
                   }

                    second_prev->link = second->link;
                    second->link = first_prev->link
                    first_prev->link = second;
                    first->link = second_prev->link;
                    second_prev->link = first;
                    return;
      }
0
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
sganta .. can you please let me answer this as Shaley has requested ??

Shaley, you'll need to reject sganta's answer if you want me to be able to propose a question that you can grade.

I feel that other experts here should also get their just deserts .. If you wish to reward any/all of them as well, send Linda a brief message and she'll arrange something for you .. she is very helpful.

PS: Why don't you come down here to Australia for your next holiday?

0
 

Author Comment

by:Shaley
Comment Utility
I wouldn't mind actually.  My girlfriend has travelled around Oz and we would both like to go back.  Perhaps will go again next year and pop in for a beer!

0
 
LVL 4

Expert Comment

by:sganta
Comment Utility
Dear Shaley !

Sorry for the wrong answer. In fact today morning I tried out the solution and I got it.
I hope this will work . The algorithm which I am giving is BUBBLE SORT. Please
Verify this.

#include <stdio.h>

#define NULL 0

struct ptr {
             int num;
             struct ptr *next;
           };

typedef struct ptr pointer;

void bubble_sort(pointer *node);

void main(void)
{
    pointer *list; /* This is a linked list */

    /* Here I am assuming that you've created a linked list
       i.e., ptr
    */

    bubble_sort(list);
}

void bubble_sort(pointer *node)
{
   pointer *first,*second,*first_prev,*temp;
   int n=1;

   temp = node;
   first = node;
   first_prev = node;

   /* Get the no. of nodes in the linked list */
   
   while (first->link != NULL)
   {
      n++;
      first= first->link;
   }


   for (i=1; i<n; i++)
   {
      first = temp;
      first_prev = temp;
      second = first->next;

      for (j=1; j<=(n-i); j++)
      {
         if (first->num > second->num)
         {
            if (first == temp)  /* If it is an header node */
            {
                first->next = second->next;
                second->next = first;
                temp = second;
                first = second;
             }
            else
            {
                first->next = second->next;
                second->next = first;
                first_prev->next = second;
                first = second;
            }
          }
         
          first_prev = first;
          first = first->next;
          second = first->next;
       }              
    }
}          
0
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
sganta .. Shaley wants me to propose an answer, and you keep putting in yours !!

Please let me post my answer as requested.

Hopefully Shaley will take steps (if not, then I will) to arrange for points to be awarded for you as well (I have already suggested that he split points).


0
 
LVL 4

Expert Comment

by:sganta
Comment Utility
Dear RONSLOW

I am very very sorry for the earlier answer. Infact yesterday I worked out with my earlier
answer but it was wrong. Then I found a new solution which is "BUBBLE SORT"
This one is tested and it works fine.

Any way I have to CONGRATULATE YOU that you are in TOP 2 expert.
Can I know your E-Mail Address and your name. It is great to know your
information.

I hope this is acceptable to SHALEY. Sorry for the inconvenience.

Please forgive my mistake.
                        Thanks and Regards
                        SGANTA
0
 

Author Comment

by:Shaley
Comment Utility
PLEASE LEAVE THIS FOR RONSLOW TO PICK UP!!!

I have emailed Linda and asked her to award sganta some points.

Hope this is ok with everyone.

SHALEY
0
 
LVL 10

Accepted Solution

by:
RONSLOW earned 100 total points
Comment Utility
Thanks.  sganta did seem rather keen :-)

0
 
LVL 4

Expert Comment

by:sganta
Comment Utility
Dear Shaley/ Ronslow !

It is very unfair to me. Ronslow has written that
/*
Accepted Answer
    From: RONSLOW
                                                          Date: Thursday, May 21 1998 - 06:58AM PDT

    Thanks.  sganta did seem rather keen :-)
*/

But I did not get any points. This is too much. Why did you do like that ?
We are not children like playing games. We are growned and matured.
I think you know what I mean.

I had worked hard for your question and spent 8 hours to solve the problem.
Finally you rejected my answer just because of RONSLOW. Even though my answer
is accepted, I did'nt get any points. I did not bother about, but it pains me lot.
THANKS A LOT FOR YOUR TREAT.


0
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
Didn't you read the comments from Shaley? .. he said he has written to Linda so she can award points for you.  I also asked for points to be shared and advised Shaley what he needed to do to accomplish this.

Why did Shaley 'do like that'? .. because the answers/comments I provided was what he found most useful.

You may well have worked hard on the question .. I don't doubt that .. but don't you think that other experts have worked hard and/or used our knowledge to help?  Your original answer was rejected because it was incorrect .. not because of me (although I did point out the proble).  Your subsequent answers came after Shaley had already decided to award the points to me and wanted me to post an answer so he could do that.

I think we are being fair .. you will be awarded points for your effort.  Shaley could have just awarded points to me and ignored you altogether .. and I could have accepted them without suggesting that the points be shared.

You'll probably see a question for you in the C area from linda which you can answer so that you can be award the points which you really do deserve.

I think you _should_ be grateful that both Shaley and myself are fair and generous enough to want to ensure you are rewarded for your efforts.

0
 

Author Comment

by:Shaley
Comment Utility
Sganta - I have indeed asked Linda to award you 50 points.  

Thank you for all your hard work and I hope you enjoy your 'treat'.

Sorry you feel agrieved, but thanks again for you help.
0
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
Sganta...

FYI: Try Roger_Onslow@start.com.au - It is nice to be able to talk to other experts here via email instead of the occasional encounter here at EE.  Of course, I trust you don't want my e-mail so you can flame me !!

0
 

Author Comment

by:Shaley
Comment Utility
Sganta...

On Linda's advice I have added a question under C for your response only to enable you to award points.


0
 
LVL 4

Expert Comment

by:sganta
Comment Utility
Dear RONSLOW !
I am not worrying about points. That day I felt so sorry about it because the previous
day I spent time on the above problem.

It's OK. we are like BROTHERS and SISTERS eventhough we cannot see each other.
Thank you for your E-Mail Address. Definetely I will contact you . Thanks & Regards
                                                       SGANTA.
0

Featured Post

Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
mixing C++ and C code elegantly 10 150
SQL handling single and double quotes 3 88
chcp 65001 File encoding 66 215
Line meaning 9 75
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

6 Experts available now in Live!

Get 1:1 Help Now