Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Quicksort is described as "in-place" but using an implementation such as:

def sort(array):
    less = []
    equal = []
    greater = []
    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)
        return sort(less) + equal + sort(greater)
    else:
        return array

You have to create a copy of the list for each recursion. By the first return, in memory we have:

  • array
  • greater+equal+less

Then by the second recursion across all sub-lists we have:

  • array
  • greater, equal, less from first recursion
  • greater+equal+less from less1, greater+equal+less from greater1

etc...

Is this just badly written code or am I correct in thinking that for a big list, you actually have to have, proportionally, a fair amount of extra space to store thse?

When I think of something that is "in-place", I think of bubble sort, which simply swaps elements in the list like: http://en.wikipedia.org/wiki/File:Bubble-sort-example-300px.gif

BubbleSort only requires 1 extra variable to store a potentially swapped element.

share|improve this question
1  
I can't tell what you are asking. Would you like to try editing the question to make clearer what your question is? Are you just asking whether it is possible to implement QuickSort in-place? If so, that's a standard question with a standard answer in the usual places -- you haven't done enough research. P.S. Also you might try to be more precise in your wording. For instance, I can't tell what the first sentence is saying (it seems to be missing a verb). In the second sentence, I can't tell who the "You" is. –  D.W. Mar 11 at 23:29
1  
In-place mean you can avoid using external data areas but only use the original array you are sorting. This implementation does not do that. –  Thorbjørn Ravn Andersen Mar 12 at 10:20

2 Answers 2

up vote 19 down vote accepted

This particular implementation of quicksort is not in-place. It treats the data structure as a list that can only grow in one direction (in which case a merge sort would be simpler and faster). However, it is possible to write an in-place implementation of quicksort, and this is the way it is usually presented.

In an in-place implementation, instead the sort function is not called recursively on newly constructed arrays that become smaller and smaller, but on bounds that become closer and closer.

def sort(array, start, end):
    if end >= start: return
    pivot = array[start]
    middle = start + 1
    for i in range(start+1, end):
        if array[i] >= array[middle]:
            tmp = array[i]
            array[i] = array[middle]
            array[middle] = tmp
            middle += 1
    sort(array, start, middle)
    sort(array, middle, end)

(Beware of this code, I have only typed it, not proved it. Any off-by-one errors are yours to fix. Real-world implementations would use a different algorithm for small sizes but this doesn't affect asymptotic behavior. Real-world implementations would choose a better pivot but I won't get into that here as it doesn't really for this question.)

The Wikipedia page presents both a non-in-place and an in-place version of the algorithm.

Quicksort as written here requires $O(d) + s$ extra storage, where $d$ is the depth of the recursion (which depends on the pivot quality) and $s$ is the element size. The stack size requirement can be improved: there are two recursive calls, and we can make the second one a tail call (which consumes no stack). If we always do the recursive call on the smaller half first, then the maximum stack size for array lengths up to $n$ satisfies $\hat S(n) \le \hat S(m)$ with $m \le n/2 \le \hat S(n/2)$, so $\hat S(n) \le \lg_2(n) \hat S(1)$. Thus we can achieve $O(\log n) + s$ extra storage requirement, regardless of the pivot choice.

There are plenty of other sorting algorithms that can be implemented in-place, including insertion sort, selection sort and heap sort. The simple form of merge sort isn't in-place, but there is a more sophisticated variant which is.

Thanks to Aryabhata for pointing out that Quicksort can always be done in $\lg(n)$ stack and that there is a variant of merge sort with both $O(1)$ additional storage and $O(n \log(n))$ runtime.

share|improve this answer
1  
@Gilles: No. Even if the pivot selection algorithm always chose the minimum, we can implement Quicksort to use $O(\log n)$ space. (You might argue that is a variant of quicksort, though). The key is to always recurse on the shorter partition, and tail recurse on the longer one. –  Aryabhata Mar 12 at 19:38
1  
btw, I think in-place mergesort with $O(n \log n)$ has been achieved too. akira.ruc.dk/~keld/teaching/algoritmedesign_f04/Artikler/04/… claims a linear time in-place merge. –  Aryabhata Mar 12 at 19:43
    
@Aryabhata After sleeping on it, now I get it. Thanks for that and for the better in-place merge sort reference. –  Gilles Mar 13 at 13:10
    
You are welcome! –  Aryabhata Mar 13 at 19:16

In addition to Gilles' answer, you can also make Quicksort in-place with your code, if you use linked lists instead of arrays. Just make sure to remove the element from the original list, when appending them to one of the smaller lists.

The following pseudocode assumes/guarantees:

  • The first entry in each list (in the following called the head) does not stare an element and allows to keep pointers to the list intact on modifications. new list creates a list consisting of a head with NIL next-pointer.
  • sort takes a pointer to a head and returns a pointer to the last element of the sorted list. The pointer given as the argument is also the head of the sorted list.
  • The memory location of each element and of the list head remains the same.

.

sort(list):
    less_cur = less = new list
    equal_cur = equal = new list
    greater_cur = greater = new list
    if list.next != NIL:
        cur = list.next
        pivot = cur.value
        while cur != NIL:
            list.next = cur.next
            if cur.value < pivot:
                less_cur.next = cur
                less_cur = less_cur.next
            if cur.value == pivot:
                equal_cur.next = cur
                equal_cur = equal_cur.next
            if cur.value > pivot:
                equal_cur.next = cur
                equal_cur = equal_cur.next
            cur = cur.next
        less_cur.next = greater_cur.next = NIL
        less_last = sort(less) 
        list.next = less.next
        less_last.next = equal
        greater_last = sort(greater)
        equal_cur.next = greater.next
        return greater_last
    else:
        return list

While there is some optimization possible from the above code, this implementation has a greater memory overhead than the array based implementation in Gilles' answer. Additionally it suffers in practice from the problem that linked lists typically are less localized and thus induce a greater number of cache misses than maintaining the same data in an array.

However, this implementation is of advantage, if you have to maintain pointers to the elements through sorting. It is also good to be aware of it, if you are storing your data in a linked list for reasons unrelated to sorting. (If in-place-ness of sorting is of concern, converting between list and array is likely out of question.)

share|improve this answer
    
This considers "in-place" as "not having to copy the elements" but in turn does a lot of work with all the lists pointing to the elements. I would consider the use of all these auxillary data structures (all ending up as garbage needing to be collected) as not being fully "in-place" –  Thorbjørn Ravn Andersen Mar 12 at 13:16
    
@Thorbjørn You can do the removing from the original list and appending to the smaller list by changing 2 pointers (4 for doubly linked lists). I don't see, where this generates garbage. –  FrankW Mar 12 at 13:29
    
Perhaps you should show an implementation of what you suggest to make sure we are discussing the same thing. –  Thorbjørn Ravn Andersen Mar 12 at 13:50
    
@ThorbjørnRavnAndersen One in Common Lisp is the Sheep Trick from The Pitmanual. It's not "in place" since the list node that was the original beginning of the list might not be afterward, but it doesn't require any additional storage. The partitioning destructively modifies the list structure so that the sublists are built from the same list nodes as the original list. Obviously this requires the ability to modify the structure of the list, which some implementations (e.g., Java's List interface) don't provide. –  Joshua Taylor Mar 12 at 14:07
    
@FrankW I don't think it's correct to call this "in place" so much as "without additional storage". A list node at position i before the list is sorted might not be at position i afterward. –  Joshua Taylor Mar 12 at 14:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.