Quiz 4 Review B: Questions

Q4rB.1.

In your own words, describe how selection sort works.

Q4rB.2.

Complete the following method so that it uses selection sort to reorder the elements of its parameter list.

def selection_sort(data):

Q4rB.3.

In your own words, describe how insertion sort works.

Quiz 4 Review B: Solutions

Q4rB.1.

Given a list to sort, we first determine where the smallest value is in the list; we do this starting with the assumption that the first value (index 0) is the smallest, but then we go through each subsequent index to see whether the value at that index is less than the value we were thinking is smallest — and when it is, we update our assumed smallest to be the element at that index. Once locating the smallest element, and we swap it into the first location (index 0) in the list.

Then we repeat the process to find the smallest element in the second and subsequent locations of the list (indices 1 and higher); we swap that into the second location (index 1).

We continue repeating this process starting from the third location; and again for the fourth; and so on, until the list segment for which we are determining the smallest contains just one element.

Q4rB.2.

def selection_sort(data):

    for i in range(len(data) - 1):

        mini = i

        for j in range(i + 1, len(data)):

            if data[j] < data[mini]:

                mini = j

        data[i], data[mini] = data[mini], data[i]

Q4rB.3.

We observe that the first element, considered alone, is already in sorted order. We then insert successive elements in the list into this already-sorted segment of the list, each time shifting values back to make room for the element we are inserting. Once the already-sorted segment includes all list elements, we are done.