DestroyerDust DestroyerDust - 4 months ago 25
C Question

Linked list sorting in C

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

Answer

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
}