Write a function SelSort(x) that performs a selection sort on a list of numbers.

Question

Write a function SelSort(x) that performs a selection sort on a list of numbers. Then generate random lists of numbers of lengths 10, 50, 100, 500, 1000, 5000, 10,000, and 50,000. Measure the time it takes to perform a sort, and make a table of sorting time as a function of list length. Use the following template as a starting point. def sel_sort(vals): for jj in range(0, len(vals)): for kk in range(jj + l, len(vals)): if: # Here you need to test if you have found a smaller value. # If you have found a smaller value, you need to swap entries in vals accordingly. return vals # Note, we never create a new array svals in a selection sort. Instead, we swap values around in vals directly. tstart = time() sel_sort(random.sample(range(50000), )) # You need to decide how many points to put in your list tend = time() ctime = tend-tstart print ctime

Explanation / Answer

from time import time
import random

#selection sort function. Returns sorted array
def sel_sort(vals):
    #for loop to iterate through the list
    for jj in range(0, len(vals)):
        positionOfMin=0
        for kk in range(jj+1, len(vals)):
            if vals[kk]<vals[positionOfMin]: #testing if found a smaller value
                positionOfMin = kk

        #swapping values
        temp = vals[jj]
        vals[jj] = vals[positionOfMin]
        vals[positionOfMin] = temp

    #returning the sorted list
    return vals

#all list lengths for which to test the function
vals_lengths = [10, 50, 100, 500, 1000, 5000, 10000, 50000]

#Will print a table of sorting time vs list length
print "Sorting Time --- List Length"
for vals_length in vals_lengths:
    tstart = time()
    sel_sort(random.sample(range(500000), vals_length))
    tend = time()
    ctime = tend-tstart
    print ctime, "    ", vals_length

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.