Stable sorts

And why understanding the language around sorts is important

Sorting is really important in computing; imagine looking through your contacts list on your mobile phone while they do not have any particular order — let me tell you this would be an absolute nightmare.

Image for post
Image for post
Photo by Tim Gouw on Unsplash

Difficulty: Beginner | Easy | Normal | Challenging

Prerequisites:

  • Some awareness of sorting in your target language
  • Selection sort uses linear search, and although this is explained familiarity of it would help

Terminology

Documentation: Written text and/or diagrams that accompany computer software

Sorting: The process of arranging items systematically

Stable sort: A stable sorting algorithm preserves the original order of elements are that are equal when sorted

The issue

Imagine you are told from some documentation that a particular sorting algorithm “… is not guaranteed to be stable”.

You are being told something that is important, but are you aware of what you are being told and why this is vital to your software development journey?

An unstable sort

To understand sorting you need to understand how we are going to represent an array.

Image for post
Image for post

An Unstable sort — Selection Sort

Selection sort, in the following implementation is unstable

Image for post
Image for post

that means the relative order of elements with the same value is not maintained — Quick sort, heap sort and selection sort are three other examples of unstable sort algorithms.

Why would this matter?

The green and yellow above makes it clear that the order can change when we perform an insertion sort.

Frankly this is whenever we are interested in the order of equal elements.

For example, suppose we have a list of first and last names (for example, in a contacts list on a mobile phone)

For an unsorted list

James Dean

Nina McAlroy

Tina Obeng

James King

Ahmed Khan

If you sort by the second name, then the first name we would need the sorts to be stable.

A Stable Sort — Bubble Sort

No matter what initial values you give a Bubble Sort the sort is stable.

That is the relative order of elements with the same value is maintained

Here is a general example of a Bubble Sort

Image for post
Image for post
For brevity, only the first iteration of the bubble sort has been featured

Other Stable sorts are Insertion and Merge sorts.

Changing selection sort to be stable is actually possible — but rather than swapping elements you can insert the smallest element into the front of the list.

Conclusion…

When you have different ways to sort you need to think about which one is most suitable for your needs.

If you are stacking sorts you need to know — is your sorting algorithm stable or unstable. Only by knowing what this means can we make a good decision and select the best algorithm for any situation.

Extend your knowledge

  • There is a full guide on Linear Search (HERE)

Want to get in contact? Try the link here:

https://twitter.com/stevenpcurtis

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store