Thread: linked list sorting..

  1. #1
    Registered User
    Join Date
    Apr 2007
    Posts
    8

    linked list sorting..

    well i have some kind of problem... the goal is to developt a algorithm to sort a linked list (single or double linked).. that uses the less memory possible.. we can use for exemple auxiliar lists with pointers to the real registers instead of the real lists.. thats an example..
    so i dont know if i'll use single or double linked lists... neither the best algorithm..
    sorry for the english xD

    peace

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Well, basically, you can use any sort that you could use to sort an ordinary array of numbers: http://en.wikipedia.org/wiki/Sorting_algorithm

    You probably want to use a sorting algorithm that doesn't require random access to the sorting elements; bubble sort, insertion sort, and selection sort would probably be workable.

    As for whether you need a single-linked list or a double one, that's your decision. You probably want to avoid sorts like the Shaker sort that practically require double-linked lists.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Come up up with a way to merge two already-sorted linked lists into a single sorted linked list. This can be done in constant space by pointer swapping, and doesn't require a doubly-linked list. Once you have that you can mergesort. This requires you to walk down the list to divide it roughly in half each time, but it's an option.

  4. #4
    Registered User
    Join Date
    Apr 2007
    Posts
    141
    Quote Originally Posted by brewbuck View Post
    Come up up with a way to merge two already-sorted linked lists into a single sorted linked list. This can be done in constant space by pointer swapping, and doesn't require a doubly-linked list. Once you have that you can mergesort. This requires you to walk down the list to divide it roughly in half each time, but it's an option.
    Yeah I think you're right. Basically you can still do a kind of quick sort. Pick the first node as the pivot. Traverse through the linked list and append all nodes less than the pivot on the left side (the head of the linked list), whilst all nodes greater than the pivot would be inserted to the front of the list to the right of the pivot. You now have two linked lists left and right.
    Pointers to mark the beginning and end of each list can be retained. Rinse and repeat the process for each list and each sublist etc., and you're done.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by SevenThunders View Post
    Yeah I think you're right. Basically you can still do a kind of quick sort. Pick the first node as the pivot. Traverse through the linked list and append all nodes less than the pivot on the left side (the head of the linked list), whilst all nodes greater than the pivot would be inserted to the front of the list to the right of the pivot. You now have two linked lists left and right.
    Pointers to mark the beginning and end of each list can be retained. Rinse and repeat the process for each list and each sublist etc., and you're done.
    Rinse and repeat amounts to: recursive calls or an explicit stack. Sure, that may be fine, but it may be that using the least memory possible includes using stack space. Especially since in this case it can amount to O(n) stack space.

    dwks' ideas were actually quite sensible, provided an O(n*n) algorithm will suffice.

    Otherwise, natural-merge-sort should use only O(1) extra memory and is doable with lists. For the same reasons also consider comb-sort, strand-sort, bingo-sort, odd-even-transposition-sort (a.k.a brick-sort), and possibly even bozo-sort.

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > that uses the less memory possible
    Well if you can stand to allocate 1 pointer for every element in the list, I would
    - allocate an array of 'n' pointers
    - set each pointer to point to each successive element of the list
    - qsort on the array
    - reconstruct the linked list from the sorted array
    - free the array of pointers.
    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.

  7. #7
    Registered User
    Join Date
    Apr 2007
    Posts
    8
    Quote Originally Posted by Salem View Post
    > that uses the less memory possible
    Well if you can stand to allocate 1 pointer for every element in the list, I would
    - allocate an array of 'n' pointers
    - set each pointer to point to each successive element of the list
    - qsort on the array
    - reconstruct the linked list from the sorted array
    - free the array of pointers.
    well.. thats probably the point xP.. but how can i sort the list using an array of pointers? i should look in the list and then change in the array?

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Well do you have something to count the number of nodes in the list?

    Code:
    while ( node ) { arr[i++] = node ; node = node->next; }
    Then sort it - easy

    Code:
    head = arr[0]; for( i = 0 ; i < len-1 ; i++ ) { arr[i]->next = arr[i+1]; } arr[i]->next = NULL;
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  2. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 07:47 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM