Hello everyone =)
I'm having difficulties with one of my assignment questions this week in my Algorithms class. The assignment question states that the Heapsort algorithm isn't a stable sorting algorithm. So, what I have
to do is modify the heapsort algorithm so that it becomes a stable sorting algorithm while maintaning
a worse case running time of O(n*log(n)). The question also states that the idea behind the solution should also work for any sorting algorithm in the comparison model.
I was wondering if anyone had any ideas as to how to approch this problem. I know it would involve keeping track of the original position of each item in an array, however, whatever solution i come up
with doesn't maintain a worse case runetime of O(n*log(n)).
Any ideas?
Thanks in advance =)
Stable Sorting Algorithm
Page 1 of 15 Replies  5463 Views  Last Post: 20 March 2010  09:29 AM
Replies To: Stable Sorting Algorithm
#2
Re: Stable Sorting Algorithm
Posted 28 February 2010  11:08 PM
I am not completely sure but I thought that the worstcase scenario for the heapsort is O(nlogn). If I am correct and you say that your algorithm does not maintain that worst case, my advice would be to take at several resources describing how to implement a heapsort algorithm.
Good luck with trying to solve your problem!
Good luck with trying to solve your problem!
#3
Re: Stable Sorting Algorithm
Posted 28 February 2010  11:24 PM
sparkart, on 28 February 2010  10:08 PM, said:
I am not completely sure but I thought that the worstcase scenario for the heapsort is O(nlogn). If I am correct and you say that your algorithm does not maintain that worst case, my advice would be to take at several resources describing how to implement a heapsort algorithm.
Good luck with trying to solve your problem!
Good luck with trying to solve your problem!
The worst case scenario for the heapsort is O(nlogn)  however, a heapsort algorithm is what's called an
unstable sorting algorithm. What we have to do is turn it into a stable sorting algorithm, WITHOUT changing the worse case runtime. The challenge in makign it stable is that you need to keep track of the original position of each item without losing O(nlogn).
Hope that made things more clear.
Also, I've looked online everywhere and I can't seem to find any help/ideas whatsoever as to how to make the heapsort algorithm stable.
Help would be really appreciated
#4
Re: Stable Sorting Algorithm
Posted 02 March 2010  01:13 PM
An idea would be to let every element be a pair of the value and the values original position, and then use the positions to make decision in case of ties on the values.
This is what comes to mind and it seems like it would work for any comparison sort...
This is what comes to mind and it seems like it would work for any comparison sort...
#5
Re: Stable Sorting Algorithm
Posted 02 March 2010  01:33 PM
Stable means if the two elements have the same key, they remain in the same order or positions.
#6
Re: Stable Sorting Algorithm
Posted 20 March 2010  09:29 AM
Im not usre if this is an answer to your problem, but it's worth checking out.
http://forums.devx.c...hp/t76393.html
http://forums.devx.c...hp/t76393.html
Page 1 of 1
