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

Answer:

For a sorting algorithm to be stable, it is expected that the relative order of items will remain the same, i.e. when 2 or more items have the same value in an unsorted list, the one which had a lower index in the unsorted list is first.

 

During the insertion process, when an element (pivot) is being compared to the sorted elements of the list, it will only move past elements which are greater than it, not elements which are less than or equal to it. Hence, insertion sort is stable because when 2 or more items have the same value, the relative order of items remains unchanged. 

 

Alternative Answer:

For a sorting algorithm to be stable, it is expected that the relative order of items will remain the same. Insertion sort is stable because of the strict < (Should be >) comparison in the code (elements are only swapped if they are less than the other element, so equal elements are not swapped and the relative order is maintained). Using <= would make it unstable.

No Comments

Send Comment Edit Comment


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