# Important Algorithm Concepts | Algorithm Stability, In-place Algorithms, and Comparison Algorithms

-14 June 2021

In this article, we will discuss some important properties of algorithms that can help you to decide which algorithm is best suited to the job.

• Algorithm stability
• In-place and out-of-place algorithms
• Comparison and non-comparison sorts

Donâ€™t worry if youâ€™ve never heard these terms before, Iâ€™ll explain them fully as we go.

Disclosure: Iâ€™m always looking for things I think my readers will value. This article contains some affilate links to products that I have used and found helpful. If you purchase these, then I may see a share of the revenue. This comes at no extra cost to you.

## What is stability in sorting algorithms and why is it important?

Stable means that two elements with equal values will appear in the same order in the sorted output as they appear in the unsorted input array.

For example, if we wanted to sort:

`[â€śCherriesâ€ś, â€śBlackberriesâ€ť, â€śApplesâ€ť, â€śBananasâ€ť]`

into alphabetical order by first letter, with a stable sorting algorithm, the output would be:

`[â€śApplesâ€ť, â€śBlackberriesâ€ť, â€śBananasâ€ť, â€śCherriesâ€ť]`

As you can see, â€śBlackberriesâ€ť and â€śBananasâ€ť remained in the same relative positions in the input and output array because the algorithm is stable. Stable sorting algorithms:

• Bubble Sort
• Merge Sort

If the algorithm was unstable, then â€śBananasâ€ť and â€śBlackberriesâ€ť may be interchanged (`[â€śApplesâ€ť, â€śBananasâ€ť, â€śBlackberriesâ€ť, â€śCherriesâ€ť]`).

Unstable sorting algorithms:

• Selection Sort
• Heap Sort
• Quick Sort

Why is it important to know if an algorithm is stable?

Suppose we have an array of first and last names and we needed to sort by first name, then by last name, e.g.:

`[â€śDanny Adamsâ€ť, â€śBill Gatesâ€ť, â€śDan Jenkinsâ€ť, â€śDylan Grubâ€ť]`

First, we could sort by first name using either a stable or unstable algorithm because we donâ€™t need to preserve relative positions. Letâ€™s say we use an unstable sorting algorithm, and we get back:

`[â€śBill Gatesâ€ť, â€śDylan Grubâ€ť, â€śDan Jenkinsâ€ť, â€śDanny Adamsâ€ť]`

The array is now in order by first name â€“ great. But now we need to be careful: the relative positions need to be respected when we sort by last name; we donâ€™t want â€śBill Gatesâ€ť to get swapped with â€śDylan Grubâ€ť â€“ this could happen if we used an unstable sorting algorithm.

Using a stable algorithm to sort by last name, weâ€™d safely end up with: `[â€śBill Gatesâ€ť, â€śDanny Adamsâ€ť, â€śDylan Grubâ€ť, â€śDan Jenkinsâ€ť]`

Happy days.

## What is an In-place sorting algorithm?

An in-place sorting algorithm is an algorithm which transforms input using no auxiliary data structure; however, a small amount of extra storage space is allowed for auxiliary variables.

In simple terms, â€śin-placeâ€ť just means that the input is overwritten (via swapping or replacement) by the output as the algorithm executes.

The advantage of in-place algorithms is that they take up less space in memory. The input is overwritten, and so no extra data structures are required; this doesnâ€™t include constant time variables, which will never take up much space, such as the i in for-loops.

In-place algorithms have constant space complexity. Out-of-place algorithms have greater than constant space complexity, e.g.: linear time or quadratic time.

In-place algorithms: Bubble Sort, Selection Sort, Insertion Sort, Heap Sort.

Out-of-place: Merge Sort.

## What is a comparison algorithm?

A comparison sorting algorithm is an algorithm that only reads the list of elements through a single abstract comparison operation (usually a â€śless thanâ€ť or â€śequal toâ€ť) that determines which of the two elements should occur first in the final sorted output array.

Comparison sorting algorithms:

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort

An example of a non-comparison-type sorting algorithm would be Radix Sort. It avoids comparison by creating and distributing elements into buckets according to their radix. Radix Sort exploits the face that information about the size of a number is encoded in the number of digits; more digits equals a bigger number.

If you enjoyed this post, subscribe to my newsletter. I write on topics such as algorithms, UI design and freelancing. Iâ€™ll email you once per week with my latest article along with bonus tips and tricks. I like to dive deeply into topics to give you all the information you need in one place!

And if you want to further your knowledge of algorithms and data structures, check out: JavaScript Algorithms and Data Structures Masterclass by Colt Steele. Itâ€™s the best Udemy course Iâ€™ve ever taken đź‘Ś.