# sorting
#
# Name:
import random
def make_a_list(size):
alist = []
biggest = size * 5
for i in range(size):
alist.append(random.randint(1, biggest))
return(alist)
def swap(alist, position1, position2):
"""swap the element in position1 with the one in position2 in the list alist"""
tmp = alist[position1]
alist[position1] = alist[position2]
alist[position2] = tmp
# Q1: Why do I need tmp? Why can't I just use:
# alist[position1] = alist[position2]
# alist[position2] = alist[position1]
def bubblesort(alist):
n = len(alist) - 1
did_a_swap = True
# Q2 what does the variable did_a_swap do? and what is the purpose
# of this while loop?
while did_a_swap:
did_a_swap = False
for i in range(n):
# Q3: explain this if statement
if alist[i] > alist[i + 1]:
swap(alist, i, i + 1)
# Q4: why do I set did_a_swap to true?
did_a_swap = True
def selectionsort(alist):
# start by finding the smallest number and work up.
for i in range(len(alist) - 1):
# so i is the position I will fill with the smallest
# number I find so far.
smallestSoFar = 999999999
positionOfSmallest = -1
for j in range(i, len(alist)):
# check if I found the smallest so far,
# if so, update the 2 variables
# now I found the smallest number
# I will swap it with the number at position i
# using the swap function above
swap(alist, i, positionOfSmallest)
def merge(alist, blist):
result = []
a = 0
b = 0
alen = len(alist)
blen = len(blist)
while a < alen and b < blen:
print("TODO")
if a < alen:
print("TODO")
else:
print("TODO")
return result
# uncomment out the following code to test merge.
# it should return
# [2, 9, 14, 16, 21, 22, 23, 24, 24, 27, 34, 34, 35, 38, 42, 46, 50,
# 51, 57, 58, 60, 61, 65, 66, 66, 67, 68, 75, 76, 77, 81, 81, 83, 85,
# 86, 88, 89, 91, 96, 98]
#lista = [9, 23, 24, 24, 34, 34, 35, 38, 42, 58, 60, 61, 67, 68, 76, 77, 81, 83, 86, 96]
#listb = [2, 14, 16, 21, 22, 27, 46, 50, 51, 57, 65, 66, 66, 75, 81, 85, 88, 89, 91, 98]
#print(merge(lista, listb))
# uncomment out the following code to test random lists in merge.
#lista = make_a_list(30)
#listb = make_a_list(25)
#bubblesort(lista)
#bubblesort(listb)
#print (merge(lista, listb))
def mergesort(alist):
# 1. if alist has only one element it is already sorted
# so return it
# 2. divide alist into two parts: left and right
# 3. call mergesort on left and right to get them sorted
# 4. now merge the sorted left and right together
# using the merge function above
# 5. and return the merged list.
print("TODO")
# example of how to time a function
# import cProfile
# cProfile.run('bubblesort(make_a_list(5000))')