In this article, we are going to take you through the one of the sorting algorithms, Selection sort step by step and perform a complete analysis of it. In this technique, we find the smallest element in each pass and place it in the appropriate positions to get the element in ascending or descending order. Number of passes required would be (n-1). For instance if we have 5 elements, it would require 4 passes. And in each pass we have n-k comparisons, where n is the number of elements and k is the pass number.

Algorithm

Consider an example of array having 5 elements and we need to arrange them in ascending order. Since we have 5 elements, we require 4 passes to get the sorted array.

5       4       3       1       2

Pass 1 of 4, Here the smallest element would be 1 and exchange that with the swap position

Now, In pass 2 the swap position will be in 4 and the smallest number will be 2. Interchanging them will yield the following result.

In pass 3, The swap position and the smallest element lie in 3. So we cannot swap but proceed to the next swap.

In the final pass, the swap position lies in 5 and the smallest element is in 4. So we swap them in order to get the array arranged in ascending order.

Code

On execution of the above code, we get the output as shown below

Time complexity

For n elements array,

In 1st pass we have, (n-1) comparisons

In 2nd pass we have, (n-2) comparisons

Similarly, in kth pass we have (n-k) comparisons.

Therefore, total comparisons are :

F(n)= (n-1) + (n-2)+ (n-3)+ .. +3+2+1 = n(n-1)/2 = O(n2)

References

This site uses Akismet to reduce spam. Learn how your comment data is processed.