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
- Some awareness of sorting in your target language
- Selection sort uses linear search, and although this is explained familiarity of it would help
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
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
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
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.
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.
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: