Selection Sort Algorithm Example | DSA Tutorials

The selection sort algorithm has a complexity of O(n²). The advantage of selection sort is that it is simple and easy to implement. The disadvantage is that it is inefficient for large lists, so, similar to the more efficient insertion sort, the insertion sort should be used in its place.

Selection Sorting Algorithm

The selection sorting is based on the idea of selecting the smallest unsorted item remaining in the list and then swapping it with the item to be replaced in the next position. The logic for selection sort is very simple.

Sorting Steps

• Step-1: Given a set of elements N, we find out the location of the minimum element among the set and replace it with the location of the first element.
• Step-2: Next, we do the same task for N-1 elements and find out the location of the minimum element among N – 1 elements and replace it with the location of the first element (of set N – 1). After the first step, the minimum element will be at the first location. After the second step, the second minimum element among the remaining list will be at the second position and soon.
• Step-3: Next, we repeat the same task for all the elements and find out the location of the minimum element among the remaining array elements and replace it with the respective position.
• Step (N-1): This process is repeated, and finally, after N – 1 steps, the list or set will be sorted. Here, N is the number of elements of the array.

Although it is faster than the bubble sort, there is no improvement if the input file is completely sorted or unsorted. Despite the fact that it is simple to code, it is unlikely that the straight selection sort would be used on any files but those for which n is small. The selection sort algorithm for sorting works as follows. First, find the smallest element in the list and put it in the first position. Then find the second smallest element in the list and put it in the second position. It is to be noted that the number of comparisons in the selection sort algorithm is independent of the original sort of the elements. The selection sort method requires (n-1) passes to sort an array.

Selection Sorting Example

Let’s take an example to understand the selection sort in detail with a complete step-by-step process.

Example 1: We have an array ‘A‘ with ‘N‘ elements.

2 5 6 7 8 12 34 20 1 67

Solution: So, using the selection sort, we need N-1 = 10 – 1 = 9 steps to sort the array.

L_min = smallest element index
A[0] = 2
A[1] = 5
A[2] = 6
A[3] = 7
A[4] = 8
A[5] = 12
A[6] = 34
A[7] = 20
A[8] = 1
A[9] = 67

Step 1: First, we are going to find the Index of the smallest element, which is L_min = A[8] = 1. So we are going to swap the position of A[8] to A[0] (means the value of A[8] goes to the first position and the value of A[0] goest ot 8^th position of the array). So our new array is:

2, 5, 6, 7, 8, 12, 34, 20, 1, 67 $\Rightarrow$ 1, 5, 6, 7, 8, 12, 34, 20, 2, 67

Now, the first position of the array has the smallest element. So we are going to follow the same step with the remaining array elements. First, we are going to find the smallest element in the remaining array and then swap the position of that element with the 2^nd position of the array. In this selection sorting algorithm, we need 9 steps to sort the array. All the sorting steps are shown in Table 1 below.

Algorithm Steps

The algorithm for selection sort is very simple:

selsort (arr[], N)
{
    for (i=0 to N-1)
    {
        loc = location of the minimum element in the index range 0 to N-i-1
        swap arr[i] and arr[loc]
    }
}

selsort (arr[], N)
{
    for (i=0 to N-1)
    {
        loc = location of the minimum element in the index range 0 to N-i-1
        swap arr[i] and arr[loc]
    }
}

Algorithm Implementation

SELECTION_SORT (A, N)
Here A is an array with N elements. This algorithm sorts the array A with N elements in ascending order.
1.   Repeat Steps 2 to 5 for i = 1 to N-1:
2.       Set MIN: = A[i]
3.       Set POS: = i
4.       Repeat Steps for j = i + 1 to N:
              If A[j] < MIN, then:
                    (a) Set MIN:= A[j]
                    (b) Set POS:= j
              [End of If structure]

SELECTION_SORT (A, N)
Here A is an array with N elements. This algorithm sorts the array A with N elements in ascending order.
1.   Repeat Steps 2 to 5 for i = 1 to N-1:
2.       Set MIN: = A[i]
3.       Set POS: = i
4.       Repeat Steps for j = i + 1 to N:
              If A[j] < MIN, then:
                    (a) Set MIN:= A[j]
                    (b) Set POS:= j
              [End of If structure]

Let’s take another example to understand the selection sort, and then we implement the algorithm in a programming language.

Example 2: Suppose an array A contains 8 elements as follows:

77, 33, 44, 11, 88, 22, 66, 55

Applying the selection sort algorithm to A yields the data. Observe that LOC gives the location of the smallest among A[K], A[K+1], …, A[N] during Pass K. The green elements indicate the elements that are to be interchanged.

Complexity of Selection Sort