Selection Sort - Algorithm Analysis

Let us look at the time and space complexity of the Selection Sort algorithm.

As seen in the above diagram, for n element list, there are total n -1 iterations required. Total number of comparisons required in the first iteration is n - 1, in second iteration n - 2, in third iteration n -2 and so on. This is comparison scenario is equivalent to summation series.

Hence, the time complexity of selection sort using asymptotic Big(O) notation is O(n^2). 

If we consider the swap operations, selection sort takes n swaps (1 swap operation in each iteration). According to the asymptotic notation, the value n^2 will dominate for large values of n. Hence this constant value of swap operations can also be dropped for algorithm analysis. So worst case running time for selection sort is O(n^2).

Space complexity for selection sort is O(1). Extra space is required only during swap operation.

Selection Sort

In selection sort algorithm, list is divided into 2 lists: sorted & unsorted list.
In each iteration, smallest element is selected from unsorted list and appended to the sorted list.

While starting the scan of list, assume that the first element is the smallest, then compare it with the rest of the elements in the list, save the index of smallest element along the way. Once all the elements are scanned, swap the starting index element with the minimum index element (if the indices are different).

Here is a Java implementation of a selection sort algorithm:

In the next post, we will look at the time & space complexity of the selection sort algorithm.