5 Replies - 4914 Views - Last Post: 20 March 2010 - 09:29 AM

#1 Nizbel99  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 6
  • View blog
  • Posts: 117
  • Joined: 19-May 09

Stable Sorting Algorithm

Posted 27 February 2010 - 09:32 PM

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 =)

Is This A Good Question/Topic? 0
  • +

Replies To: Stable Sorting Algorithm

#2 sparkart  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 113
  • View blog
  • Posts: 688
  • Joined: 16-February 09

Re: Stable Sorting Algorithm

Posted 28 February 2010 - 11:08 PM

I am not completely sure but I thought that the worst-case 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!
Was This Post Helpful? 0
  • +
  • -

#3 Nizbel99  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 6
  • View blog
  • Posts: 117
  • Joined: 19-May 09

Re: Stable Sorting Algorithm

Posted 28 February 2010 - 11:24 PM

View Postsparkart, on 28 February 2010 - 10:08 PM, said:

I am not completely sure but I thought that the worst-case 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!



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 :)
Was This Post Helpful? 0
  • +
  • -

#4 LaFayette  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 43
  • View blog
  • Posts: 326
  • Joined: 24-November 08

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...
Was This Post Helpful? 0
  • +
  • -

#5 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2263
  • View blog
  • Posts: 9,467
  • Joined: 29-May 08

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.
Was This Post Helpful? 0
  • +
  • -

#6 IngeniousHax  Icon User is offline

  • |>|20-514<|{3|2

Reputation: 78
  • View blog
  • Posts: 1,358
  • Joined: 28-March 09

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/t-76393.html
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1