Sorting Algorithms

Selection Sort

This is the worst algorithm, but it is introduced in every class.

High Level Idea:

1. Find the smallest element of array
2. Swap with the first element of array
3. Repeat with the rest of the array, looking for the second smallest element and swapping with the second element

Selection Sort Pseudocode

A is the name of the array

for i in range(len(A)-1):
	i_min = i 
	for j in range(i+1, len(A)): # 1. Find smallest element
		if A[j] < A[i_min]:
			i_min = j
			
	A[i_min], A[i] = A[i], A[i_min] # 2. Swap

Time Complexity

This algorithm is bad because no matter the case, even when the array is sorted, we need to go through every element twice.

• Best Case Sort: $O(n^2)$
• Average Case Sort: $O(n^2)$
• Worst Case Sort: $O(n^2)$

Space Complexity

• Worst Case: $O(1)$

Better algorithms:

• Insertion Sort