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.