Question

Let us consider the easiest sorting algorithms – Maxsort. It works as follows: Find the largest key, say max, in the unsorted section of array (initially the whole array) and then interchange max with the element in the last position in the unsorted section. Now max is considered part of the sorted section consisting of larger keys at the end of the array. It is no longer in the unsorted section. Repeat this until the whole array is sorted. a) Write an algorithm for Maxsort assuming an array E contains n elements to be sorted, with indexes 0, 1,…,n-1. b) How many comparisons of keys does Maxsort do in the worst case and on average? Submit source code, test cases, results, and the answers to part (b)

Answer 1

count = 0

for x in range(len(array)):

if count == Len(array) -1:

break

max = max(array[:-1 - count])

count += 1

if array.index(max) == -1:

break

else:

hold = array[-1]

array[-1] = max

array[array.index(max)] = hold

Step-by-step explanation:

The python program is an implementation of a maxsort. The for loop iterates over the array, getting the maximum number for each reduced array and swaps it with the corresponding last items.