Sorting

Question 1

Selection sort algorithm

Answer 1

For each element in list:
FInd smallest element
Swap it with the element
repeat with unsorted part

Question 2

Selection sort Runtime efficiency

Answer 2

Worst/Best/Average case: O(n^2)

Question 3

Bubble sort algorithm

Answer 3

Starting on the left: For each pair of elements in the list, swap them if they are not in order. The largest element is bubbled to position N
Start on the left again, and bubble the second largest element to position N-1.
Keep doing this until there are no longer any swaps

Question 4

Bubble sort Runtime efficiency

Answer 4

WOrst/Average: O(n^2) 2 nested loops

Best case: O(n) for almost sorted list

Question 5

Insertion sort

Answer 5

Set a marker for the sorted section after the first element.
Select the first unsorted element.
Swap other elements to the right to create the correct position and shift the unsorted element
Advance the marker to the right by one element.
Do this until unsorted section is empty.