Sorting algorithm - Selection Sort and Insertion Sort

This post will introduce two simple sorting algorithms - Selection Sort and Insertion Sort.

Selection Sort

The selection sort algorithm sorts an array by finding minimum element from unsorted part of the array and putting it at the front of the unsorted part.

Let A[0..n] be an array of n elements. The selection sort algorithm sorts the elements in A as follows. First, it finds the minimum element and store it in A[0]. Next, it finds the minimum of the remaining n-1 elements and store it in A[1]. It continues until A is sorted. The pseudo code  is described in SelectionSort.

Algorithm 1 SelectionSort
Input: An array A[0..n] of n elements
Output: A[0..n] sorted in non-decreasing order

1. for i = 0 to n
2.     k = i
3.     for j = i + 1 to n
4.         if A[j] < A[k] k = j
5.     end for
6.     if \(i \neq k\) then swap A[i] and A[k]
7. end for

A JAVA implementation of this algorithm can be found on GitHub - Selection Sort. 

Time complexity 

The basic operation of this algorithm is the element comparison in step 4. It is easy to see the number of element comparison performed by selection algorithm is $$ \sum\limits_{i=0}^n (n-i) = n + (n-1) + (n-2) + ... + 1 = \sum\limits_{i=1}^n i = \frac{n(n-1)}{2}$$
It is easy to see the number of element comparison performed by selection sort algorithm is always \(\frac{n(n-1)}{2}\) regardless of how the input array are ordered. Thus, the time complexity is \(\Theta(n^2)\).

Insertion Sort

The insertion sort algorithm sorts an array by inserting one element from the unsorted part of the array into the right position of the sorted part. It works the way of sorting cards in our hands.

Let A[0..n] be an array of n elements. The insertion sort algorithm sorts the elements in A as follows. We begin with the sub array of the first element A[0]. Apparently, A[0] is already sorted because there is only one element. Next, A[1] is inserted before A[0] if it is smaller than A[0], otherwise, A[1] is inserted after A[0]. Continuing this way, A[i] is inserted in the sorted sub array A[0..i-1]. This is done by comparing A[i] to A[i-1] down to A[0] until an element is less than or equal to A[i] is found. If A[j] (j = i-1 to 0) is greater than A[i], shift A[j] to A[j+1]. A[i] is then inserted at the position after the found element. The pseudo code is described in InsertionSort.

Algorithm 2 InsertionSort

Input: An array A[0..n] of n elements

Output: A[0..n] sorted in non-decreasing order

1. for i = 0 to n
2.     x = A[i]
3.     j = i - 1
4.     while (\(j\ge0\)) and (A[j] > x)
5.         A[j+1] = A[j]
6.         j = j - 1
7.     end while
8.     A[j+1] = x
9. end for

A JAVA implementation of this algorithm can be found on GitHub - Insertion Sort.

Time complexity

Unlike selection sort algorithm, the number of element comparison performed by insertion sort algorithm depends on the order of the input array. If the input array is already sorted in non-decreasing order, the number of element comparison is n - 1, because the element A[i] is compared with A[i-1] only. On the other hand, if the input array is already sorted in decreasing order, the number of element comparison is $$ \sum\limits_{i=0}^{n}i = \frac{n(n-1)}{2} $$

As stated above, the number of element comparison performed by insertion sort is between n - 1 and \(\frac{n(n-1)}{2}\). The time complexity can be described using the O-notation as O(\(n^2\)).

Based on the discussion above, we can see that the insertion sort algorithm performs better than selection sort algorithm if the input array is not sorted in decreasing order already. But the time complexity of both algorithms is O(\(n^2\)).

Reference:

http://geeksquiz.com/selection-sort/

http://geeksquiz.com/insertion-sort/

Algorithm Design Techniques and Analysis by M.H. Alsuwaiyel