heapsort

[vsgdp]

Hi,

I have a couple of questions. What is meant by "running time"? Is that big O notation?

I need to find the running time of heapsort on an array of n elements that is already sorted in increasing order.

Is this a trick question? I did an example, 1, 2, 3, 4, 5, 6, 7, 8, 9 as my dataset.

Even though it is sorted, you will still need to heapify the data (max heapify), and Heapify is O(n log2 n). Then each type you extract the max item, you need to correct the heap.

So it still stays O(n log2 n). That's why I'm wondering if my understanding of what "running time" means is off.

[Chris Gunter]

i think ur calculation might mistake somewhere a long teh 'road', please check it up in basic textbooks i am sure you have them in hands.

Good luck with yoru homework
Have a nice day by teh way

[Smasher/Devourer]

Yes, running time is typically understood to mean complexity (big-O notation), and yes, if I recall correctly, I'm pretty sure that a heap sort still requires O(n log n) even if operating on a perfectly sorted array. I wouldn't say that it's a "trick question" exactly. There are several sorting algorithms whose best-case complexity is the same as that for the average case. The point of the question is probably just to get you to take a closer look at the algorithm and make sure you understand how it works. And it sounds like you do.

[mehdi62b]

in heapsort algorithm,
its first step is making a valid (max)heap..in your case this step takes the maximum time.

[cma]

The first step of constructing the heap can be done in linear time. The second operation of putting the elements in place would take O(n*log(n)).

Keep this in mind about sorting algorithms and comparisons: The best running-time that any comparison-based sorting algorithm can do is O(n*log(n)).

[Smasher/Devourer]

Keep this in mind about sorting algorithms and comparisons: The best running-time that any comparison-based sorting algorithm can do is O(n*log(n)).

That is true when you're talking about the average complexity for such an algorithm, but it's not true when we're talking about best-case complexity as in the original post. An insertion sort, for example, has a best-case (i.e. when operating on a data set that's already sorted) complexity of O(n), even though it typically takes O(n²).

[mehdi62b]

Selection Sort: it has typically O(n^2) because of two nested loop cycles so its if condition is executed anyway regardless of the sorting statue

Insertion Sort:

• if the array is sorted increasingly it has the best time which is O(n)
• if the array is sorted decreasingly it has the worst time which is O(n^2)

[cma]

An insertion sort, for example, has a best-case (i.e. when operating on a data set that's already sorted) complexity of O(n), even though it typically takes O(n²).

This would depend on the implementation, if you do a linear seach going towards the first element to find the insertion point, then yes, if you do a binary search, then no.