What does it mean for a sorting algorithm to be stable? Why? Is Selection Sort stable?

Answer:

 

A sorting algorithm is considered stable if it preserves the relative order of items with equal values. This means that if two elements in the list are equal, their order relative to each other remains the same after sorting.

 

For. e.g. in a list of tuples[(Earl,80), (Sebastian, 80),(David,90), (Charlie,70)]  is going to be sorted by the grades of students. Two people in the grades have the same grade 80 – Sebastian and Earl. Earl is at index 0 while Sebastian is at index v3 in the unsorted list – Earl has a lower Index than Sebastian. If the list is sorted by a stable sorting algorithm, to maintain the relative order of all items, Earl would have a lower index than Sebastian in the sorted list. The expected sorted list under a stable sorting algorithm would be:  

 

 

[(Charlie,70), (Earl,80), (Sebastian, 80),(David,90)], (UPDATED EXAMPLE)

 

However, in selection sort, as non-adjacent elements are swapped, the relative order of all items in the output may be disrupted. As such, the expected output from the selection sort algorithm would be: 

 

 

[(Charlie,70), (Sebastian,80), (Earl, 80),(David,90)], (UPDATED EXAMPLE)

 

As the relative order under the selection sort algorithm is not preserved, it is not a stable sorting algorithm.

 

UPDATE: Example has been changed as per feedback

 

 

Alternative Answer#1: 

Bad example, the list of tuples could be [(Earl,80), (Sebastian, 80),(David,90), (Charlie,70)], in this way, non-adjacent elements are swapped. In the original example. It is actually a specific implementation which seems stable.(However, in general selection sort is unstable)

 

 

Alternative Answer#2:

Selection sort is not stable because it may swap non-adjacent elements, causing elements with equal values to be reordered. For example, if there are two identical elements and the algorithm selects one from later in the list to swap with an earlier position, it might end up ahead of an identical element that was originally in front, disrupting their original order.

 

No Comments

Send Comment Edit Comment


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
Previous
Next