QUESTION:

Consider the incomplete function below:

def my_selection_sort(a_list):  
    for I in range(len(a)_list - 1, 0, -1):
    ...

Complete the my_selection_sort() function above so that it returns the total number of elements, comparisons and swaps needed to sort the numbers list. The function must return these 3 values as a tuple.

Consider the following:

• A list with reverse order numbers: # of elements = 8, # of comparisons = 28 (1 2 3 4 5 6 7), # of swaps = 7
• A list with sorted order numbers: # of elements = 8, # of comparisons = 28 (1 2 3 4 5 6 7), # of swaps = 7

MY CODE:

def my_selection_sort(a_list):
    length = len(a_list)
    swaps = 0
    comparisons = 0
    for i in range(len(a_list)-1,0,-1):
        lowest_value_index = i
        for j in range(len(a_list)-1,i 1,-1):
            comparisons  = 1
            if a_list[j] < a_list[lowest_value_index]:
                lowest_value_index = j
        swaps  = 1
        a_list[i],a_list[lowest_value_index] = a_list[lowest_value_index],a_list[i]
    return (length,comparisons,swaps)

TEST:

Test 1:

nums = [6]
res = my_selection_sort(nums)
print('Length: {} Comparisons: {} Swaps: {}'.format(res[0], res[1], res[2]))

Test 2:

nums = [70, 48, 54, 79, 33]
res = my_selection_sort(nums)
print('Length: {} Comparisons: {} Swaps: {}'.format(res[0], res[1], res[2]))
    

EXPECTED OUTPUT:

Test 1:

Length: 1 Comparisons: 0 Swaps: 0

Test 2:

Length: 5 Comparisons: 10 Swaps: 4

ACTUAL OUTPUT:

Test 1:

Length: 1 Comparisons: 0 Swaps: 0

Test 2:

Length: 5 Comparisons: 3 Swaps: 4

CodePudding user response：

A different and simple strategy. You don't need to even apply the for loops. In selection sort, the comparisons and swapping's are fixed always. There are mathematical formulas for both that you can implement in python:

Assume length of the list = n

1. Total no of comparisons: Summation from 1 till n-1

2. Total number of swaps = n-1

   Special Case : n = 0 and n=1 (You can check for this in if statements)

   Other Cases : n > 1 , for example n = 8 , Comparisons = 1 2 3 4 5 6 7 = 28, Swaps = 8-1 = 7.

   for example n = 5, Comparisons = 1 2 3 4 = 10, Swaps = 5-1 = 4.