Array Sorting Algorithms: Selection Sort and its Efficiency

Last updated : Jul 30, 2023 12:00 AM

Selection sort reduces the number of swaps. We need O(N) swaps, compared to O(N²) with Bubble sort. But the number of comparisons remains O(N²). The advantage of Selection sort is the reduced number of time-consuming swaps (n-1 swaps in the worst case scenario), which can improve performance on large amounts of data. However, most modern languages use references instead of values. Therefore, swapping has less impact on performance.

How Selection Sort works

Starting from the array position zero, the Selection sort compares each element with other elements in the array. Then it stores the reference to the lowest element. Then at the end of each iteration, it swaps the values.

Now let's try to sort the below array with Selection sort.

int arr = {3,10,8,9,7,5,4,6,2,1}; int min = arr[0]

Array length is 10

We need 9 iterations = n
We need 45 comparrisons (n(n+1)/2)

In the first iteration, first comparrison, we compare element 0 with element 1, or arr[0] with arr[1]. Since 3 < 10, arr[0] is less than arr[1], min remains unchanged.

Figure 1 :First iteration, min is still index 0

In the second comparison, arr[0] is smaller than arr[2] (3 < 8), min remains unchanged.

Figure 2 :Second iteration, min is still index 0

Third comparison, arr[0] is smaller than arr[3] (3< 9), min remains unchanged.

Figure 3 :Third iteration, min is still index 0

Fourth comparison, arr[0] is smaller than arr[4] (3 < 7), min remains unchanged.

Figure 4 :Fourth iteration, min is still index 0

Fifth comparison, arr[0] is smaller than arr[5] (3 < 5), min remains unchanged.

Figure 5 :Fifth iteration, min is still index 0

Sixth comparison, arr[0] is smaller than arr[6] (3 < 4), min remains unchanged.

Figure 6 :Sixth iteration, min is still index 0

Seventh comparison, arr[0] is smaller than arr[7] (3 < 6), min remains unchanged.

Figure 7 :Seventh iteration, min is still index 0

Eighth comparison, arr[0] is greater than arr[8] (3 > 2), and min is set to 8.

Figure 8 :Eighth iteration, min is index 8

Ninth comparison, arr[0] is greater than arr[9] (3 > 1), and min is set to 9.

Figure 9 :Ninth iteration, min is index 9

Now we have the index of the smallest number set to min. Swap the values of arr[0] and arr[min]. This process happens 9 times (n-1) before the array is fully sorted.

Placeholder 1

private static void SelectionSort() {
   int[] arr = {99,10,28,100,1,76,2,33,0,3,-1};
   int length = arr.length;
   int min;
   int temp;
   for(int a=0; a<length-1; a++) {
      min = a;
      for(int b=a+1; b<length; b++) {
         if(arr[b] <arr[min]) {
            min = b;
         }
      }
      temp = arr[a];
      arr[a] = arr[min];
      arr[min] = temp;
   }
}

The Efficiency of Selection Sort

As we discussed above, we needed 9 iterations to sort an array with 10 elements. The inner loop made 9 comparisons on the first pass, 8 on the second, and so forth. 9+8+7+6+........+1 = 45 comparisons for 10 elements. When the number of elements is represented by n, (n-1)+(n-2)+(n-3)+(n-4)+......+1 = n(n-1)/2 = n*n-1/2 = 45 for 10 elements

We can ignore the -1 for larger n's. n*n/2 Ex, for an array of 10000 elements 10,000*10,000/2 = 50,000,000 comparisons.

Even in the worst-case scenario (array is inversely sorted), only one swap happens in every iteration. So for larger amounts of data, Selection sort runs in O(N²). However, Selection sort has the advantage of lesser swaps, a slightly increased performance.

Array Sorting Algorithms: Selection Sort and its Efficiency

How Selection Sort works

The Efficiency of Selection Sort

Related Links

By: Lance