Selection Sort Algorithm Analysis

Analyze Selection Sort using Big O Asymptotics Line by Line!

Note: The code I use in this article is slightly different

OVERVIEW

Selection sort is a sorting algorithm in computer science. It has O(n²) time complexity. O(n²) isn’t a good time complexity for sorting lists when it comes to large input sizes. This algorithm sorts an array or list by repeatedly finding the minimum value (if we are sorting in ascending order) from the list or array and placing it at the beginning of the list. Here I am going to go line by line on the selection sort algorithm to compute the algorithms runtime.

arr[] = 65 25 12 22 10

// Find the minimum element in arr[0...4]
// and place it at beginning
10 30 12 22 65

// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
10 12 30 22 65

// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
10 12 22 30 65

// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
10 12 22 30 65

Selection Sort Code

Selection Sort C-Program Analysis

Here I am going to analyze the code being executed line by line (this does not include comments).Their are two things we need to keep track of to analyze the time complexity of the selection sort algorithm and that is the cost it takes to execute the statement at each line and the number of times the statement at that line is executed.

 // C program for implementation of selection sort
//NOTE: REMOVE The Line Numbers (e.g. Line 1.) if you want to run this code
// I inserted them to help with the analysis
#include <stdio.h>
void selectionSort(int arr[], int n)
{
 Line 1.int i, j, min_idx;
  
  // One by one move boundary of unsorted subarray
 Line 2. for (i = 0; i < n; i++){
// Find the minimum element in unsorted array
 Line 3.    min_idx = i;
 Line 4. for (j = i+1; j < n; j++){
 Line 5.        if (arr[j] < arr[min_idx])
 Line 6…