Question: Selection sort
Answer: a sorting algorithm that treats the input as two parts, a sorted part and an unsorted part, and repeatedly selects the proper next value to move from the unsorted part to the end of the sorted part.
==================================================
Question: Given list (9, 8, 7, 6, 5), what value will be in the 0th element after the first pass over the outer loop (i = 0)?
Answer: 5
==================================================
Question: Given list (9, 8, 7, 6, 5), how many swaps will occur during the first pass of the outer loop (i = 0)
Answer: 1
==================================================
Question: Given list (5, 9, 8, 7, 6) and i = 1, what will be the list after completing the second outer loop iteration? Type answer as: 1, 2, 3
Answer: 5, 6, 8, 7, 9
==================================================
Question: The selection sort algorithm runtime is
Answer: O(N^2)
==================================================
Question: If a list has N elements, the outer loop executes
Answer: N times
==================================================
Question: For each of those N outer loop executions, the inner loop executes an average of
Answer: N/2
==================================================
Question: So the total number of comparisons is proportional to
Answer: N⋅N/2 , or O(N^2)
==================================================
Question: Assuming each comparison takes 2 µs, how long will the selection sort algorithm take to sort a list of 50 elements?
Answer: 5000 µs
==================================================
Question: How many times longer will sorting a list of 20 elements take compared to sorting a list of 10 elements?
Answer: 4
==================================================
Question: How many times longer will sorting a list of 500 elements take compared to a list of 50 elements?
Answer: 100
==================================================