Describe the difference between Selection, Bubble and Insertion Sort

Question

Describe the difference between Selection, Bubble and Insertion Sort

Answer 1

This comparison is written on the assumption that you know how the algorithms work.

Let n be the number of element in the given array to be sorted.

All three algorithms are "in place" (i.e., use only constant amount of extra memory), and

use the same strategy of dividing the given array into two section:

- sorted section (initially empty)

- unsorted section (initially the whole array).

They all do a number of passes over the array (in the worst case n passes).

Each pass expands the sorted section and shrinks the unsorted section.

They terminate when the unsorted section becomes empty.

Now the differences:

1) Each pass of the Insertion sort iterates over the sorted section, while each pass of

Bubble sort and Selection sort iterate over the unsorted section.

2) All three algorithms swap elements (which is what makes them "in place"), but they

differ in the number of swaps per pass, and in the choice of elements to swap.

Selection sort makes just one swap per pass - it swaps the first element of the

unsorted section with the smallest element of the unsorted section.

Bubble sort swaps only neighboring elements; namely those in the "wrong" order.

Insertion sort swaps elements in the sorted section when moving them to make room

for the new element to be inserted.

3) Insertion sort is the only one that is "online" -- it can sort one element at a time

as it receives them.

This is a consequence of not passing over the unsorted section.

4) Bubble sort, by the nature of the algorithm, is "stable"; that means that two elements

with identical keys will retain their relative position in the sorted array.

Insertion sort and Selection sort can be implemented as stable, as well, but it is

up to the implementation; it is not guaranteed by the nature of the algorithm.

5) All three algorithms have O(n²) worst case complexity.

But Bubble sort and Insertion sort are "adaptive", meaning that their complexity for

sorted arrays is only O(n).

In contrast, Selection sort has O(n²) complexity even for sorted array.

The reason is that every pass must go over the entire unsorted section.