Selection Sort

#Sorting#Computer-Science#CS251 Loops through the array, for each index finds the position it goes in the array and swaps it with the element at that position.

Psuedocode §

SelectionSort(A: array of size n)
	for (i = 0, i < n-1, 1)
		index <- i
		for (j = i+1, j < n, 1)
			if (A[j] < A[index])
				index <- j
			endif
		endfor
		if (index != i)
			swap(A, i, index)
		endif
	endfor
end SelectionSort

Details §

• Is Unstable
• Is in place
• Time Complexity
  • If Array is sorted
    • # Compares = $T(n)=\frac{1}{2}{n}^2-\frac{1}{2}n\in \Theta (n^2)$
    • # Swaps = $T(n)=0\in \Theta (1)$
  • If array is in opposite order
    • # Compares = $T(n)=\frac{1}{2}{n}^2-\frac{1}{2}n\in \Theta (n^2)$
    • # Swaps = $T(n)=\frac{n}{2}\in \Theta (n)$

Best Case $\Theta (n^2)$ §

Worst Case $\Theta (n^2)$ §