DEV Community

loading...

Selection Sort Algorithm Analysis and implementation in C

Rodolfo
Updated on ・2 min read

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(n2)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.


ALGORITHMSelectionSort(A[0..n1])// Sorts a given array by selection sort// Input: An array A[0..n - 1] of orderable elements// Output: Array A[0..n - 1] sorted in nondecreasing orderfor i0 to n2 domin ifor ji+1 to n1 doifA[j]<A[min] minjswap A[i] and A[min] \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.

C(n)=i=0n2j=i+1n11=i=0n2[(n1)(i+1)+1]=i=0n2(n1i) C(n) = \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 n2n^2

C(n)=j=i+1n11=i=0n2(n1i)=(n1)n2=(n2n)2 C(n) = \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(n2) O(n^2)

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

gcc selection_sort.c -o selection_sort
Enter fullscreen mode Exit fullscreen mode
#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;
}
Enter fullscreen mode Exit fullscreen mode

Discussion (0)