putting linked list in order

**mackieinva** · 09-20-2007

hi people, i made a program that puts 25 random integers into a linked list, and then finds the sum and average. everything works fine, one thing im wondering is if i wanted to put these numbers in order from lowest to highest how can i walk through the list to do that? I know the for loop needs to be there walking through num 1-25 but im not sure how to compare them with pointers in a linked list. thanks for the help.

Code:

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

struct listNode {
   struct listNode *nextPtr;
   int data;
};

typedef struct listNode ListNode;
typedef ListNode *ListNodePtr;

void printList( ListNodePtr currentPtr );
int generateList( ListNodePtr *startPtr );

int main()
{
          int total;
          ListNodePtr startPtr = NULL;

                      generateList( &startPtr );

                      total = get_total(startPtr);

                      printList( startPtr );

                      printf( "\nTotal of all 25 elements is %d", total );
                      printf( "\nAverage of all 25 elements is %.2f\n\n", (float)total / 25 );
   
                       getchar();
                       return 0;
}


int generateList( ListNodePtr *startPtr )
{
     int randNum, total = 0, i = 0;
     ListNodePtr newPtr, currentPtr;
     srand( time( NULL ) );

   

            for (i =0; i < 25; i++ ) {
                 randNum = rand() % 100;
                 newPtr = malloc( sizeof( ListNode ) );
                 newPtr->data = randNum;
                 newPtr->nextPtr = NULL;

	                             if(*startPtr == NULL)	{ 
	                             *startPtr = newPtr; 
	                             currentPtr=newPtr;
	                             continue;
	                                                    }
                                                        currentPtr->nextPtr=newPtr;	
                                                        currentPtr=currentPtr->nextPtr;
          }
   return 0;
}




void printList( ListNodePtr currentPtr )
{ 
                if ( currentPtr == NULL )
                   printf( "List is empty.\n\n" );
                                 else { 
                                      printf( "The list is:\n" );

                                              while ( currentPtr != NULL ) { 
                                                    printf( "%d, ", currentPtr->data );
                                                    currentPtr = currentPtr->nextPtr;
                                              }

                                              printf( "NULL\n\n" );
                                }
               }


int get_total(ListNodePtr currentPtr)
{

                          if(currentPtr==NULL) return 0;

                          return currentPtr->data + get_total(currentPtr->nextPtr);

}

**matsp** · 09-20-2007

You need to do something along the lines of this stupid bubble sort:

Code:

void sortList(ListNodePtr list) {
   ListNodePtr *p;
   ListNodePtr *q;
   
   for(p = list; p; p = p->next) {
      for(q = p->next; q; q = q->next) {
         if (q->data < p->data) swap(q, p);
      }
   }
}

I'll let you figure out how to do swap (and no cheating of swapping just the data, ok?)

The other option is of course to insert it sorted in the first place.

--
Mats

**mackieinva** · 09-20-2007

thanks mats, i kind of get the idea, will post what i did soon.

**iMalc** · 09-21-2007

Bubble sort on a linked-list isn't nearly as simple as it is for an array.

Actually, that's not BubbleSort either. Bubble sort always swaps adjacent items, and is hence always stable. You've posted SimpleSort (as I call it) which is not stable. Furthurmore, to swap two arbitrary items in a list requires the previous node pointer for each item, which since this isn't a doubly-linked list you have to track yourself, as well.

The simplest singly-linked-list sorting algorithm is actually InsertionSort. I suggest using that, since it is only 25 items.

You could refer to the list-sorting pages from the link in my sig...

**mackieinva** · 09-24-2007

yeah i still cant find the right way to do it. I went to your links iMalc but couldn't find the right thing i guess. thanks for anyone that can help me with putting the list in order from lowest to highest, still confused on how to do that. later people.

**Prelude** · 09-24-2007

If you need it sorted, why not build it sorted from the start? That saves you the trouble and upfront cost of an explicit sorting operation. I believe in the help by massive information method, so see if this helps you. It covers building a sorted list as well as a great deal of other information you might find helpful.

**matsp** · 09-24-2007

An insertion-sort looks something like this:

Code:

struct node {
   int data;
   struct node *next;
};

/* Take the list indicated by head, and create a new one, 
 * returning the head of the new list. 
 */
struct node *insertion_sort_list(struct node *head)
{
    struct node  *newhead = NULL;
    struct node *p;
    struct node *pNext;
    struct node *q;
    struct node *qPrev;

    for ( p = head; p; p = pNext) {
       pNext = p->next;
       // Simplest case - new list is empty, insert current element first. 
       if (newhead == NULL) {
          newhead = p;
          p->next = NULL;
       } else {
         qPrev = NULL;
         for(q = newhead; q->data < p->data; qPrev = q, q = q->next);
         // Is the current value smaller than first item in the list?
         // If so, make this a new head.
         if (qPrev == NULL) {
            p->next = newhead;
            newhead = p;
        } else {
            qPrev->next = p;
            p->next = q;
        }
      }
    }
    return newhead;
}

I haven't tested this code, but I beleive it's correct.

**mackieinva** · 09-24-2007

this is what i put together but I did something wrong, received some errors and dont know where to begin to fix them.

Code:

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

struct listNode {
   struct listNode *nextPtr;
   int nums;
};

typedef struct listNode ListNode;
typedef ListNode *ListNodePtr;

void printList( ListNodePtr currentPtr );
int generateList( ListNodePtr *startPtr );

int main()
{
          int total;
          ListNodePtr startPtr = NULL;

                      generateList( &startPtr );

                      total = get_total(startPtr);

                      printList( startPtr );

                      printf( "\n\n\nTotal: &#37;d", total );
                      printf( "\nAverage: %.2f\n\n", (float)total / 25 );
   
                       getchar();
                       return 0;
}


int generateList( ListNodePtr *startPtr )
{
     int randNum, total = 0, i = 0;
     ListNodePtr newPtr, currentPtr;
     srand( time( NULL ) );

   

            for (i =0; i < 25; i++ ) {
                 randNum = rand() % 100;
                 newPtr = malloc( sizeof( ListNode ) );
                 newPtr->nums = randNum;
                 newPtr->nextPtr = NULL;

	                             if(*startPtr == NULL)	{ 
	                             *startPtr = newPtr; 
	                             currentPtr=newPtr;
	                             continue;
	                                                    }
                                                        currentPtr->nextPtr=newPtr;	
                                                        currentPtr=currentPtr->nextPtr;
          }
          insertion_sort_list(&startPtr); 
   return 0;
}




void printList( ListNodePtr currentPtr )
{ 
                if ( currentPtr == NULL )
                   printf( "List is empty.\n\n" );
                                 else { 
                                      printf( "The list is:\n" );

                                              while ( currentPtr != NULL ) { 
                                                    printf( "%d ", currentPtr->nums );
                                                    currentPtr = currentPtr->nextPtr;
                                              }

                                             
                                }
               }


int get_total(ListNodePtr currentPtr)
{

                          if(currentPtr==NULL) return 0;

                          return currentPtr->nums + get_total(currentPtr->nextPtr);

}


int insertion_sort_list(ListNodePtr *startPtr)
{
    struct node  *newStart = NULL;
    struct node *newPtr;
    struct node *newPtrNext;
    struct node *nextPtr;
    struct node *nextPtrPrev;

    for ( newPtr = startPtr; newPtr; newPtr = newPtrNext) {
       newPtrNext = newPtr->next;
       // Simplest case - new list is empty, insert current element first. 
       if (newStart == NULL) {
          newStart = newPtr;
          newPtr->next = NULL;
       } else {
         nextPtrPrev = NULL;
         for(nextPtr = newStart; nextPtr->data < newPtr->data; nextPtrPrev = nextPtr, nextPtr = nextPtr->next);
         // Is the current value smaller than first item in the list?
         // If so, make this a new head.
         if (nextPtrPrev == NULL) {
            newPtr->next = newStart;
            newStart = newPtr;
        } else {
            nextPtrPrev->next = newPtr;
            newPtr->next = nextPtr;
        }
      }
    }
    return newStart;
}

**matsp** · 09-24-2007

Then you'd better post the errors!

--
Mats

**mackieinva** · 09-24-2007

In function `insertion_sort_list':
99 [Warning] assignment from incompatible pointer type
104 [Warning] assignment from incompatible pointer type
107 [Warning] assignment from incompatible pointer type
107 [Warning] assignment from incompatible pointer type
107 [Warning] assignment from incompatible pointer type
111 [Warning] assignment from incompatible pointer type
114 [Warning] assignment from incompatible pointer type
115 [Warning] assignment from incompatible pointer type
119 [Warning] assignment from incompatible pointer type

i have no idea how to fix that problem, i understant that its with how i coded the pointers but thats about it.

**Prelude** · 09-24-2007

I'm guessing those errors come from the fact that you're trying to use struct node rather than struct listNode. I also get quite a few more errors and warnings than you posted, so you might want to turn up your compiler's ..........y level.

**matsp** · 09-24-2007

And you may want replace this:

Code:

          insertion_sort_list(&startPtr);

with something like:

Code:

          startPtr = insertion_sort_list(startPtr);

--
Mats

**Prelude** · 09-24-2007

>And you may want replace this:
>with something like:
Not when insertion_sort_list returns an int.

Do a brain compile on the OP's code, it needs a bit more work than just fixing the errors posted.

**mackieinva** · 09-24-2007

thanks for helping guys, i may never get this one but im still trying.

**ggs** · 09-25-2007

Merge sort provides excellent performance and the implementation for linked lists is remarkably elegant.

The following routine should return a pointer to a linked list.

If the linked list given to be sorted is only 1 nodes in length or NULL, it is already sorted, so you can just return.

1. Save a pointer to the first list node.

2. Walk through your list in a loop with two pointers. Advance one pointer one node at a time, advance the 2nd two nodes at a time.

3. When the 2nd pointer has hit null, your 1st pointer is at the halfway point of the list. Save a pointer to the node after the 1st pointer, and set the next node of the 1st pointer to null.

Now the pointer you saved in step 1 points to the first half of the list, and pointer you saved in step 3 points to the second half of the list.

Recursively call your sort routine on both lists. Since your sort routine returns a linked list, save the return values of each.

Now you need to merge the 2 lists together. Since each of the lists is sorted, you can just set a pointer to the start of each list and start a loop where you build the larger sorted list.

From the two pointers, pick the node with the smallest value, and add it to the return list. Advance the pointer which you picked the node from to the next value in its list. When one of the pointers runs out of nodes, append the other list to your sorted list.

Return the newly constructed sorted list.

Try running this algorithm on paper with some small (maybe 5 or 6 valued) lists before implementing it, and it will be easy to see how and why it works.

If my explanation doesn't cut mustard, try searching on the web for it, or using the link below.

http://en.literateprograms.org/Category:Merge_sort

Thread: putting linked list in order

Thread Tools

Search Thread

Display

putting linked list in order

Similar Threads

C++ Linked list program need help !!!

single linked list to double linked list (help)

seg fault for linked list in another linked list--help!!

putting search result into a linked list

problem with structures and linked list