Selection Sort

Notation

$\Omega (n^2)$

$\theta (n^2)$

$O(n^2)$

Step by Step

Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted

1. Find the smallest value in the list

2. Put the smallest value at the start of the list (after any values already put there)

3. Now you search the rest of the list (not including the values moved to the start of the list)

Pseudocode

a = list
n = size of list


for (i = 0; i < n-1; i++)
	int iMin = i;

	for (j = i+1; j < n; j++)
		if (a[j] < a[iMin])
			iMin = i;
	
	if (iMin != i)
		swap(a[i], a[iMin])
 

Video