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 1## 5 Replies - 8316 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 worst-case scenario for the heapsort

Good luck with trying to solve your problem!

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

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

Good luck with trying to solve your problem!

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

## 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/t-76393.html

http://forums.devx.c...hp/t-76393.html

Page 1 of 1