2.2 Introduction to Algorithms started from https://brilliant.org/courses/computer-science-algorithms/array-algorithms-2/insertion-sort-algo/1/

 started from https://brilliant.org/courses/computer-science-algorithms/array-algorithms-2/insertion-sort-algo/1/

Selection sort animations:

https://www.youtube.com/watch?v=n7eyTv2k_-k

#SELECTION sorting Algorithm

PSEUDO selection sort .

input: A, an array of numbers

for current from 0

to length of A - 2:

set minIndex to current

for i from current + 1

to length of A - 1:

if A[i] < A[minIndex]:

set minIndex to i

swap A[current]

and A[minIndex]

Comparing Algorithms

For both selection sort and insertion sort, we found that the average cost was pretty close to $$c⋅n2, where $n$ is the length of the array and $c$ is some constant value.

Question 1.

Imagine we're given an implementation of each of these sorting algorithms. We test their performance on many arrays of size 100 and find that, on average, insertion sort is ten times faster than selection sort.

Which algorithm should we expect will do better, on average, on arrays of size 10,000?

Insertion sort

Suppose that we tweak the implementations of these sorting algorithms and test on arrays of size 100 again. This time we find that selection sort is twice as fast as insertion sort.

Which should we expect will do better, on average, on arrays of size 10,000?

Insertion sort

Selection sort

a new sorting algorithm called mystery sort, which has a best-case, worst-case, and average-case cost of $15\cdot n^{3\mathrm{/}2}\mathrm{.}$

We test the implementation of mystery sort along with an implementation of selection sort on arrays of size 100, and find that mystery sort is five times faster.

Which should we expect will be faster on arrays of size 10,000?

Mystery sort

Selection sort

runtimes are in $O(n^2)$ and $O(n^{3\mathrm{/}2})$ (MYSTERY) is just as useful as knowing the precise number of comparisons that each algorithm makes.