Simple Sorts

From

There are three basic simple sorting algorithms: Insertion Sort, Selection Sort, and Bubble Sort. We will consider how each sort works using the example: 81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15 and sorting in ascending order.

Insertion Sort:

We can see that the worst case for Insertion Sort is when the data is sorted in the opposite order; i.e., the data is in descending order and we want it sorted in ascending order. In this case, for N items, the sort requires, 1 + 2 + 3 + … + N -1 comparisons. By Gauss’s formula, this is ((N(N-1))/2)-N comparisons, which makes Insertion Sort an O( N²) algorithm. The best case for Insertion Sort, however, occurs when the data is already sorted in the proper order. In this case, the sort requires N comparisons for N data items making it an Ω(N) sort in the best case.

A variation of Insertion Sort is called Binary Insertion Sort. This sort uses a binary search to find the proper location for the item being inserted. However, while a binary insertion sort can take less time than insertion sort for a large array, the asymptotic run-time does not change.

Selection Sort:

As we can see from the example, a selection sort must run a minimum or a maximum function on the unsorted portion of the data to find the next element to be placed. Since it takes N comparisons to find the minimum or the maximum of N unsorted items, selection sort requires N + N-1 + N-2 + … + 2 comparisons to sort N items. Again, by Gauss’s formula, this makes Selection Sort O( N² ). Note, however, that it doesn’t matter if the data is sorted already or not. Selection Sort requires the same number of comparisons in all cases, so that Selection Sort is Ω( N² ) as well.

Bubble Sort:

In its basic form, Bubble Sort is as bad a sort as you can find. In the basic form bubble sort takes (N -1)(N-1) = N² – 2N + 1 comparisons to sort N items. We might say that Bubble Sort is about as close to a true O( N² ) and Ω( N² ) algorithm as we can find.

We can see that a few improvements to the algorithm, such as an early exit, can allow Bubble Sort to take only N comparisons on N items when the data is already in the correctly sorted order. However, it is still normally the slowest of the three simple sorts. It only real advantage is that it has the simplest algorithm to code.

Even with an early exit, if the smallest value in the array is in location A[N], where A is an N item array to be sorted in ascending order, Bubble Sort still takes N² – 2N + 1 comparisons to sort the array. Because of this, there is a variation on Bubble Sort called Shaker Sort or Two-Way Bubble Sort that attempts to get around this problem. However, Shaker Sort also has a special case which will cause it to take N² – 2N + 1 comparisons: Place the middle element in the first position of the array and the rest of the data in descending order.

One of the reasons that both Insertion Sort and Bubble Sort are O( N² ) algorithms, is that they sort by exchanging adjacent elements. We can prove mathematically that in the general case a sorting algorithm that only exchanges adjacent elements can not do better than O( N² ). This means that a characteristic of an advanced sort, which does better than O( N² ), is that it exchanges elements that are not adjacent.

Back to Sorting