Thread: Quick sort using linked list

  1. #1
    Registered User
    Join Date
    Feb 2013
    Posts
    1

    Quick sort using linked list

    Hey everyone!
    I've been trying to implement a quick sort algorithm for linked list but when i try to run it with 1000000 values my compiler tells me its running too long and ends up not finishing. However when i run it with 10 values it seems to work fine.
    Is there anyway to improve this run time?

    Code:
    struct listnode *quicksort( struct listnode *data ) {
       size_t length = 0;
       struct listnode *pivNode, *temp = NULL, *low = NULL, *high = NULL, *ltail = NULL, *htail = NULL, *prev = NULL, *end = NULL, *next;
    
       // Get length
       for( struct listnode *cursor = data; cursor != NULL; cursor = cursor->next ) {
          length++;
       }
    
       // Base case
       if( length <= 1 ) { return data; }
    
       // Get and remove pivot from data
       pivNode = data;
       for( int i = 0; i < rand()%length; i++ ) {
          pivNode = pivNode->next;
       }
    
       for( struct listnode *cursor = data; cursor != NULL; cursor = cursor->next ) {
          if( cursor == pivNode ) {
             if( prev == NULL ){
                data = data->next;
             }
             else {
                prev->next = cursor->next;
             }
             break;
          }
          else {
             prev = cursor;
          }
       }
    
       // Split into low and high
       for( struct listnode *cursor = data; cursor != NULL; cursor = cursor->next ) {
          temp = new struct listnode;
          temp->value = cursor->value;
          temp->next = NULL;
          if( cursor->value < pivNode->value ) {
             if( ltail == NULL ) {
                low = temp;
                ltail = temp;
             }
             else {
                ltail->next = temp;
                ltail = ltail->next;
             }
          }
          else {
             if( htail == NULL ) {
                high = temp;
                htail = temp;
             }
             else {
                htail->next = temp;
                htail = htail->next;
             }
          }
       }
       
       low = quicksort( low );
       high = quicksort( high );
    
    if(low != NULL){
          pivNode->next = high;
          for( struct listnode *cursor = low; cursor != NULL; cursor = cursor->next) {
            if( cursor->next == NULL ) {
              cursor->next = pivNode;
              break;
            }
          }
          return low;   
      }
      else {
         pivNode->next = high;       
         return pivNode;   
      }

  2. #2
    Registered User
    Join Date
    Mar 2010
    Posts
    583
    What do you mean "my compiler tells me its running too long"? That's not the usual job of the compiler. Perhaps you mean you're running it in an IDE and that's giving you a message?

    What does the memory consumption look like as the program runs? From looking at the code I would guess that it's going slowly because it's eating memory.

    Where you partition the list into low and high:
    Code:
       // Split into low and high
       for( struct listnode *cursor = data; cursor != NULL; cursor = cursor->next ) {
          temp = new struct listnode;
          temp->value = cursor->value;
    So - if I'm reading this right, you're creating a new node "temp" for every node, and then building yourself new linked lists by linking the temps together. Is there some way you could do this without creating new nodes? It seems like this will consume a lot of memory. It should be possible to construct the new lists in place out of existing nodes. I guess this'll be a bit trickier, and "trickier" probably means more code and more processing. So you should probably check and see if it is memory that is the problem, or if it's sheer runtime.

    If it's just runtime, you might see if you can avoid looping over the whole linked list so many times. Do you really need to loop over the whole lot to count the length every time? Could you not pass that as an argument, having calculated it when you constructed the high/low partitions? Similarely with the pivot node -- you have one loop to identify it and another loop to remove it. Could they be merged into one?

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Code:
    for( int i = 0; i < rand()%length; i++ )
    The rand()%length is evaluated each time through the loop, resulting in a different random number each time. This does not give you an equal chance of selecting each item as the pivot.
    Not that it matters a lot of course, since the algorithm will run correctly with any pivot. But you should probably still fix it.

    Other than that it looks okay until line 36. Why are you allocating anything at all? It should be a simple matter of popping an item from the original list, and then pushing it onto one of two other lists.
    You don't bennfit at all from keeping track of the tails of lists anywhere. The only thing that could help with would be the concatenation of the sorted lists and the pivot afterwards, but you are simply walking through the list again for that.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 11
    Last Post: 02-20-2012, 10:38 PM
  2. sort linked list
    By johnhuge in forum C Programming
    Replies: 12
    Last Post: 10-06-2011, 12:47 AM
  3. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  4. sort linked list using BST
    By Micko in forum C Programming
    Replies: 8
    Last Post: 10-04-2004, 02:04 PM
  5. sort a linked list ???
    By goran in forum C Programming
    Replies: 2
    Last Post: 11-13-2001, 08:18 AM