Selection Sort: Algorithm Implementation and Time Complexity

Introduction

Of all the sorting algorithms, selection sort may be the easiest to conceptualize, selecting the smallest values in an array, and bringing them to the front.

This comprehensive guide will cover all the bases of selection sort, from its pros and cons and an implementation within C, to calculations of its time complexity.

So... Why Selection Sort?

Nearly every sorting algorithm comes with a trade-off between system resources--memory and CPU--and speed or algorithmic efficiency known as time complexity.

Much like insertion sort, selection sort tends to use less resources, all the while skimping on runtime. Let's look over some pros and cons of this sorting method.

Advantages:

• Ideal for small lists

• In-place sorting algorithm

  • doesn’t require any additional memory, as all of the sorting occurs within the same array

  • basically, the program doesn’t create a new, temporary array for storage

Disadvantages:

• Not so efficient for large lists

• Not a stable sorting algorithm

  • relative order of (equal) elements is NOT preserved once sorted

Selection Sort in C

On a higher, less syntactic-level, we can express selection sort in pseudocode:

• On the first iteration, starting at the zeroth element, the program loops over the entire list (excluding the zeroth element), finding the smallest value.
  

• Once found, the smallest value is swapped with the zeroth element. Now, one element is successfully sorted.

• On the next iteration, starting at the first element, the program loops over the rest of the list (excluding the zeroth and first elements), to find the next smallest value.

• This value is swapped with the first element.

• This process continues until the loop has sorted the second-to-last element, at which point we know that the last element is the greatest (or one of the greatest) elements in the list.

Let's use the list [ 9, 5, 3, 8, 0 ] to simulate this. The numbers highlighted are the ones that have just been swapped.

1. [ 0, 5, 3, 8, 9 ]

2. [ 0, 3, 5, 8, 9 ]

3. [ 0, 3, 5, 8, 9 ] (no elements are swapped here)

4. [ 0, 5, 3, 8, 9 ] (no elements are swapped here)

With a general idea as to how this algorithm should work, let's have a look at its formal implementation in C.

Note that the comments (denoted with //) can be helpful in understanding what each part of the program does!

#include <stdio.h>

// function for swapping uses a temporary variable to store the address of one value. Note that * must be used to swap the memory addresses of the values.
void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void selectionSort(int arr[], int n)
{
    int i, j, min_idx;

    // loops over the entire array excluding the last element
    for (i = 0; i < n-1; i++)
    {
        // Finds the minimum element in the unsorted array
        min_idx = i;
        for (j = i+1; j < n; j++)
          if (arr[j] < arr[min_idx])
            min_idx = j;

        // Swaps the found minimum element with the ith element
        if(min_idx != i)
          swap(&arr[min_idx], &arr[i]);
    }
}

// prints array
void printArray(int arr[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}


int main()
{
    int arr[] = {64, 25, 12, 22, 11};
	// finds the length of the list by dividing the number of  bytes in the total array by the number of bytes in a single element (as all elements have the same type)
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Calculating Time Complexity

Time Complexity is a measure of how efficient the program in terms of the amount of time it takes to run (and thus, the number of steps required to run the algorithm).

In order to measure time complexity, we can consider the two corner cases: a fully sorted and an unsorted array of infinite elements, expressed through Big-Omega and Big-O notations (respectively), on which you can find more about in my CS50's Week 3 blog!

Best Case Scenario: all elements in the array are pre-sorted

Assuming that all elements are sorted, our outer loop from 0 to n-2 (inclusive) would yet run, and our inner loop going from i+1 to n-1 (inclusive) would also run. Note that because the if statements throughout the program run just once at a time, they are negligible when considering time complexity because they are constant values.

Mathematically...

n - 2 n - 1 n - 2

Σ Σ 1 = Σ n - (i + 1) = (n - 2)(n - 1)/2

i = 1 j = i + 1 i = 1

Because n^2 is the most prominent term, we can express this as Ω(n^2).

Worst Case Scenario: all elements in the array are in reverse order

In this case, both the inner and outer loops would run! The only difference, technically, would be a greater constant value (from the singular if statement within the second loop); however, since time complexity disregards constants, our worst case scenario time complexity would be the same

Again...

n - 2 n - 1 n - 2

Σ Σ 1 = Σ n - (i + 1) = (n - 2)(n - 1)/2

i = 1 j = i + 1 i = 1

Because the most prominent term is n^2, we can express this as Ο(n^2).

Now since both the best and worst cases share the same time complexity, we can, in fact, say that selection sort has a time complexity of θ(n^2), read as Big-Theta of n^2.

Final Thoughts

Overall, selection sort is an easy-to-implement sorting algorithm, looping through an array and placing the smallest local value at the front.

This sorting method can be especially useful when dealing with smaller datasets, unaffected by the initial order of elements.

This was everything you need to know about selection sort. Thanks for reading!

Meanwhile, stay tuned for updates by following my blog and LinkedIn page.