Thread: Sort strings in double linked list. (Optimize code)

  1. #1
    Registered User
    Join Date
    Nov 2004
    Posts
    20

    Sort strings in double linked list. (Optimize code)

    I have a struct with different members and the ones I want to sort is int and string. The sorting will only affect one member of the struct and the hole linked list. As it is now I have one sorting function for every variable and I want one sorting function for all the variables. The difference in code are minimal but I can't seem to figure out how to only have one sorting function.

    The only difference between the functions are the highlighted variable.

    Ex function 1.

    Code:
    void sortDiscID(sCdPost *CdRoot) 
    {
        sCdPost *current;
        bool swap = true;
        
        current = CdRoot;
    
        if (current->pNext)
             current = current->pNext;
        
        while (swap || current->pNext != CdRoot)
        {
             swap = false; 
             while (current->pNext != CdRoot)
             {
                  if (current->discID > current->pNext->discID)
                  {
                       current->pPrev->pNext = current->pNext;
                       current->pNext->pNext->pPrev = current;
                       current->pNext->pPrev = current->pPrev;
                       current->pPrev = current->pNext;
                       current->pNext = current->pNext->pNext;
                       current = current->pPrev;               
                       current->pNext = current->pNext->pPrev;
                       
                       swap = true;
                  }
                  current = current->pNext;
             }
             if (swap)
                  current = CdRoot->pNext;
        }    
    }//sortDiscID

  2. #2
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    What you do is to use the same sorting function but create seperate compare functions.

  3. #3
    Registered User
    Join Date
    Nov 2004
    Posts
    20
    Ok so this is what you recommend? (Awful lot of function calls if you got a long list.)

    Code:
    int compare(sCdPost *current, int sel)
    {
             if (sel == 1)
                  return current->discID > current->pNext->discID;
             ...
    }
    
    ...
    
    while (current->pNext != CdRoot)
             {
                  if (compare(current, sel))
                  {
                       current->pPrev->pNext = current->pNext;

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Unless the list is almost sorted already (say you want to add an element to the correct place in an already sorted list), the quickest way is probably to turn it into an array, sort it using qsort() and then relink it as a double-linked list.

    An array of pointers, each one pointing at a node in the list would be my approach.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Nov 2004
    Posts
    20
    That's really clever. But I guess it's a bit to sophisticated for my little Cd database. But in a larger list it's definitely worth looking at. For the moment I'll implement the code in my previous post. Atleast it removes some unnecessary code.

    Thanks for the great ideas.

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Why don't you save yourself the trouble, and sort it as you insert it?

    1) Place first node.
    2) Place next node in order.
    3) Repeat step 2 until done.

    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    Nov 2004
    Posts
    20
    I do sort it when I input new Cd:s. But as I said in my first post I would also like to sort my list by any variabel in the struct (Artist etc.). And if my list is sorted by Artist the discID won't be in order any longer. This poses a problem when I want to insert new Cd:s. Therefore I have to call the sorting function and sort by discID before entering addCd function. This might not be the only solution or best solution but it's how it's being done at the moment.

  8. #8
    Registered User
    Join Date
    Nov 2004
    Posts
    20
    I really liked Salems idea so I decided to give it a try. I think I understand it in theory but it doesn't work very well when I try to implement it.
    Here are some code hopefully someone can correct me were I have failed.

    Code:
    int compare(const void *prim, const void *sec)
    {
        sCdPost *p_prim = (sCdPost *)prim;
        sCdPost *p_sec = (sCdPost *)sec;
        
        cout << p_prim << " : " << p_sec << endl;
        cout << p_prim->discID << " : " << p_sec->discID;
        
        return 0;
    }//compare
    
    void sortAlgorithm(sCdPost *CdRoot) 
    {
        sCdPost *current, **temporary;
        int i = 0, j = 0;
        
        current = CdRoot;
        
        current = current->pNext;
        
        i = CdRoot->pPrev->discID;
        temporary = new sCdPost *[i];
        
        while (current != CdRoot)
        {
             temporary[j] = current; 
             j++;
             current = current->pNext;
        }
       cout << &temporary[0] << " : " << &temporary[1] << endl;
       cout << temporary[0]->discID << " : " << temporary[1]->discID << endl; 
       
       qsort ((void **)temporary, i, sizeof(sCdPost), compare);
       
       for (j=0; j < i; j++)
       {
             cout << temporary[j]->discID << endl;
             cout << temporary[j]->title << endl;
       }
       delete[] temporary;
    }//sortAlgorithm
    Since it doesn't work I have removed some code. What I want is the same output from compare() and sortAlgorithm(). (I only have two posts in the list at the moment.)

    Output:
    <sortAlgorithm()>
    Adress> 0x3d3cd0 : 0x3d3cd4
    discID> 1 : 2
    <compare()>
    Adress> 0x3d3cd4 : 0x3d3cd0
    discID> 4018064 : 4013888

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Example
    Code:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    typedef struct info {
        char         name[20];
        struct info *next;
    } info;
    
    /* List Functions */
    /* -------------- */
    info *newnode ( void ) {
        info *new = malloc( sizeof *new );
        if ( new ) {
            new->next = NULL;
        }
        return new;
    }
    
    info *list_prepend ( info *head, char *name ) {
        info *new = newnode( );
        if ( new ) {
            new->next = head;
            strcpy( new->name, name );
        }
        return new;
    }
    
    void list_print ( info *head ) {
        while ( head ) {
            printf( "%s\n", head->name );
            head = head->next;
        }
    }
    
    int list_count ( info *head ) {
        int result = 0;
        while ( head ) {
            result++;
            head = head->next;
        }
        return result;
    }
    
    
    int compare ( const void *a, const void *b ) {
        info * const *pa = a;
        info * const *pb = b;
        return strcmp( (*pa)->name, (*pb)->name );
    }
    
    info *list_sort ( info *head ) {
        int i, n;
        info **array;
    
        /* create array out of a list */
        n = list_count( head );
        array = malloc( n * sizeof *array );
        for ( i = 0 ; i < n ; i++ ) {
            array[i] = head;
            head = head->next;
        }
    
        /* sort it */
        qsort( array, n, sizeof(array[0]), compare );
    
        /* create list out of array */
        for ( i = 0 ; i < n-1 ; i++ ) {
            array[i]->next = array[i+1];
        }
        array[n-1]->next = NULL;
        head = array[0];
    
        free( array );
        return head;
    }
    
    int main ( ) {
        info *list = NULL;
        char *names[] = { "now", "is", "the", "time", "for", "all", "to", "party" };
        int i;
    
        /* create a list */
        for ( i = 0 ; i < sizeof(names)/sizeof(names[0]) ; i++ ) {
            list = list_prepend( list, names[i] );
        }
    
        printf( "Unsorted\n" );
        list_print( list );
    
        printf( "\nsorted\n" );
        list = list_sort( list );
        list_print( list );
        return 0;
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  10. #10
    Registered User
    Join Date
    Nov 2004
    Posts
    20
    Thanks!

    Nice program you made there. But I have no problem with my program, I have a problem with qsort though. When you are in the compare() function wouldn't it be possible to output the strings that are being compared? You can try that with the code you posted.

    Code:
    int compare ( const void *a, const void *b ) {
        info * const *pa = a;
        info * const *pb = b;
        printf("OUTPUT: %s", pa->name);
        return strcmp( (*pa)->name, (*pb)->name );
    }
    Why does printf() output the way it does?

    It works with your program when you have pre defined arrays but what if you turn your program into c++ and use strings. It will most certainly crash. That was my point in my previous post. Since you can't use your variables when you are in the compare() function how would you then convert your strings to const char *?

    Should the sorting really look like this, or have I missed something?

    [Sorted]
    for
    all
    to
    party
    now
    is
    the
    time

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    If you insist on using printf and the string class:
    Code:
    printf("OUTPUT: %s\n", yourstring.c_str() );
    Quzah.
    Hope is the first step on the road to disappointment.

  12. #12
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > Why does printf() output the way it does?
    Probably because pa->name != (*pa)->name

    > It works with your program when you have pre defined arrays
    The array in main has nothing to do with it. You can replace it with something which reads a file if you want to. It's merely there to allow the list to be quickly initialised.

    > Since you can't use your variables when you are in the compare() function
    Of course you can. So long as it returns some suitable answer which is the result of comparing 'a' and 'b' parameters, that's all that matters.

    My output is
    Code:
    Unsorted
    party
    to
    all
    for
    time
    the
    is
    now
    
    sorted
    all
    for
    is
    now
    party
    the
    time
    to
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  13. #13
    Registered User
    Join Date
    Nov 2004
    Posts
    20
    quzah>> I'm aware of that but pa->name is not a c++ string.

    salem>> Ok, things are getting freaky. You know aswell as I do that your previous posted code does not compile without fixing it. The compare() function compares the elements in your info **array therefore your conversion "info * const *pa = a" is not valid. Because a is of type void *. And if you should assign an element in **array to a new pointer it should be an "const info *pa". This is were I get stuck. The address an element in **array points to is valid before entering compare(). When I'm in compare() the element points at something else. So who's right gcc v.3.3.5 and dev-c++ v.4.9.9.1 or you salem?

    I would appreciate if you could post a compare() function that works on the above compilers.

    This compare() function compiles but don't deliver the right result.
    Code:
    int compare ( const void *a, const void *b ) {
        const info *pa = (info *)a;
        const info *pb = (info *)b;
        return strcmp( pa->name, pb->name );
    }
    PS.
    And please don't use "new" as a variable in a c++ forum.

  14. #14
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > You know aswell as I do that your previous posted code does not compile without fixing it.
    shrug
    Code:
    $ gcc -W -Wall hello.c
    $ gcc -v
    Reading specs from /usr/lib/gcc-lib/i386-redhat-linux/3.2/specs
    Configured with: ../configure --prefix=/usr --mandir=/usr/share/man
     --infodir=/usr/share/info --enable-shared --enable-threads=posix --disable-checking
     --host=i386-redhat-linux --with-system-zlib --enable-__cxa_atexit
    Thread model: posix
    gcc version 3.2 20020903 (Red Hat Linux 8.0 3.2-7)
    Well yes it's true that it's unlikely to compile as C++, simply because C++ doesn't allow uncast void* expressions.

    In C++, I get these errors
    Code:
    g++ -W -Wall hello.cpp
    hello.cpp: In function `info* newnode()':
    hello.cpp:14: invalid conversion from `void*' to `info*'
    hello.cpp: In function `int compare(const void*, const void*)':
    hello.cpp:48: invalid conversion from `const void*' to `info* const*'
    hello.cpp:49: invalid conversion from `const void*' to `info* const*'
    hello.cpp: In function `info* list_sort(info*)':
    hello.cpp:59: invalid conversion from `void*' to `info**'
    > This compare() function compiles but don't deliver the right result.
    That's because you cast to the wrong type.

    If you have an array of T, then the compare function is really
    int compare ( T *a, T *b );
    But since the compare function is written for qsort, the parameters appear as void*, and need to be cast into T* before use.

    Now in this case, the array is an array of info*, so the pointers the compare function gets are really info**
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  15. #15
    Registered User
    Join Date
    Aug 2001
    Posts
    244
    also c style casts ( that is "(type)expression") should be avoided in c++.
    there is static_cast and dynamic_cast.

    in some situations youll need reinterpret_cast.
    and i havent ever needed const_cast yet.
    signature under construction

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  2. Need some help...
    By darkconvoy in forum C Programming
    Replies: 32
    Last Post: 04-29-2008, 03:33 PM
  3. how do i reverse a circular double linked list
    By kobra_swe in forum C Programming
    Replies: 13
    Last Post: 04-08-2008, 04:20 PM
  4. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 08:38 PM
  5. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM