Linked list sorting in C

Question

I'm writing a simple file for one of my classes that is a simple linked list activity and I need to sort a linked list.

This is my source code so far:

/*
 * Simple list manipulation exercise.
 * 1. Create a list of integers.
 * 2. Print the list.
 * 3. Sort the list.
 * 4. Print the list
 * 5. Free the list nodes.
 */

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

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

extern struct node *mk_node(int v) ;
extern void print_list(struct node *head) ;
extern struct node *sort_list(struct node *head) ;
extern void free_list(struct node *head) ;

#define NVALUES (6)

int initial_contents[] = { 3, 8, 2, 5, 1, 9 } ;

/*
 * Main driver program. Create the list from the initial_contents,
 * print it, sort it, print it, free it, and return.
 */

int main() {
    struct node *head = NULL ;
    struct node *curp ;

    int i ;

    /*
     * Put the initial values into the list. This algorithm
     * will result in the values being inserted in reverse
     * order of the array.
     */
    for( i = 0 ; i < NVALUES ; i++ ) {
        curp = mk_node( initial_contents[i] ) ;
        curp->next = head ;
        head = curp ;
    }

    print_list(head) ;
    head = sort_list(head) ;
    print_list(head) ;
    free_list(head) ;

    return 0 ;
}

/*
 * Return a new node with 'v' as the label and a NULL next link.
 */

struct node *mk_node(int v) {
    struct node *newp = malloc( sizeof(struct node) ) ;
    newp->value = v;
    newp->next = NULL;  

    return newp ; // Place holder
}

/*
 * Print the list headed by 'head', one value per line.
 */

void print_list(struct node *head) {
    printf("List: ");
    struct node *ptr = head;
    while(ptr!=NULL){
        printf("%d ", ptr->value);
        ptr=ptr->next;
    }
    putchar('\n');
}    

/*
 * Sort the list headed by 'head', returning a pointer to the node
 * that ends up at the head of the list.
 */

struct node *sort_list(struct node *head) {
    struct node *tmpPtr;
    struct node *tmpNxt;

    tmpPtr = head;
    tmpNxt = head->next;

    int a, tmp;

    while(tmpNxt != NULL){
        a = tmpPtr->value;
        while(tmpNxt != tmpPtr && tmpNxt->value < a){
            tmp = a;
            tmpPtr->value = tmpNxt->value;
            tmpNxt->value = tmp;
            tmpPtr = tmpPtr->next;
        }
        tmpPtr = head;
        tmpNxt = tmpNxt->next;
    }

    return tmpPtr ; // Place holder
}

/*
 * Free all the nodes in the list headed by 'head'.
 */

void free_list(struct node *head) {
    //struct node *releasep ;
    //while( head != NULL ){
//      releasep = head;
//      head = head->next ;
//
//      free(releasep->value) ;
//      free(releasep) ;
//  }
}

I'm having troubles with my sort method. I even even went step by step and I can't find the problem.

Below is my program's output.

XXXXXXX@linus:~/350/c_memory_activity$ gcc -o test listsort.c 
XXXXXXX@linus:~/350/c_memory_activity$ ./test 
List: 9 1 5 2 8 3 
List: 1 9 5 2 8 3 
XXXXXXX@linus:~/350/c_memory_activity$

P.S.: Original sorting algorithm was here: Linked list insertion sort

Tagged as homework since it says its for one of his classes... — alternative
– alternative, Commented Apr 3, 2011 at 0:27
@sehe Ya it was for homework, it was stated at top, sorry I didn't know there was a homework tag. — DestroyerDust
– DestroyerDust, Commented Apr 3, 2011 at 0:31
As a side note I don't see the point of sorting a linked list, when you really should use some other data structure if you need to sort. — alternative
– alternative, Commented Apr 3, 2011 at 0:38

MByD · Accepted Answer · 2011-04-03 00:38:50Z

5

Well, This loop will only go once (in the good case):

 while(tmpNxt != tmpPtr && tmpNxt->value < a){
        tmp = a;
        tmpPtr->value = tmpNxt->value;
        tmpNxt->value = tmp;
        tmpPtr = tmpPtr->next;
    }

Since it's homework, just a hint: which is tmpNxt and which is tmpPtr after the first iteration?

another lines to look at are those:

tmpPtr = head;
tmpNxt = tmpNxt->next;

both examples explain why only the first two elements were replaced in your example.

answered Apr 3, 2011 at 0:38

MByD

138k30 gold badges269 silver badges278 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

DestroyerDust Over a year ago

Ok, ill take another look through it right now and see what I get.

DestroyerDust Over a year ago

I understand why the first loop breaks on first run, but I don't fully understand why the 2nd part, (tmpPtr = head; tmpNxt = tmpNxt->next;) is causing problems...

MByD Over a year ago

@DestoyerDust print the value of a before entering the loop (hint hint...) I only pointed out part of the problem, but you will need to reconsider this way of sorting.

salezica · Accepted Answer · 2011-04-03 00:45:22Z

3

MByD already pointed out the problem (my upvote for you, MByD), so with that addressed, I'd like to contribute some advice.

Sorting is one of the problems that have been tackled over, and over, and over and over in the history of computer science. There's an excellent Wikipedia article with an index and comparison of tons of sorting algorithms. Pick a few and learn how they work! Reverse-engineering (sort of) algorithms is a great way to improve your own skills.

Try for example bubble sort, insertion sort and quick sort.

Cheers!

answered Apr 3, 2011 at 0:45

salezica

77.5k29 gold badges113 silver badges168 bronze badges

1 Comment

DestroyerDust Over a year ago

Thanks for the Wikipedia article! I'm in the process of taking MByD's suggestion and working it step by step again.

DestroyerDust · Accepted Answer · 2011-04-03 02:16:21Z

1

I figured it out after some stack traces with a friend. Heres the fixed code:

struct node *sort_list(struct node *head) {

    struct node *tmpPtr = head;
    struct node *tmpNxt = head->next;

    int tmp;

    while(tmpNxt != NULL){
           while(tmpNxt != tmpPtr){
                    if(tmpNxt->value < tmpPtr->value){
                            tmp = tmpPtr->value;
                            tmpPtr->value = tmpNxt->value;
                            tmpNxt->value = tmp;
                    }
                    tmpPtr = tmpPtr->next;
            }
            tmpPtr = head;
            tmpNxt = tmpNxt->next;
    }
         return tmpPtr ; // Place holder
}

answered Apr 3, 2011 at 2:16

DestroyerDust

471 gold badge2 silver badges10 bronze badges

Comments

user1596193 · Accepted Answer · 2013-03-17 03:38:18Z

Here is my version of linked list sorting using Quick Sort Algorithm. Check if this helps..

#include "stdafx.h"
#include "malloc.h"

typedef struct node {
    struct node *next;
    int val;
} node;

bool insert_node(struct node **head, int val)
{
    struct node *elem;
    elem = (struct node *)malloc(sizeof(struct node));
    if (!elem)
        return false;
    elem->val = val;
    elem->next = *head;
    *head = elem;
    return true;
}

int get_lval(struct node *head, int l)
{
    while(head && l) {
        head = head->next;
        l--;
    }
    if (head != NULL)
        return head->val;
    else
        return -1;
}

void swap(struct node *head, int i, int j)
{
    struct node *tmp = head;
    int tmpival;
    int tmpjval;
    int ti = i;
    while(tmp && i) {
        i--;
        tmp = tmp->next;
    }
    tmpival = tmp->val;
    tmp = head;
    while(tmp && j) {
        j--;
        tmp = tmp->next;
    }
    tmpjval = tmp->val;
    tmp->val = tmpival;
    tmp = head;
    i = ti;
    while(tmp && i) {
        i--;
        tmp = tmp->next;
    }
    tmp->val = tmpjval;
}


struct node *Quick_Sort_List(struct node *head, int l, int r)
{
    int i, j;
    int jval;
    int pivot;
    i = l + 1;
    if (l + 1 < r) {
        pivot = get_lval(head, l);
        printf("Pivot = %d\n", pivot);
        for (j = l + 1; j <= r; j++) {
            jval = get_lval(head, j);
            if (jval < pivot && jval != -1) {
                swap(head, i, j);
                i++;
            }
        }
        swap(head, i - 1, l);
        Quick_Sort_List(head, l, i);
        Quick_Sort_List(head, i, r);
    }
    return head;
}

struct node *Sort_linkedlist(struct node *head)
{
    struct node *tmp = head;
    // Using Quick sort.
    int n = 0;

    while (tmp) {
        n++;
        tmp = tmp->next;
    }
    printf("n = %d\n", n);
    head = Quick_Sort_List(head, 0, n);
    return head;
}

void print_list(struct node *head)
{
    while(head) {
        printf("%d->", head->val);
        head = head->next;
    }
    printf("\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
    struct node *head = NULL;
    struct node *shead = NULL;

    insert_node(&head, 10);
    insert_node(&head, 12);
    insert_node(&head, 9);
    insert_node(&head, 11);
    insert_node(&head, 7);
    insert_node(&head, 1);
    insert_node(&head, 3);
    insert_node(&head, 8);
    insert_node(&head, 5);
    insert_node(&head, 2);
    insert_node(&head, 4);
    insert_node(&head, 6);
    print_list(head);

    shead = Sort_linkedlist(head);
    print_list(shead);

    return 0;
}

BMitch · Accepted Answer · 2011-04-03 00:39:38Z

0

Rather than copy someone else's code that has known issues, I'd suggest making your own. You'll learn a lot more and just might end up with fewer bugs.

That said, if you want to know what it's not working, follow through what happens once the smallest value reaches the head of the list. tmpPtr->value will get set to 1, which gets assigned to a, which ends up skipping the inner while loop.

answered Apr 3, 2011 at 0:39

BMitch

271k52 gold badges555 silver badges511 bronze badges

Collectives™ on Stack Overflow

Linked list sorting in C

5 Answers 5

3 Comments

1 Comment

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

3 Comments

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related