# Stable Sorting Algorithm

Page 1 of 1

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

### #1 Nizbel99

Reputation: 6
• 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?

Is This A Good Question/Topic? 0

## Replies To: Stable Sorting Algorithm

### #2 sparkart

Reputation: 114
• Posts: 692
• 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!

### #3 Nizbel99

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

## 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 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

### #4 LaFayette

• D.I.C Regular

Reputation: 43
• 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...

• MrCupOfT

Reputation: 2292
• Posts: 9,531
• 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.

### #6 IngeniousHax

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

Reputation: 83
• Posts: 1,378
• 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