SelectionSort Algorithm using Python

Question

I am a rookie and I need help optimizing this SelectionSort() algorithm which I have tried using Python.

def selectionSort(arr,an):
    for lastUnsortedInteger in range(an-1,0,-1):
        largest = arr.index(max(arr[0:lastUnsortedInteger+1]))
        swap(arr,largest,lastUnsortedInteger)
    return arr

def swap(arr,ai,aj):
    arr[ai],arr[aj] = arr[aj],arr[ai]

if __name__ == '__main__':
    an = int(input())
    arr = list(map(int,input().strip().split()))
    selectionSort(arr,an)
    print("Sorted using SelectionSort():\n")
    for ai in arr:
        print(arr)

Answer 1

Seems like you already incorporated a few of the suggestions from back when this was on StackOverflow, e.g. changing the inner loop to max. However, you do so in a very inefficient way:

• you create a slice of the list, O(n) time and space
• you get the max of that slice, O(n) time
• you get the index of that element, O(n) time

Instead, you can get the max of the range of indices, using a key function for comparing the actual values at those indices:

largest = max(range(0, lastUnsortedInteger+1), key=arr.__getitem__)

This way, this step has only O(n) time (for Python 3).

Some other points:

• the an parameter (the length of the array/list) is not necessary, you can use len
• in my opinion, it is a bit simpler looping from first to last index, and using min instead of max accordingly
• since the swap is a single line now and only used once, we could inline this directly into the sorting function
• the function modifies the list in-place, so no return is needed and might lead users to expect that the function does not modify the list but create a sorted copy instead
• technically, arr is not an array but a list, and you might prefer snake_case to camelCase (it's "Python" after all)

My version:

def selection_sort(lst):
    for i in range(len(lst) - 1):
        k = min(range(i, len(lst)), key=lst.__getitem__)
        lst[i], lst[k] = lst[k], lst[i]

Needless to say, for all practical purposes you should just use sorted or sort.