Selection Sort Algorithm Analysis

Analyze Selection Sort using Big O Asymptotics Line by Line!

Image for post
Image for post
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. min_idx = j;}
// Swap the found minimum element with the first element
Line 7. int temp = arr[min_dx];
Line 8. arr[min_dx] = arr[i];
Line 9. arr[i] = temp;
}
}
/* Function to print an array */
void printArray(int arr[], int size){
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program to test above functions
int main(){
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}

Inside the selectionSort function:

Line 1: COST= C1, TIME = 1, where C1 is some constant
Line 2: COST=C2, TIME = n+1, where C2 is some constant
Line 3: COST = C3, TIME = n, where C3 is some constant
Line 4: COST = C4, TIME = (n²-n) / 2 + n, where C4 is some constant
Line 5: COST = C5, TIME = (n²-n) / 2, where C5 is some constant
Line 6: COST= C6, TIME = (n²-n) / 2, where C6 is some constant
Line 7: COST = C7, TIME = n, where C7 is some constant
Line 8: COST = C8, TIME = n, where C5 is some constant
Line 9: COST = C9, TIME = n, where C9 is some constant

A video showing how I figured out the TIME for each line of code being executed is below, or you can click here to watch. Now that we have all of the costs and the times, we must sum up all of the costs times the time to get the runtime:

Runtime = (C1 *1) + (C2 *(n+1)) + (C3 *n) + (C4 * ((n²-n)/2) + n) + (C5 * (n²-n) / 2) + (C6 * (n²-n) / 2) + (C7 * n)+ (C8 * n)+ (C9 * n)

Where U,V, and W are constants
= U +Vn + Wn²
= O(n²)

If you would like to learn more about Algorithm Analysis , you can take my online course here. I also have a course on Udemy.com called Recurrence Relation Made Easy where I help students to understand how to solve recurrence relations and asymptotic terms such as Big-O, Big Omega, and Theta. You can check out my YouTube channel of videos where I solve recurrence relations and perform algorithm analysis on code that anyone can check out for free !

Image for post
Image for post

Thanks for reading this article I hope its helpful to you all ! Keep up the learning, and if you would like more computer science, programming and algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )

Check Out the following for content / videos on Computer Science, Algorithm Analysis, Programming and Logic:

YouTube Channel:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA

Website:
http://everythingcomputerscience.com/

Video Tutorials on Recurrence Relation:
https://www.udemy.com/recurrence-relation-made-easy/

Video Tutorial on Algorithm Analysis:
https://www.udemy.com/algorithm-analysis/

Twitter:
https://twitter.com/CsEverything

YouTube Channel:

Image for post
Image for post

Computer Science Website:

Image for post
Image for post

Udemy Videos on Algortithm Analysis:

Image for post
Image for post

RESOURCES:
[1] https://www.geeksforgeeks.org/selection-sort/

http://www.cs.cornell.edu/courses/cs211/2005sp/Lectures/L14-BigO/L14-15-Complexity.4up.pdf

https://math.stackexchange.com/questions/417853/selection-sort-algorithm-analysis

https://www.khanacademy.org/computing/computer-science/algorithms/sorting-algorithms/a/analysis-of-selection-sort

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store