# How do I know if a certain sorting algorithm is stable?

Page 1 of 1

## 7 Replies - 1245 Views - Last Post: 24 August 2016 - 06:18 PM

### #1 jsvillatech

Reputation: 4
• Posts: 17
• Joined: 14-March 15

# How do I know if a certain sorting algorithm is stable?

Posted 22 August 2016 - 09:21 AM

Hello, I was given a bunch of algorithms to analyze and determine if they are stable or not.
I know that that an algorithm is stable if two objects with equal keys appear in the same order in sorted output as they appear in the input unsorted array.
But I don't know how to determine that when it comes to code. what criteria should I use?

Thanks
Is This A Good Question/Topic? 0

## Replies To: How do I know if a certain sorting algorithm is stable?

### #2 jon.kiparsky

• Beginner

Reputation: 11095
• Posts: 18,982
• Joined: 19-March 11

## Re: How do I know if a certain sorting algorithm is stable?

Posted 22 August 2016 - 01:02 PM

Interesting question. I think I'm going to move it to Computer Science, since it's not language-specific.

### #3 jon.kiparsky

• Beginner

Reputation: 11095
• Posts: 18,982
• Joined: 19-March 11

## Re: How do I know if a certain sorting algorithm is stable?

Posted 22 August 2016 - 01:08 PM

So let's start by thinking this through. What would have to be true about a sorting algorithm for it to be stable? Or, thinking about it from the other end, what characteristics or behaviors would you look for to see if an algorithm is not stable?

### #4 jsvillatech

Reputation: 4
• Posts: 17
• Joined: 14-March 15

## Re: How do I know if a certain sorting algorithm is stable?

Posted 22 August 2016 - 05:22 PM

jon.kiparsky, on 22 August 2016 - 01:08 PM, said:

So let's start by thinking this through. What would have to be true about a sorting algorithm for it to be stable? Or, thinking about it from the other end, what characteristics or behaviors would you look for to see if an algorithm is not stable?

Thanks for answering . What I understand about an algorithm in order to be stable is, for example, we have a deck of cards and if there are elements that are equal, the algorithm respects the order. but what I don't really understand is when we have an int array and there is a sequence of numbers 2 4 3 5 3 3. how do I know if those 3 swapped positions?

### #5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12324
• Posts: 45,424
• Joined: 27-December 08

## Re: How do I know if a certain sorting algorithm is stable?

Posted 22 August 2016 - 05:42 PM

Let's take insertion sort for example. And consider your sequence 2 4 3 5 3 3. Now we label each 3 for our purposes, just to keep track of them (the algorithms do no such thing, but we do for the sake of the proof- and this is a good proof strategy for proving a sorting algorithm is stable): 2 4 3A 5 3B 3C.

By hand, use insertion sort on this example. Keep track of each instance of 3. What happens when you hit 3B? Do you ever move it before 3A? Justify using the steps of the algorithm.

From this example, try to generalize for an arbitrary array.

### #6 jon.kiparsky

• Beginner

Reputation: 11095
• Posts: 18,982
• Joined: 19-March 11

## Re: How do I know if a certain sorting algorithm is stable?

Posted 23 August 2016 - 09:25 AM

jsvillatech, on 22 August 2016 - 07:22 PM, said:

Thanks for answering />. What I understand about an algorithm in order to be stable is, for example, we have a deck of cards and if there are elements that are equal, the algorithm respects the order. but what I don't really understand is when we have an int array and there is a sequence of numbers 2 4 3 5 3 3. how do I know if those 3 swapped positions?

That's something that's true about the result - if the algorithm is stable, then the result has certain qualities, specifically, order is preserved for identically-sorting elements. What you want to ask yourself is, what has to be true about the algorithm for this to be the case, in general?

So for example, let's imagine an algorithm called RandomSort. This operates by pulling a randomly-selected element e from the list to be sorted (removing it from the list) and walking up a list of sorted output until it reaches an element which sorts after or equal to e. e is inserted before that element.

Leaving any concerns about the complexity of this algorithm (you might enjoy thinking about why it sucks, but that's another question), I think it's pretty clear that RandomSort is NOT stable. Why? What does it do that makes it clearly not stable?

### #7 jsvillatech

Reputation: 4
• Posts: 17
• Joined: 14-March 15

## Re: How do I know if a certain sorting algorithm is stable?

Posted 23 August 2016 - 03:53 PM

jon.kiparsky, on 23 August 2016 - 09:25 AM, said:

jsvillatech, on 22 August 2016 - 07:22 PM, said:

Thanks for answering />/>. What I understand about an algorithm in order to be stable is, for example, we have a deck of cards and if there are elements that are equal, the algorithm respects the order. but what I don't really understand is when we have an int array and there is a sequence of numbers 2 4 3 5 3 3. how do I know if those 3 swapped positions?

That's something that's true about the result - if the algorithm is stable, then the result has certain qualities, specifically, order is preserved for identically-sorting elements. What you want to ask yourself is, what has to be true about the algorithm for this to be the case, in general?

So for example, let's imagine an algorithm called RandomSort. This operates by pulling a randomly-selected element e from the list to be sorted (removing it from the list) and walking up a list of sorted output until it reaches an element which sorts after or equal to e. e is inserted before that element.

Leaving any concerns about the complexity of this algorithm (you might enjoy thinking about why it sucks, but that's another question), I think it's pretty clear that RandomSort is NOT stable. Why? What does it do that makes it clearly not stable?

Now I understand thank you! yeah random sort doesn't respect the order at all. while bubble and others do that

macosxnerd101, on 22 August 2016 - 05:42 PM, said:

Let's take insertion sort for example. And consider your sequence 2 4 3 5 3 3. Now we label each 3 for our purposes, just to keep track of them (the algorithms do no such thing, but we do for the sake of the proof- and this is a good proof strategy for proving a sorting algorithm is stable): 2 4 3A 5 3B 3C.

By hand, use insertion sort on this example. Keep track of each instance of 3. What happens when you hit 3B? Do you ever move it before 3A? Justify using the steps of the algorithm.

From this example, try to generalize for an arbitrary array.

Thank you so much, that was really helpful, now I understand the concept

### #8 ishkabible

• spelling expret

Reputation: 1747
• Posts: 5,898
• Joined: 03-August 09

## Re: How do I know if a certain sorting algorithm is stable?

Posted 24 August 2016 - 06:18 PM