How do you sort a linked-list data structure?

The sort will be just for display purposes, right?


Look for LL_Sort
  http://ftp.cdut.edu.cn/pub/linux/network/server/route/mrt/html/Public_html/doc/html/mrtprogrammer.html

You'll have to hunt for the code though:

http://ftp.cdut.edu.cn/pub/linux/network/server/route/mrt/mrt/src/

Definitions:

Variable: A variable consists of an ADDRESS where it RESIDES and a VALUE. The value can be an integer, float, etc.

Pointer(or pointer variable): Is a variable whose VALUE is always the ADDRESS in memory at which another variable resides.

Linked lists: A linked list is a set of variables which are related by the fact that each variable (or element) contains at least one ADDRESS of another variable in the SET. This is typical of a SINGLY linked list. A doubly linked list contains at least TWO ADDRESSES - one to traverse forwards and the other backwards. This is true only if you are working with LINEAR linked lists. Other linked lists may be far more complicated.

You can replace the above definitions with compound variables like structs, in which case the VALUE is one of the members.

Now in your question of sorting, there are a number of ways you can do this:

APPROACH 1:

- Keep the list sorted whilst you are building it. e.g.
  Start at the HEAD and see if the alphabetical compare
  of the data means you insert it here or move down to
  the next element/node. If you reach the end (i.e.
  NULL), then you simply add it at the end. This is the
  preferred method. It is less time and overhead
  intensive than first creating an unsorted list and then
  sorting it.

Or if you must sort the list, then use the second approach.

APPROACH 2:

- Create a pointer to the start of a new List. Then
  traverse the old list moving each element into the new
  as you would have done if you maintained a sorted list.
  After you move the element to the new list, adjust the
  pointers in the old.

This should solve your problem.

Hi john_gabriel, welcome to EE (even though you've been around for a few years).

All of the experts here, for the most part have learn from other experts as to the proper etiquette
for posting answer.

Please don't lock questions especialy when the questioner has asked that the question not be locked.

An answer should not be posted as an answer, if other experts have previously posted possible answers
as comments, and/or have already made contributions to the question.

There are many experts who never post answers as answer.  Instead, they post their answers as comments.

If you read the following link, you'll see why this is the preferred method for many of our valued experts,
including myself.

https://www.experts-exchange.com/jsp/cmtyQuestAnswer.jsp

Hi jitjester:
Feel free to click the [Reject Answer] button near john_gabriel 's response, even if it seems like
a good answer.
Doing so will increase your chance of obtaining additional input from other experts.  Later, you can
click the [Select Comment as Answer] button on any response.

Triskelion,
  I was unaware that this actually locked the question. Thanks for the info. However, I am certain the information you provided is not only vague, but also appears to be quite inappropriate. I have provided SOLID, RELIABLE information which IS AN ANSWER!

To put it frankly: I think you should provide USEFUL comments rather than RED Herrings which I believe is what you have done. UNLESS you KNOW what you are talking about, you should refrain even from making USELESS comments and let the true experts answer the question.

John

Hi John,
I can see you have been here since 1998.  With your expert points, I can see you have not posted many correct answers.  Tres has tried to be nice in this and I as a Moderator will step in.  Your proposed answer may be correct but your attitude is not. The questioner will have the option to accept your answer.  In this topic area, it is a standard that proposed answers are not given.  For that reason, your proposed answer is rejected.

Computer101
E-E Moderator

As this is really early to propose an answer, that is another reason to leave it in open questions.

Computer101
E-E Moderator

Moderator,
   All the answers I have submitted are CORRECT. You can see NOTHING but your own stupidity.

Actually, I stopped answering questions because I ran into fools like Tres way back in 1998. Grades received mean nothing to me. Why did I start to contribute again? E-E invited me to contribute. I can see it is a waste of my precious time, therefore I shall cease once and for all to contribute.

Don't bother replying because I will turn off notifications from EE!

"You can see NOTHING but your own stupidity."


Thanks for your input.


Noted

Computer101
E-E Moderator

jitjester:

Unlike others, I don't consider links to functioning code a red herring, vague, or useless.  Triskelion's links are on the mark.

If you haven't already found it, the various LL_Sort functions are at:

http://ftp.cdut.edu.cn/pub/linux/network/server/route/mrt/mrt/src/lib/struct/linked_list.c

Hmm...looks like I've missed a lot while I was gone. :-)  In any case, all the links I've been supplied with seem to involve much more complicated data structures than what is necessary for my purposes.  I could just implement them, but I'd like a kind of templated form for an alphabetical sort on my structs.  I know I did this in C++ back in school using node objects, but I can't think of a quick, simple way to do the same thing in C.  This thing has to interface with some other stuff that is in C, so I can't use my old code.  If one of you could just verbalize the process, I can figure out the code for it.  If not, I'll figure it out from the links that have already been given.  I do appreciate everyone who has tryed to help so far.  I'll increase the points if someone makes it easy for me..;-)

jitjester

Well, john_gabriel did verbalize the process.
Were you looking for something other than that or a plain sort?

john_gabriel, the JSP code is being re-written, so the unsubscribe is broken, which means, you Will get notifications, unless you choose to filter at your email, which you probably not yet done.  At least until you see my reply.

I am quite sure that IF you were called, it was probably from either the EAB or Austin Miller.  It would be nice if all the older Experts came back, including you.  

But, this site will not tolerate flaming others.  You have shot the mmessenger my friend.  This "Locked" question was a response generated from another Expert in Community Support.  We answer each and every question or complaint that is posted there.  I have no doubt in and of your abilities, and as I said before we would like for you to re-join EE, but please leave the attitude behind.

And to your remark, yes the site has changed...for the better.  The site will continue to grow with or without you, I would like all the old Experts to return, and many have but they abide by the MA and T&C's.

It is up to you to make the bed, in which you lay.  If you feel you would like to discuss this, feel free to contact me at comtech@experts-exchange.com , and referrence this QID number or URL.

The ball is in your court!

Regards,
ComTech
CS Admin @ EE

btw-the Moderator and Triskelion have been around as long as you, and they are both very good Experts.

Your call.

Do a bubble sort:
Keep doing passes on the data, comparing consecutive elements (and swapping if incorrect order) until a pass produces no swapping.

BOOL mustsort = true;
while (mustsort)
{
 mustpass = false;
 ITEM * pItem = First;
 while (pItem != NULL)
 {
  ITEM * pNext = pItem->Next;
  if (pNext != NULL)
  {
    if (inwrongorder(pItem, pNext))
    {
      swaporder(pItem, pNext);
      mustpass = true;
    }
  }
  pItem = pItem->Next;
 }
}

hi,

an easy way to do it is to read each element in turn , and compare it with the next one using strcmp. if it belongs where it is, go on to the next element, and repeat the process. if it belongs after element 2, you should insert it in its place. you will need to alter the pointers to the elements that have moved, so mke sure you store these


eg


element 1

data:  aaaaaaaa
pointer1: pointer to element 2

element 2

data:  cccccccc
pointer2:  pointer to element 3


element 3

data: bbbbbbbb
pointer3: null

as you can see element one is in the correct position, so move onto element 2.

element 2 belongs after element 3, so you need to change pointer 1 to point to element 3, change pointer 2 to null, and change pointer3 to point to element 2.

It always helps me to thing of it as a piece of string, which you cut two sections out of, and then swap them. to make it a whole peice again, you nedd to tie them back to gether.

how about using the qsort routine from stdlib.h?

1. allocate an array of pointers large enough to store
   pointers to all your list members

2. check the documentation for qsort and write an
   appropriate compare function

3. sort that pointer array using qsort

4. update the first-member-pointer and the next fields
   in your list using the sorted pointer array

5. dispose the sorted pointer array

Hope this helps

2 jitjester
it seems to be a hard insert a comments for this topic but I try.

IMHO, the best way for sorting list it is moving items in the new order. I hope you already know how to realize functions:
RemoveNodeAfter(root) -- root->N1->N2 = root->N2
InsertAfterNode(root,N1) -- root->N2 = root->N1->N2
CompareNode(root, N1) -- return -1 <, 0 ==, 1 >

We have unsorted list started as RootOld nad sorted list as RootNew. Here is pseudocod (undebugged, not optimal)

while (RootOld != NULL) {
    //Get old node
  pCurrNode = RootOld->pNext;
  if (pCurrNode != NULL) {
    RemoveNodeAfter(RootOld);
   }else{
     pCurrNode = RootOld;
     RootOld = NULL;
  }  
     // insert in the new list
  if (RootNew != NULL){
     if (CompareNode(RootNew,pCurrNode) < 0) {
         // new node is "smaller" as root
       pCurrNode->pNext = RootNew;
       RootNew = pCurrNode;
      }else{
       pInsertNode = FindInsertNode(RootNew, pCurrNode);
       InsertAfterNode(pInsertNode,pCurrNode);
     }
   }else{
     RootNew = pCurrNode;  
  }
}

//pTestNode always >= pStartNode
FindInsertNode(pStartNode, pTestNode)
{
  pCurrNode = pStartNode;
  pLastNode = pCurrNode;
  while (pCurrNode != NULL) {
    nCompare = CompareNode(pCurrNode, pTestNode);
    if (nCompare >= 0 ) {
      pLastNode = pCurrNode;
      pCurrNode = pCurrNode->pNext;
     }else{
       // test node > pLastNode && test node < pCurrNode. Exit
      break;      
    }
  }
  return pLastNode;
}

I'm really new to the Experts Exchange, but hopefully not new to C.  It seems that there are several comments pointing you in the right direction, but no real answers.

I think that the code below demonstrates several suggested solutions, with sorting done by allocating space to hold all the pointers; using qsort to sort those; then applying the new pointers throughout the list.  It extends the comments to include sorting by arbitrary types (a c-string and int are used as examples), and to show how the same comparison functions could be used to keep the list in the same order even when adding items, hopefully while demonstrating reasonable memory-handling practice.  Note that list node deletions and modifications are left as "an exercise for the reader" :-).

#include <stdlib.h>
#include <stdio.h>

/* Type definitions for sort directions */
typedef enum {
  SORT_NONE,
  SORT_STRING_ASC,
  SORT_STRING_DESC,
  SORT_INTEGER_ASC,
  SORT_INTEGER_DESC
} SortEnum;

/* Type definition for comparison functions */
typedef int (*CmpFun)(const void *, const void *);

/* Type definitions for list nodes */
typedef struct NodeStruct *NodePtr;
typedef struct NodeStruct {
  NodePtr   next;
  char      *string;
  int       integer;
} Node;

/* Type definition for a list head */
typedef struct HeadStruct *HeadPtr;
typedef struct HeadStruct {
  int       listLength;
  NodePtr   list;
  SortEnum  sortOrder;
  CmpFun    cmpFun;
} Head;

/* Comparison functions */
int cmpNone (const void *a, const void *b) {
  return 0;
}

int cmpStringAsc(const void *a, const void *b) {
  NodePtr *nodePtrPtrA, *nodePtrPtrB;

  nodePtrPtrA = (NodePtr *) a;
  nodePtrPtrB = (NodePtr *) b;

  return strcmp((*nodePtrPtrA)->string, (*nodePtrPtrB)->string);
}

int cmpStringDesc(const void *a, const void *b) {
  return -1 * (cmpStringAsc(a, b));
}

int cmpIntegerAsc(const void *a, const void *b) {
  NodePtr *nodePtrPtrA, *nodePtrPtrB;
  int cmp;

  nodePtrPtrA = (NodePtr *) a;
  nodePtrPtrB = (NodePtr *) b;

  if ((*nodePtrPtrA)->integer == (*nodePtrPtrB)->integer) {
    cmp = 0;
  } else if ((*nodePtrPtrA)->integer < (*nodePtrPtrB)->integer) {
    cmp = -1;
  } else {
    cmp = 1;
  }

  return cmp;
}

int cmpIntegerDesc(const void *a, const void *b) {
  return -1 * (cmpIntegerAsc(a, b));
}

/* Function to create a node */
NodePtr createNode(char *string, int integer) {
  NodePtr nodePtr;

  nodePtr = (NodePtr) malloc(sizeof(Node));
  nodePtr->next = (void *) NULL;
  nodePtr->string = (char *) malloc((strlen(string) + 1) * sizeof(char));
  strcpy(nodePtr->string, string);
  nodePtr->integer = integer;

  return nodePtr;
}

/* Function to free a node */
void freeNode(NodePtr *nodePtrPtr) {
  free((*nodePtrPtr)->string);
  free(*nodePtrPtr);
  *nodePtrPtr = (void *) NULL;
}

/* Functon to create a list (header) */
HeadPtr createList() {
  HeadPtr headPtr;

  headPtr = (Head *) malloc(sizeof(Head));
  headPtr->listLength = 0;
  headPtr->list = (void *) NULL;
  headPtr->sortOrder = SORT_NONE;
  headPtr->cmpFun = cmpNone;

  return headPtr;
}

/* Function to free an entire list */
void freeList(HeadPtr *headPtrPtr) {
  NodePtr nodePtr, nextPtr;

  nodePtr = (*headPtrPtr)->list;
  while (nodePtr != (void *) NULL) {
    nextPtr = nodePtr->next;
    freeNode(&nodePtr);
    nodePtr = nextPtr;
  }

  free(*headPtrPtr);
  *headPtrPtr = (void *) NULL;
}

/* Function to print a list */
void printList(HeadPtr headPtr) {
  NodePtr nodePtr;

  printf("List contents (%d), sort order %d:\n", headPtr->listLength, headPtr->sortOrder);
  for (nodePtr = headPtr->list; nodePtr != (void *) NULL; nodePtr = nodePtr->next) {
    printf("  <%s><%d>\n", nodePtr->string, nodePtr->integer);
  }
  printf("List ends\n");
}

/* Function to add values as the final list node (inefficient, but demonstrates navigation) */
void addListNode(HeadPtr headPtr, NodePtr nodePtr) {
  NodePtr *nodePtrPtr;

  /* Find position to add node, and add it! */
  for (nodePtrPtr = &(headPtr->list); *nodePtrPtr != (void *) NULL; nodePtrPtr = &((*nodePtrPtr)->next));
  *nodePtrPtr = nodePtr;

  /* Increment header node count */
  headPtr->listLength += 1;
}

/* Function to add values as a list node, preserving the current sort order */
void addSortedListNode(HeadPtr headPtr, NodePtr nodePtr) {
  NodePtr *nodePtrPtr, *nodePtrPtrOther;

  /* If the list is empty, simply add the node and we're done */
  if (headPtr->list == (void *) NULL) {
    nodePtr->next = headPtr->list;
    headPtr->list = nodePtr;
    headPtr->listLength += 1;
    return;
  }

  /* Otherwise, use the comparison function to find the insertion point */
  nodePtrPtr = &nodePtr;
  for (nodePtrPtrOther = &(headPtr->list);
       *nodePtrPtrOther != (void *) NULL;
       nodePtrPtrOther = &((*nodePtrPtrOther)->next)) {
    if (headPtr->cmpFun(nodePtrPtr, nodePtrPtrOther) < 1) {
      break;
    }
  }

  /* Found position, so insert the node */
  nodePtr->next = *nodePtrPtrOther;
  *nodePtrPtrOther = nodePtr;

  /* Don't forget to update the record count */
  headPtr->listLength += 1;
}

/* Function to sort list in some way */
void sortList(HeadPtr headPtr, SortEnum sortOrder) {
  NodePtr nodePtr;
  NodePtr *nodePtrPtr;
  NodePtr *nodePtrArray;
  CmpFun  cmpFun;
  int     i;

  /* Assign sort function */
  switch (sortOrder) {
  case SORT_NONE:
    fprintf(stderr, "WARNING: No sort order leaves list unchanged\n");
    return;
  case SORT_STRING_ASC:
    cmpFun = &cmpStringAsc;
    break;
  case SORT_STRING_DESC:
    cmpFun = &cmpStringDesc;
    break;
  case SORT_INTEGER_ASC:
    cmpFun = &cmpIntegerAsc;
    break;
  case SORT_INTEGER_DESC:
    cmpFun = &cmpIntegerDesc;
    break;
  default:
    fprintf(stderr, "ERROR: Unexpected sort enum <%d> (%s:%d)\n", sortOrder, __FILE__, __LINE__);
    return;
  }

  /* Allocate space for array of pointers */
  nodePtrArray = (NodePtr *) malloc(headPtr->listLength * sizeof(NodePtr));

  /* Initialise array of node pointers */
  i = 0;
  for (nodePtr = headPtr->list; nodePtr != (void *) NULL; nodePtr = nodePtr->next) {
    nodePtrArray[i] = nodePtr;
    i++;
  }

  /* Sort array */
  qsort((void *) nodePtrArray, (size_t) headPtr->listLength, sizeof(NodePtr), cmpFun);

  /* Apply result */
  nodePtrPtr = &(headPtr->list);
  for (i = 0; i < headPtr->listLength; i++) {
    *nodePtrPtr = nodePtrArray[i];
    nodePtrPtr = &((*(nodePtrArray[i])).next);
  }
  *nodePtrPtr = (void *) NULL;

  /* Store detail in list head */
  headPtr->sortOrder = sortOrder;
  headPtr->cmpFun = cmpFun;

  /* Free pointer array */
  free(nodePtrArray);
}

/* Main program */
int main (int argc, char *argv[]) {
  HeadPtr headPtr;

  /* Create list head */
  headPtr = createList();
  printList(headPtr);

  /* Create example list */
  addListNode(headPtr, createNode("Two", 2));
  addListNode(headPtr, createNode("One", 1));
  addListNode(headPtr, createNode("Three", 3));
  printList(headPtr);

  /* Sort list by ascending integer */
  printf("Setting sort order to SORT_INTEGER_ASC\n");
  sortList(headPtr, SORT_INTEGER_ASC);
  printList(headPtr);
  printf("Setting sort order to SORT_STRING_ASC\n");
  sortList(headPtr, SORT_STRING_ASC);
  printList(headPtr);

  addSortedListNode(headPtr, createNode("Four", 4));
  printList(headPtr);

  printf("Setting sort order to SORT_STRING_DESC\n");
  sortList(headPtr, SORT_STRING_DESC);
  printList(headPtr);
  printf("Setting sort order to SORT_INTEGER_DESC\n");
  sortList(headPtr, SORT_INTEGER_DESC);
  printList(headPtr);

  /* Sort list by descending integer */
  printf("Setting sort order to SORT_INTEGER_ASC\n");
  sortList(headPtr, SORT_INTEGER_ASC);
  addSortedListNode(headPtr, createNode("Five", 5));
  addSortedListNode(headPtr, createNode("Zero", 0));
  printList(headPtr);

  /* Tidy up */
  freeList(&headPtr);

  exit(0);
}

melliffe, please read my comments posted on:
   05/06/2002 05:00PM PST


It's always good to read the comments before posting.

Triskelion: I *did* read the comments, and said so in my answer, but it seems that I only understood them with respect to the question (i.e. it seemed to me that the original questioner wanted to see some real code).  Unless you tell me otherwise, I'll take it from your comment that what I got wrong was etiquette, specifically that I should post comments *only*, regardless whether or not I think my "answer" provides a significant advance on existing comments ... not readily apparent as a newbie, since even when I followed the link you supplied (and I had read this before I posted), the advice seemed ambiguous at best!

Whatever, it was nice to flex some C muscles that haven't been used in years.

No offence taken, and none intended in return.  Cheers

-- melliffe

melliffe, I have rejected your answer, as it is proper to let the User accept a comment as the answer.  You will also make more firends by doing so.  Some if not all of use did it at first, I was balsted much worse than you.

Your comment is still in the running, just please post comments.

Thank you,
ComTech
CS Admin @ EE

Triskelion: I *did* read the comments, and said so in my answer, but it seems that I only understood them with respect to the question (i.e. it seemed to me that the original questioner wanted to see some real code).  Unless you tell me otherwise, I'll take it from your comment that what I got wrong was etiquette, specifically that I should post comments *only*, regardless whether or not I think my "answer" provides a significant advance on existing comments ... not readily apparent as a newbie, since even when I followed the link you supplied (and I had read this before I posted), the advice seemed ambiguous at best!

Whatever, it was nice to flex some C muscles that haven't been used in years.

No offence taken, and none intended in return.  Cheers

-- melliffe

i think i have to side with mellife on this........

Answers
An answer is a specific solution to a question and should be submitted if it will solve the questioner's problem and doesn't duplicate a previous comment

(taken from bottom of page). It seems to me that the proposed answer conformed to the advice given. perhaps this should be changed?

2 ComTech
Is it not better to remove both radio buttons "Comment", "Answer" and post all topics as comment.

My only concern was of etiquette.
I had to get used to it too.
...and yes, I was blasted before I fell into the etiquette.

I only post answers when there has been no attempt at a solution.

This question has been open for a long time with little response from jitjester.

*Something* in this thread has to be an answer.

BOOL mustsort = true;
while (mustsort)
{
  mustsort= false;
  ITEM * pItem = First;
  while (pItem != NULL)
  {
   ITEM * pNext = pItem->Next;
   if (pNext != NULL)
   {
     if (inwrongorder(pItem, pNext))
     {
       swaporder(pItem, pNext);
       mustsort= true;
     }
   }
   pItem = pItem->Next;
  }
}


//you have to implement the inwrongorder function
//you have to implement the swaporder function

BOOL inwrongorder(ITEM * pSmaller, ITEM * pLarger); //returns FALSE if *pSmaller is larger than *pLarger

void swaporder(ITEM * pFirst, ITEM * pNext); //swap order so that the pNext is in pFirst's place and pFirst is in pNext's place.

Good luck!

Hi Alex, that has been a Topic of debate for years, and is seems to me and other Experts, that is causes nothing by problems.  With the New owners, this could actually take place as it is being polled and taken into consideration during this re-write.  We are re-writing the code page by page, a difficult process at best.  And we are breaking it down into sections, as of now in our third Beta Phase.  This last one, we pushed some new Topic Areas, and if okay, we will release them into the site.  I have requested this batch to contain the .Net series.

Thakns for asking,
ComTech
CS Admin @ EE

btw-we still have "Whats New" but for site info, we have created a TA called Community News, and can be found on the left side of each page, beneath What's New.

Has anything worked so far, jitjester?

Wow, I just realized that this thread was still open.  Honestly I recall posting this question and being overwhelmed by the responce.  I think I eventually found my solution elsewhere or didn't need it anymore.  In any case, looking back over it now I really don't know who I should award the points to.  If a moderator wants to just give it to whoever or if someone who originally participated in this thread wishes to make a case for their answer as THE answer, that would be fine.  

I do appologize to everyone that participated and got less than a worthy responce from me.  It was about the time I posted this that I lost my internet access at home and I have just recently regained it and gotten involved with ee once again.  Thanks so much to everyone that put time into this, I really do appreciate it.

jitjester

No comment has been added lately, so it's time to clean up this TA.

I will leave a recommendation in the Cleanup topic area that this question is:
Accept Triskelion's comment as answer

Please leave any comments here within the next seven days.

PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!

Kent (Kdo)
EE Cleanup Volunteer