Run Code  | API  | Code Wall  | Misc  | Feedback  | Login  | Theme  | Privacy  | Patreon 

Lesson5-

#python 3.5.2
import time

# 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
               
N = 1
alist = [26,54,93,17,77,31]*N # length = 6
start = time.time() # start counting time
sortList = selectionSort(alist)
end = time.time() # stop counting time
print (end-start)

 run  | edit  | history  | help 0