In this assignment, you will conduct a set of experiments using basic sorting algorithms.

Please see the description of the assignment in the following file: a6.pdf

Source files:

bubbleSort.py

'''

Description: Sorts myList in ascending order using a bubble sort.

File: bubbleSort.py

'''

import random

import time

def bubbleSort(myList):

"""Rearranges the items in myList so they are in ascending order"""

for lastUnsortedIndex in range(len(myList)-1,0,-1):

# scan the Before sorting part at the beginning of myList

for testIndex in range(lastUnsortedIndex):

# if we find two adjacent items out of order, switch them

if myList[testIndex] > myList[testIndex+1]:

temp = myList[testIndex]

myList[testIndex] = myList[testIndex+1]

myList[testIndex+1] = temp

def shuffle(myList):

for fromIndex in range(len(myList)):

toIndex = random.randint(0,len(myList)-1)

temp = myList[fromIndex]

myList[fromIndex] = myList[toIndex]

myList[toIndex] = temp

def main():

print("bubbleSort Timings")

aList = list(range(10000,0,-1))

print( " Before sorting list: ",end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

start = time.clock()

bubbleSort(aList)

end = time.clock()

print( "sorted list:", end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

print( "Time to sort",end - start,"seconds")

print( " Before sorting list: ", end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

start = time.clock()

bubbleSort(aList)

end = time.clock()

print( "sorted list:", end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

print( "Time to sort",end - start,"seconds")

aList = list(range(10000,0,-1))

shuffle(aList)

print( " Before sorting (random) list: ",end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

start = time.clock()

bubbleSort(aList)

end = time.clock()

print( "sorted list:",end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

print( "Time to sort",end - start,"seconds")

aList = list(range(10000,0,-1))

shuffle(aList)

print( " Before sorting (random) list: ",end='')

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

start = time.clock()

bubbleSort(aList)

end = time.clock()

print( "sorted list:",end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

print( "Time to sort",end - start,"seconds")

input("Hit -key to end")

if __name__ == "__main__": main()

bubbleSortB.py

'''

Description: Sorts myList in ascending order using a bubble sort.

The bubble sort stops early if no items are exchanged when scanning

the unsorted part of the list.

File: bubbleSortB.py

'''

import random

import time

def bubbleSort(myList):

"""Rearranges the items in myList so they are in ascending order"""

for lastUnsortedIndex in range(len(myList)-1,0,-1):

alreadySorted = True

# scan the unsorted part at the beginning of myList

for testIndex in range(lastUnsortedIndex):

# if we find two adjacent items out of order, switch them

if myList[testIndex] > myList[testIndex+1]:

temp = myList[testIndex]

myList[testIndex] = myList[testIndex+1]

myList[testIndex+1] = temp

alreadySorted = False

if alreadySorted:

return

def shuffle(myList):

for fromIndex in range(len(myList)):

toIndex = random.randint(0,len(myList)-1)

temp = myList[fromIndex]

myList[fromIndex] = myList[toIndex]

myList[toIndex] = temp

def main():

print("bubbleSortB Timings")

aList = list(range(10000,0,-1))

print( " Before sorting list: ",end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

start = time.clock()

bubbleSort(aList)

end = time.clock()

print( "sorted list:", end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

print( "Time to sort",end - start,"seconds")

print( " Before sorting list: ", end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

start = time.clock()

bubbleSort(aList)

end = time.clock()

print( "sorted list:", end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

print( "Time to sort",end - start,"seconds")

aList = list(range(10000,0,-1))

shuffle(aList)

print( " Before sorting (random) list: ",end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

start = time.clock()

bubbleSort(aList)

end = time.clock()

print( "sorted list:",end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

print( "Time to sort",end - start,"seconds")

aList = list(range(10000,0,-1))

shuffle(aList)

print( " Before sorting (random) list: ",end='')

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

start = time.clock()

bubbleSort(aList)

end = time.clock()

print( "sorted list:",end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

print( "Time to sort",end - start,"seconds")

input("Hit -key to end")

if __name__ == "__main__": main()

insertionSort.py

'''

Description: Sorts myList in ascending order using an insertion sort.

File: insertionSort.py

'''

import random

import time

def insertionSort(myList):

"""Rearranges the items in myList so they are in ascending order"""

for firstUnsortedIndex in range(1,len(myList)):

itemToInsert = myList[firstUnsortedIndex]

# Scan the sorted part from the right side

# Shift items to the right while you have not scanned past the

left

# end of the list and you have not found the spot to insert

testIndex = firstUnsortedIndex - 1

while testIndex >= 0 and myList[testIndex] > itemToInsert:

myList[testIndex+1] = myList[testIndex]

testIndex = testIndex - 1

# Insert the itemToInsert at the correct spot

myList[testIndex + 1] = itemToInsert

def shuffle(myList):

for fromIndex in range(len(myList)):

toIndex = random.randint(0,len(myList)-1)

temp = myList[fromIndex]

myList[fromIndex] = myList[toIndex]

myList[toIndex] = temp

def main():

print("insertionSort Timings")

aList = list(range(10000,0,-1))

print( " Before sorting list: ",end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

start = time.clock()

insertionSort(aList)

end = time.clock()

print( "sorted list:", end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

print( "Time to sort",end - start,"seconds")

print( " Before sorting list: ", end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

start = time.clock()

insertionSort(aList)

end = time.clock()

print( "sorted list:", end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

print( "Time to sort",end - start,"seconds")

aList = list(range(10000,0,-1))

shuffle(aList)

print( " Before sorting (random) list: ",end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

start = time.clock()

insertionSort(aList)

end = time.clock()

print( "sorted list:",end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

print( "Time to sort",end - start,"seconds")

aList = list(range(10000,0,-1))

shuffle(aList)

print( " Before sorting (random) list: ",end='')

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

start = time.clock()

insertionSort(aList)

end = time.clock()

print( "sorted list:",end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

print( "Time to sort",end - start,"seconds")

input("Hit -key to end")

if __name__ == "__main__": main()

selectionSort.py

'''

Description: Sorts myList in ascending order using an selection sort.

File: selectionSort.py

'''

import random

import time

def selectionSort(aList):

for lastUnsortedIndex in range(len(aList)-1, 0, -1):

# look for maximum item in unsorted part of list

# Assume maximum is the first item in the unsorted part

maxIndex = 0

# scan the unsorted part of the list to correct the assumption

for testIndex in range(1, lastUnsortedIndex+1):

if aList[testIndex] > aList[maxIndex]:

maxIndex = testIndex

# exchange the items at maxIndex and firstUnsortedIndex

temp = aList[lastUnsortedIndex]

aList[lastUnsortedIndex] = aList[maxIndex]

aList[maxIndex] = temp

def shuffle(myList):

for fromIndex in range(len(myList)):

toIndex = random.randint(0,len(myList)-1)

temp = myList[fromIndex]

myList[fromIndex] = myList[toIndex]

myList[toIndex] = temp

def main():

print("selectionSort Timings")

aList = list(range(10000,0,-1))

print( " Before sorting list: ",end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

start = time.clock()

selectionSort(aList)

end = time.clock()

print( "sorted list:", end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

print( "Time to sort",end - start,"seconds")

print( " Before sorting list: ", end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

start = time.clock()

selectionSort(aList)

end = time.clock()

print( "sorted list:", end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

print( "Time to sort",end - start,"seconds")

aList = list(range(10000,0,-1))

shuffle(aList)

print( " Before sorting (random) list: ",end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

start = time.clock()

selectionSort(aList)

end = time.clock()

print( "sorted list:",end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

print( "Time to sort",end - start,"seconds")

aList = list(range(10000,0,-1))

shuffle(aList)

print( " Before sorting (random) list: ",end='')

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

start = time.clock()

selectionSort(aList)

end = time.clock()

print( "sorted list:",end="")

print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-

1])

print( "Time to sort",end - start,"seconds")

input("Hit -key to end")

if __name__ == "__main__": main()

quickSort.py

"""

File: quickSort.py

Recursive implementation of quickSort

"""

import random

import time

def quickSort(aList):

quickSortHelper(aList, 0, len(aList) - 1)

def quickSortHelper(aList, left, right):

if left

pivotLocation = partition(aList, left, right)

quickSortHelper(aList, left, pivotLocation - 1)

quickSortHelper(aList, pivotLocation + 1, right)

def partition(aList, left, right):

# Find the pivot and exchange it with the last item

middle = (left + right) // 2

pivot = aList[middle]

aList[middle] = aList[right]

aList[right] = pivot

# Set boundary point to first position

boundary = left

# Move items less than pivot to the left

for index in range(left, right):

if aList[index]

temp = aList[index]

aList[index] = aList[boundary]

aList[boundary] = temp

boundary += 1

# Exchange the pivot item and the boundary item

temp = aList[boundary]

aList[boundary] = aList[right]

aList[right] = temp

return boundary

mergeSort.py

"""

File: mergeSort.py

Recursive implementation of mergeSort

"""

import random

import time

def mergeSort(alist):

if len(alist)>1:

mid = len(alist)//2

lefthalf = alist[:mid]

righthalf = alist[mid:]

mergeSort(lefthalf)

mergeSort(righthalf)

i=0

j=0

k=0

while i

if lefthalf[i]

alist[k]=lefthalf[i]

i=i+1

else:

alist[k]=righthalf[j]

j=j+1

k=k+1

while i

alist[k]=lefthalf[i]

i=i+1

k=k+1

while j

alist[k]=righthalf[j]

j=j+1

k=k+1

WHAT TO SUBMIT: Submit a report in Word or PDF format, including the tables with timings and answers to all questions. Also include some information about the machine you used to run the tests (processor type and speed, amount of memory, operating system...).

Assignment 6 Objectives: To experiment with simple sorts: selection, bubble, and insertionsorts To experiment with advanced sorts: quick, and mergesorts To start the assignment: Download the source files provided in the assignment page. The files contain the following sorting algorithms, which all sort in ascending order (i.e., from smallest to largest): 1. bubbleSort.py - bubble sort code which does not check if it can stopearly. 2. bubbleSortB.py - bubble sort code which stops early if no swapping is needed during a scan of the unsorted part. 3. insertionSort.py - the insertion sort 4. selectionSort.py - the selection sort 5. mergeSort.py the merge sort 6. quicksort.py the quick sort Files 1 to 4 run their sorting algorithm several times with different initial orderings of 10,000 list items. The initial orderings of items are: descending order, ascending order, random order, and random order again to check for consistence. Files 5 and 6 contain the sorting algorithm, but do not contain the main() function that tests the algorithm. You must add the main() function all you need to do is copy this function from one of the other files and change the name of the sort algorithm being called. You also need to copy the function shuffle(). Part 1: Simple Sort Algorithms Complete the following timings by running each program. Timings of Sorting Algorithms on 10,000 items (seconds) Sorting algorithm Initial Ordering of Items Descending Ascending Random order 1 Random order 2 bubbleSort.py bubbleSortB.py insertionSort.py selectionSort.py mergeSort.py quicksort.py Page 2 of 4 Part 2: Advanced Sort Algorithms Merge Sort The general idea of Merge Sort is as follows. Assume you have n items to sort. 1. Split the unsorted part in half to get two smaller sorting problems of size about n/2. 2. Solve both smaller problem recursively using mergesort. 3. Merge the solution to the smaller problems together to solve the original sorting problem of size n. Update your mergeSort.py to test the algorithm with larger lists of random numbers as specified in the following table. Complete the timings: Timings of Merge Sort (seconds) List size Initial Ordering of Items Descending Ascending Random order 1 Random order 2 100,000 200,000 400,000 Page 3 of 4 Quick Sort The general idea of Quick sort is as follows. Assume n items tosort. 1. Select a random item in the unsorted part as the pivot 2. Rearrange (called partitioning) the unsorted items such that: 3. Quick sort the unsorted part to the left of the pivot 4. Quick sort the unsorted part to the right of the pivot Update your quickSort.py to test the algorithm with larger lists of random numbers as specified in the following table. Complete the timings to get a feel for the speed of quicksort. Timings of Quick Sort (seconds) List size Initial Ordering of Items Descending Ascending Random order 1 Random order 2 100,000 200,000 400,000 Part 3: Questions Study the code and answer the following questions about the sorting algorithms: a) Why does the bubbleSort algorithm take less time on the ascending ordered list than the descending ordered list? b) Why does the bubbleSortB algorithm take A LOT less time on the ascending ordered list than the descending ordered list? c) Why does the insertionSort algorithm take A LOT less time on the ascending ordered list than the descending ordered list? d) Why does the insertionSort algorithm take less time on the descending ordered list than the bubbleSort algorithm on the descending ordered list? e) Why does the selectionSort algorithm take less time on the descending ordered list than the insertionSort algorithm on the descending ordered list? f) Both advanced sorting algorithms are O (n log2 n) on initially random data. Why do you suppose quick sort is the fastest advanced sort on random items? Page 4 of 4 Part 4: Bubble Sort (again) Write a variation of bubble sortthat: sorts in descending order (largest to smallest) builds the sorted part on the left-hand side of the list, i.e., Your code does NOT need to stop early if a scan of the unsorted part has no swaps. Name your function bubbleSortC Implement and test your bubbleSortC code and complete the following. Run the test 3 times. Timings of Sorting Algorithms on 10,000 items (seconds) Sorting algorithm Initial Ordering of Items Descending Ascending Random order 1 Random order 2 bubbleSortC.py, run 1 bubbleSortC.py, run 2 bubbleSortC.py, run 3 a) How does the above algorithm compare with the original bubbleSort.py?