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.

Bubble Sort:

Another common operation is to sort the data in an array. We usually want to put the data into ascending order, but sometimes descending (backwards) order is used. 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.

Bubblesort is based on swapping out-of-order pairs of data items, in sequence, so as to bubble to the top of the array (if pictured vertically) the largest data item. That largest item is somehow marked as done and the same game of bubbling the largest (of the rest of the data items) to the top is played all over again, etc. Thus we get the largest at the top, then the second largest, then the third largest, etc.

Although our program sorts an array of integers, for the purpose of tracing the workings of bubblesort let's pretend that we have modified it to sort an array of characters. This leads to the following drawings, where each row (or "pass") is handled by the for loop and the succession of passes is handled by the while loop. The bracket in each drawing of the array shows the two data items that are being compared to see if they are out of order.

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.

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.