Stability

In this lesson, we will check for the stable nature of bubble sort algorithm.

What is stability?

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.

For example, if we have to sort the array- [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] , here we have two 8's, denoted by 8₁ and 8₂. After sorting, two possible arrays can be obtained- [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>] and [1,2,4,6,<strong>8<sub>2</sub></strong>,<strong>8<sub>1</sub></strong>] . These both the arrays are sorted, but in the second one, order of two 8's is different, whereas in the first array, it is same as the input array.

Now, let's check this for bubble sort algorithm.

First Pass: [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] -> [2,4,<strong>8<sub>1</sub></strong>,6,1,<strong>8<sub>2</sub></strong>]

Second Pass: [2,4,<strong>8<sub>1</sub></strong>,6,1,<strong>8<sub>2</sub></strong>] -> [2,4,6,1,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

After all the passes, final output will be: [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

Try to notice that, order of 8's is same in both output and input arrays.

Hence, Bubble sort algorithm is Stable!