Lesson 5, Python 3

Language: Layout:

#python 3.5.2

# Selection sort: You select the largest number, and take it all the way to the right

# Selection sort:      v-----------------------------------------v
# Example: [ 26, 54, {93}, 17, 77, 31] -> [26, 54, 31, 17, 77, {93}]
#                                   ^--------------^

#                              v----------------------------v
# Example: [ 26, 54, 31, 17, {77}, 93] -> [26, 54, 31, 17, 77, 93]

#                  v--------------------------------------v
# Example: [ 26, {54}, 31, {17}, 77, 93] -> [26, 17, 31, 54, 77, 93]
#                             ^------------------^

# Example: [ 1, 9, 4, 2, 5] -> [ 1, 5, 4, 2, 9]

# 1. Identify the 1-largest number
# 2. Swap with the number in [last - 0] position
#
#  - Identify the 2-largest number
#  - Swap with the number in [last-1] position

#    - Identify the 3-largest number
#    - Swap with the number in [last-2] position

# CODE range[0,10) : 0, 1, 2, ..., 9
def selectionSort(alist):
    length = len(alist) # -> 6
    for nLastPosition in range(length-1, 0, -1): 
        # nLastPosition -> 5 -> 4 -> 3 -> 2 -> 1
        # this loop goes from last position to first position
        # 1: identifying the maximum number [come back to this]
        maxIndex = 0
        for numIndex in range(0, nLastPosition+1):
            if alist[numIndex] > alist[maxIndex]:
                maxIndex = numIndex
        
        print ("Max number: ", alist[maxIndex])
        temp = alist[nLastPosition]
        alist[nLastPosition] = alist[maxIndex]
        alist[maxIndex] = temp
        print ("After swap: ", alist)
        print ()
    return alist
                
alist = [26,54,93,17,77,31] # length = 6

sortList = selectionSort(alist)
print (sortList)

[ + ] Show input
Absolute running time: 0.19 sec, cpu time: 0.16 sec, memory peak: 6 Mb, absolute service time: 0,2 sec