Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I can not see why the heapsort is considered an inplace sorting algorithm.

I mean an extra data structure populated with the elements of the array to be sorted i.e. a heap, is used to assist in the extraction of the min value and the sorting process.

So may be I am misunderstanding the definition of inplace here?

But insertion sort for example it is obvious that it is inplace algorith, i.e. no extra memory needed for the elements.

So why is it considered inplace?

share|improve this question

5 Answers 5

up vote 8 down vote accepted

I mean an extra data structure populated with the elements of the array to be sorted i.e. a heap, is used to assist in the extraction of the min value and the sorting process.

No. The array is transformed to conform to the heap constraint without using more than O(1) extra memory. (In fact all you need is extra memory sufficient to hold one element of the array, for swap purposes, plus a boolean or two and a loop variable or two).

Ok, on a technicality it may be that heapsort is usually explained as using a separate heap, but it's perfectly possible to implement it in-place.

share|improve this answer
    
The only place I'd expect to see "heapsort" with a separate heap (in code) is in a functional language like Haskell, for the same reason that the usual functional "Quicksort" isn't in-place too - functional programmers like their lists a lot, and an in-place sort is stateful - it changes the state of the array/whatever containing the data. Scare-quotes because I don't really accept that an out-of-place quicksort is a quicksort at all, or that an out-of-place heapsort is a heapsort at all - at least not without clearly saying that it's not in-place. –  Steve314 Oct 30 '11 at 5:01
    
@Steve314, I think I've seen some teaching material which says something to the effect of "put it in a heap and then pull the elements out one at a time and put them in an array". But having just checked CLR I can report that they do show an in-place version. –  Peter Taylor Oct 30 '11 at 7:46
    
@PeterTaylor:Yes, the book I was reviewing (Skiena) presented heapsort by building an extra heap. –  user10326 Oct 30 '11 at 8:15

You may be missing the fundamental understanding that an array can be used to specify the layout of a tree.

Suppose you have a binary tree, and an interior node is at index i of the array. Then the array index of the parent and children of that node can be found by:

Parent(i) = floor(i/2)
Left child(i) = 2i
Right child(i) = 2i + 1

See:

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm

Since the heap can be kept and organised entirely in an array, then heapsort can run in-place by moving elements around inside the input array. Indeed, the heap is built and manipulated using the original input array.

share|improve this answer
    
:I know about this.The problems seems to be that the book I am reading presented heapsort using a separate heap.I did not understand or think that this presentation was to make it easier to understand the algorithm (perhaps? not sure why it was presented like that) –  user10326 Oct 30 '11 at 8:13
    
I would highly recommend you purchase the book "Introduction to Algorithms" by Cormen, et al. It clearly answers all algorithm-related questions. If you are serious about a career as a computer scientist or software engineer, then you need to have this book. –  stackoverflowuser2010 Oct 30 '11 at 17:55

If, as you say, one really needed an extra structure to build the heap then heapsort would indeed NOT be an inplace sorting algorithm.

However, this is not the case. You can build the heap on the very same array you wanna sort, and after that you apply the heapsort algorithm, so it sorts inplace.

share|improve this answer
    
Basically, there's a "heapify" algorithm which is used to re-order data in an array so that it complies with the rules of a heap in IIRC O(n) time. See the pseudocode on programmers.stackexchange.com/questions/116904/…. After then, it's mostly a matter of doing repeated heap root-extracts and keeping track of how much of the array is still "heap" and how much is sorted end-result. –  Steve314 Oct 30 '11 at 5:10

In computer science, an in-place algorithm (or in Latin in situ) is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes. An algorithm which is not in-place is sometimes called not-in-place or out-of-place.

Wikipedia - In-place algorithm

share|improve this answer
    
So why mergesort is considered an not-in-place algorithm then? –  user10326 Oct 29 '11 at 21:35
3  
This is not a useful reply. It has nothing to do with heapsort and does not answer the question. –  stackoverflowuser2010 Oct 30 '11 at 4:51
    
Of course it has something to do with heapsort. Heapsort is an in-place sort algorithm, as should be clear from the definition. In fact, it was linked from the heapsort page. –  Rein Henrichs Oct 31 '11 at 8:32

It is considered in place because it's space requirements are negligible (constant or none at all if you're using bitwise operations to swap items). MergeSort, for example, is not in place because the input set is not modified in each iteration of the search example.

The best way to illustrate the differences between in-place algorithms and out-of-place algorithms is probably to look at the following C/C++ string reversal code that does it in place (from K&R):

void reverse(char s[])
{
      int c, i, j;

      for (i = 0, j = strlen(s)-1; i < j; i++, j--) {
         c = s[i];
         s[i] = s[j];
         s[j] = c;
      }
}

If you were, for example, reading the input string from the end and placing the characters in another buffer, it would be an out-of place string reversal algorithm.

share|improve this answer
1  
Mergesort is damned annoying - it's easy to wrongly convince yourself that you have an in-place strategy. Usually, it only works for small arrays. However, I think I downloaded a paper once where someone did work out an in-place variant of the merge-sort algorithm. I'll see if I can find it again. –  Steve314 Oct 30 '11 at 5:25

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.