Thread: Quick sorting an array of nodes in a linked list.

Hello, I'm trying to sort the elements in a linked list which contain a variable amount of data in any given case. In the sample code, the code is more static, but I plan on adding it to much more dynamic code once I have it figured out. My main problem is that I am not sure how to sort the linked list while still keeping the correct pointers to the nodes. I thought about writing my own custom quick sort instead of using the C-standard library function, but how I would keep the pointers to the next nodes correct eluded me. I barely have any experience with data structures, so it would be nice if someone who studied this could help me. Here is my code so far :

Code:

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


/* ************************************************************************ */


#define NUMBER_OF_NODES 6


typedef struct linked_list
{
    int x;


    struct linked_list * next;
} linked_list;


/* ************************************************************************ */


linked_list * create( )
{
    linked_list * temp = NULL;


    if ( !( temp = malloc( sizeof( linked_list ) ) ) )
    {
        perror( "Malloc" );
        exit( 1 );
    }


    return temp;
}


/* ************************************************************************ */


linked_list * add( linked_list * head, int x )
{
    linked_list * temp = NULL;


    if ( !head )
    {
        head = create( );


        head->x = x;
        head->next = NULL;
    }
    else
    {
        temp = create( );
        temp->next = head;
        head = temp;


        head->x = x;
    }


    return head;
}


/* ************************************************************************ */


linked_list ** copy_list_to_array( linked_list * head, size_t * size )
{


    linked_list ** list_array = NULL;
    linked_list * p1 = NULL;


    size_t array_size;
    int node_offset;


    for ( array_size = 0, p1 = head; p1; ++array_size, p1 = p1->next );


    list_array = malloc( sizeof( linked_list * ) * array_size );


    for ( node_offset = 0, p1 = head; p1; ++node_offset, p1 = p1->next )
        list_array[node_offset] = p1;


    *size = array_size;


    return list_array;
}


/* ************************************************************************ */


int compare( const void * a, const void * b )
{
    linked_list * p1 = ( linked_list * )a;
    linked_list * p2 = ( linked_list * )b;


    if ( p1->x < p2->x ) return -1;
    if ( p1->x == p2->x ) return 0;
    if ( p1->x > p2->x ) return 1;


    return 0;
}


/* ************************************************************************ */


void print_list( linked_list * head )
{
    linked_list * p1 = NULL;


    for ( p1 = head; p1; p1 = p1->next )
    {
        printf( "Node.x = %d\n", p1->x );
        printf( "---------------------------\n" );
    }
}


/* ************************************************************************ */


void free_list( linked_list * head )
{
    linked_list * p1 = head;
    linked_list * p2 = NULL;


    while ( p1 )
    {
        p2 = p1;
        p1 = p1->next;
        free( p2 );


        p2 = NULL;
    }
}


/* ************************************************************************ */


int main( )
{
    linked_list * head = NULL;
    linked_list ** list_array = NULL;


    size_t array_size;
    int n;


    srand( time( NULL ) );


    for ( n = 0; n < NUMBER_OF_NODES; n++ )
    {
        if ( n )
            head = add( head, rand( ) );
        else
            head = add( head, 0 );
    }


    list_array = copy_list_to_array( head, &array_size );
    qsort( list_array, ( array_size - 1 ), sizeof( linked_list * ), compare );


    print_list( list_array[0] );
    free_list( head );
    free( list_array );


    return 0;
}

Originally Posted by anduril462

I see you're copying the list to an array and sorting that. That works, but it's somewhat inefficient, especially since you run through the list once just to count elements. Consider keeping the count of elements in a variable and incrementing it with every add. Also, you would fix the pointers by doing something like:

Code:

for (i = 0; i < array_size - 1; i++) {
    list_array[i]->next = list_array[i + 1];  // make node's next pointer point to next element in sorted array
}
list_array[i]->next = NULL;  // terminate list

I tried that already, it didn't work. I end up getting this output.

Code:

Node.x = 24114
---------------------------
Node.x = 11576
---------------------------
Node.x = 28600
---------------------------
Node.x = 17589
---------------------------
Node.x = 11959
---------------------------
Node.x = 0
---------------------------

I'm not sure if for some reason the function didn't sort it or if I did something wrong somewhere, but it is obvious that the list is not sorted.

Code:

void re_link_list_array( linked_list ** list_array, size_t array_size )
{
    int n;


    for ( n = 0; n < ( array_size - 1 ); n++ )
        list_array[n]->next = list_array[n + 1];


    return;
}