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

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.

## An Unstable sort — Selection Sort

Selection sort, in the following implementation is unstable

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

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.

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

Want to get in contact? Try the link here:

Written by