CSC108H Fall 2022 Worksheet: Selection Sort Analysis
1. In the list below, i passes of the selection sort algorithm have been completed, and the double bar separates
the sorted part of the list from the unsorted part.
i
L sorted unsorted
(a) get_index_of_smallest(L, i) works by comparing pairs of items from the unsorted section. If
there are n items in L, when get_index_of_smallest(L, i) is executed, how many pairs of items
are compared? (Your answer should be a formula involving n and i.)
But our loop actually
guesses distancebtwn starts at it 1 so
in i and of iterations is
n
(b) For function get_index_of_smallest(L, i), is there a worst case and a best case?
N Cait 17
i 1 it runs n n 1 1 timesO
best case n
o 1
timetimes
worst case i o it runs n
n t times
(c) In terms of the number of items in the unsorted section, does get_index_of_smallest have constant
running time, linear running time, quadratic running time, or some other running time?
(a) constant (b) linear (c) quadratic (d) something else
(d) In function selection_sort, the first time that function get_index_of_smallest is called, i is
0; the second time, i is 1; and so on. What value does i have the last time that function
get_index_of_smallest is called?
I n I in the last iteration
(e) For the call selection_sort(L), write a formula expressing how many comparisons are made
during all the calls to get_index_of_smallest.
i o n fi n 1 comparisons
i I n CI ti n 2 comparisons
i 2 n 2 1 2 3 comparisons fomin
n 1 ti comparisons
ENGIE
is n 1 n
sum 0 1 2 t n 3 ca 2 Ca D
(f) In terms of the length of the list, does selection_sort have constant running time, linear running
time, quadratic running time, or some other running time?
(a) constant (b) linear
O
(c) quadratic (d) something else
1. In the list below, i passes of the selection sort algorithm have been completed, and the double bar separates
the sorted part of the list from the unsorted part.
i
L sorted unsorted
(a) get_index_of_smallest(L, i) works by comparing pairs of items from the unsorted section. If
there are n items in L, when get_index_of_smallest(L, i) is executed, how many pairs of items
are compared? (Your answer should be a formula involving n and i.)
But our loop actually
guesses distancebtwn starts at it 1 so
in i and of iterations is
n
(b) For function get_index_of_smallest(L, i), is there a worst case and a best case?
N Cait 17
i 1 it runs n n 1 1 timesO
best case n
o 1
timetimes
worst case i o it runs n
n t times
(c) In terms of the number of items in the unsorted section, does get_index_of_smallest have constant
running time, linear running time, quadratic running time, or some other running time?
(a) constant (b) linear (c) quadratic (d) something else
(d) In function selection_sort, the first time that function get_index_of_smallest is called, i is
0; the second time, i is 1; and so on. What value does i have the last time that function
get_index_of_smallest is called?
I n I in the last iteration
(e) For the call selection_sort(L), write a formula expressing how many comparisons are made
during all the calls to get_index_of_smallest.
i o n fi n 1 comparisons
i I n CI ti n 2 comparisons
i 2 n 2 1 2 3 comparisons fomin
n 1 ti comparisons
ENGIE
is n 1 n
sum 0 1 2 t n 3 ca 2 Ca D
(f) In terms of the length of the list, does selection_sort have constant running time, linear running
time, quadratic running time, or some other running time?
(a) constant (b) linear
O
(c) quadratic (d) something else
