1

I have a singly linked list and I need to sort it in constant space due to memory limitations (in other words, no extra space should be used that is proportional to the number of items in the list).

The structure of the linked list is:

  • head.item = the payload you want to sort on; and
  • head.next = the next item.

The requirement for constant space discounts solutions where I build another list, I need to do it in-place.

How can I do that?

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
Thunderboltz
  • 1,597
  • 3
  • 14
  • 16
  • 3
    at least make an effort to ask a proper question! – Mitch Wheat May 09 '09 at 00:50
  • am sorry but the question does not seem to be formatted properly – Thunderboltz May 09 '09 at 00:55
  • 1
    If you gave some code as to what you are trying to do and ask why it isn't working that may be better, rather than asking people to give you the answer. – James Black May 09 '09 at 01:13
  • sorted in constant space? what does that mean? (really I don't understand what that means...because only constant thing that may apply to algorithm is O(1)). – codingbear May 09 '09 at 01:16
  • What about std::slist http://www.sgi.com/tech/stl/Slist.html – Martin York May 09 '09 at 05:18
  • As this is obviously homework I would recommend: You should know how to swap two elements of you list. Then pick a [Sorting Algorithm](http://en.wikipedia.org/wiki/Sorting_Algorithm) and implement it. – lothar May 09 '09 at 01:09

3 Answers3

11

Sorting a linked list in constant space is easy, you just have to adjust the pointers. The easiest way to do this is to use a sort algorithm that only swaps adjacent elements. I'm going to provide a bubble-sort, just because you've made no requirement for efficiency:

# Enter loop only if there are elements in list.

swapped = (head <> null)
while swapped:
    # Only continue loop if a swap is made.

    swapped = false

    # Maintain pointers.

    curr = head
    next = curr.next
    prev = null

    # Cannot swap last element with its next.

    while next <> null:
        # Swap if items in wrong order.

        if curr.item > next.item:
            # Notify loop to do one more pass.

            swapped = true

            # Swap elements (swapping head is special case).

            if curr == head:
                head = next
                temp = next.next
                next.next = curr
                curr.next = temp
                curr = head
            else:
                prev.next = curr.next
                curr.next = next.next
                next.next = curr
                curr = next
            endif
        endif

        # Move to next element.

        prev = curr
        curr = curr.next
        next = curr.next
    endwhile
endwhile
paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
1

For in-place sorting of a linked list, I would suggest merge sort. It's stable, and runs in NlgN time.

supercat
  • 77,689
  • 9
  • 166
  • 211
0

A few methods:

  • use bubble sort on the list in place, this should be fast enough if the list is small
  • copy the list to an array and use heapsort or quicksort then copy it back
  • use bogosort on the list in place. The best case complexity is O(n) so it should be really fast*

*note that the expected runtime complexity is O(n*n!)

1800 INFORMATION
  • 131,367
  • 29
  • 160
  • 239