Selection Sort Algorithm Analysis and implementation in C

Rodolfo — Mon, 15 Feb 2021 01:31:16 +0000

Selection Sort is an algorithm that falls under the category of Brute Force because it depends on the input size and it goes over all elements (or almost all elements) in order to perform its main task. It is not really effective since it's time complexity is $O(n^2)$ but it is a really simple algorithm and the analysis is straightforward. Let's start seeing the pseudo-code, followed by its analysis and finally but not least, an example using C language.

$\bold{ALGORITHM} \quad SelectionSort(A[0..n - 1]) \newline \text{// Sorts a given array by selection sort} \newline \text{// Input: An array A[0..n - 1] of orderable elements} \newline \text{// Output: Array A[0..n - 1] sorted in nondecreasing order} \newline \bold{for} \space i \gets 0 \space \bold{to} \space n-2 \space \bold{do} \newline \quad min \gets \space i \newline \quad \bold{for} \space j \gets i + 1 \space \bold{to} \space n-1 \space \bold{do} \newline \quad\quad \bold{if} A[j] < A[min] \space min \gets j \newline \quad swap \space A[i] \space and \space A[min]$

Here you can see the algorithm analysis. We notice that since we have two for loops, we start the analysis with two sums as well.

\sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} 1 = \sum_{i=0}^{n-2}[(n-1)-(i+1)+1] = \sum_{i=0}^{n-2}(n-1-i)

Simplifying a bit more, we can see that it turns to be a fraction with a quadratic element on its numerator. If we consider this element with limit to infinite $∞\infty$ , we'll reduce to just a regular $n^2$

\sum_{j=i+1}^{n-1} 1 = \sum_{i=0}^{n-2}(n-1-i) = \frac{(n-1)n}{2} = \frac{(n^2-n)}{2}

O(n^2)

Finally, you can see the an example using C. You can compile it with:

gcc selection_sort.c -o selection_sort

#include <stdio.h>

void swap(int *a, int i, int min, int i_value, int min_value) {
  a[i] = min_value;
  a[min] = i_value;
}

int selection_sort(int *a, int n) {
  int i, j, min;

  for (i = 0; i < (n - 1); i++) { 
    min = i; 
    for (j = i + 1; j < n; j++) {
      if (a[j] < a[min]) {
        min = j;
      }
    }
    swap(a, i, min, a[i], a[min]); 
  }

  return 0;
}

int main() {
  int n = 7;
  int array[] = {89, 45, 68, 90, 29, 34, 17};

  printf("Before: \n");
  for (int x = 0; x < n; x++) {
    printf("%d, ", array[x]);
  }
  printf("\n\n");

  selection_sort(array, n);

  printf("After: \n");
  for (int x = 0; x < n; x++) {
    printf("%d, ", array[x]);
  }
  printf("\n");

  return 0;
}

DEV Community: Rodolfo

Selection Sort Algorithm Analysis and implementation in C