# bubble sort: make repeated passes through the list, # moving the greatest number to the end; each time through, # the length of the list sorted shrinks by 1 (because the # end of the list is sorted) # # we print the current state of the list each time through # # also count (and print) the number of comparisons and # exchanges # # Matt Bishop MHI 289I, Fall 2025 # # # set this to False to print *only* the original (unsorted) # and the final (sorted) lists # set to True to print the intermediate (partially sorted) lists # showintermediate = False # # we will generate a list of this many numbers # and then shuffle them 7 times using shuffle() # from the random module # import random nnums = 20 # # now set which sorts to do # default (to do them all) is set after args processedf # do_bubblesort = False do_mergesort = False do_quicksort = False do_selectsort = False # # now get the options # import getopt import sys try: optlist, args = getopt.getopt(sys.argv[1:], "bimn:qs") except getopt.GetoptError as msg: print("Unknown option:", msg) sys.exit(2) # # process them # for opt in optlist: if '-b' == opt[0]: # do bubblesort do_bubblesort = True continue elif '-i' == opt[0]: # show each step, and number of swaps at each showintermediate = True continue if '-m' == opt[0]: # do mergesort do_mergesort = True continue elif '-n' == opt[0]: # change number of integers to be sorted try: # takes a positive integer as an argument nnums = int(opt[1]) except: # not a number print("'n' option requires an integer number\n") sys.exit(2) if nnums < 1: # not positive printf("'n' option requires a positive number\n") sys.exit(2) elif '-q' == opt[0]: # do quicksort do_quicksort = True continue elif '-s' == opt[0]: # do selectsort do_selectsort = True continue else: # should never get here, but ... print("Unknown option:", opt) sys.exit(2) if not (do_bubblesort or do_mergesort or do_quicksort or do_selectsort): do_bubblesort = True do_mergesort = True do_quicksort = True do_selectsort = True # # this is the bubble sort routine # def bubblesort(numlist): # we track the number of comparisons and swaps (exchanges) global swaps, compares # get length of list n = len(numlist) # initially we assume something has to be swapped swapped = True theseswaps = 0 # continue looping until no numbers are swapped while swapped: # okay, no swaps on this pass -- yet swapped = False # go through the list, moving the highest number to the end # you swap the numbers in pairs, hence the "bubbling" for i in range(1, n): # another comparison compares += 1 # if true, the greater number is first, so we # need to exchange the numbers to move the greater # one closer to the end if numlist[i-1] > numlist[i]: # a swap will occur theseswaps += 1 swaps += 1 swapped = True # and here is the swap numlist[i-1], numlist[i] = numlist[i], numlist[i-1] # print the current state of the list (visually see the sorting) if showintermediate: print("swaps: %2d" % theseswaps, numlist) theseswaps = 0 # # this is the selection sort routine # def selectsort(numlist): # we track the number of comparisons and swaps (exchanges) global swaps, compares # get length of list n = len(numlist) theseswaps = 0 # you will make a number of passes through the list, # each time starting one element further on, as the # previous pass put the smallest element in the list first for low in range(0, n): # assume the smallest element comes first min = numlist[low] minindex = low # now find index of the smallest element for i in range(low+1, n): # doing another comparison compares += 1 # found something smaller; may be the smallest # make note of the index and value, which is\ # the new minimum if numlist[i] < min: min = numlist[i] minindex = i # minindex is now the index of the smallest element # of the list, so exchange it and the first element # of the list if minindex != low: theseswaps += 1 swaps += 1 numlist[low], numlist[minindex] = numlist[minindex], numlist[low] # print the current state of the list (visually see the sorting) if showintermediate: print("swaps: %2d" % theseswaps, numlist) theseswaps = 0 # # this is the merge sort routine # # if the list is 1 item, you are done # otherwise, split the list in two parts, sort them independently # (using mergesort), then merge the two lists # def mergesort(numlist): # we track the number of comparisons and swaps (exchanges) global copies, compares # if the list is one number, you're done if len(numlist) <= 1: # print the current state of the list (visually see the sorting) if showintermediate: print("copies:%2d" % copies, numlist) return # find the midpoint of the list mid = len(numlist) // 2 # split the list into 2 parts, left and right # note midpoint in kept in the right half left = numlist[:mid] right = numlist[mid:] # now sort each half mergesort(left) mergesort(right) # here, i indexes left, j indexes right, and # k indexes numlist # left and right are merged; their sorted merge # is put in numlist # start everything at the beginning of the lists i = j = k = 0 # this part does the merge # compare first element of left with first element # of right; put the smaller into numlist and advance # the appropriate indices while i < len(left) and j < len(right): # we do a compare and a copy here compares += 1 copies += 1 # if left is smaller or equal, put it into numlist if left[i] <= right[j]: numlist[k] = left[i] i += 1 k += 1 # if right is smaller, put it into numlist elif left[i] > right[j]: numlist[k] = right[j] j += 1 k += 1 # at this point, either i or j is at the end so # only one of the following while loops has its # body executed while i < len(left): # a copy copies += 1 # add next element of left to the end of numlist numlist[k] = left[i] i += 1 k += 1 while j < len(right): # a copy copies += 1 # add next element of left to the end of numlist numlist[k] = right[j] j += 1 k += 1 # print the current state of the list (visually see the sorting) if showintermediate: print("copies:%2d" % copies, numlist) # # this is quicksort # # pick the pivot; this partitions the list into two parts # the list is the part of numlist with index low to index high # def partition(numlist, low, high): global theseswaps, swaps, compares theseswaps = 0 # pick the pivot pivot = numlist[high] # now go through the list; at the end of this loop, # i is the index where the pivot goes; so everything # less than the pivot goes to before that index i = low for j in range(low, high+1): # a comparison with the pivot compares += 1 if numlist[j] < pivot: # now swap this with what's at index i # and advance index i by 1, to keep what # is before the index to where the pivot # will go swaps += 1 theseswaps += 1 numlist[i], numlist[j] = numlist[j], numlist[i] i += 1 # now put the pivot in the right place # remember the pivot is at the end (index high) swaps += 1 theseswaps += 1 numlist[i], numlist[high] = numlist[high], numlist[i] # print the current state of the list? if showintermediate: print("pivot %2d:" % pivot) # and return the index of the pivot return i # the actual sort routine def quicksort(numlist, low, high): global swaps, compares, theseswaps # print the current state of the list? if showintermediate: print("swaps: %2d" % theseswaps, numlist[low:high+1]) if low < high: p = partition(numlist, low, high) quicksort(numlist, low, p - 1) quicksort(numlist, p + 1, high) # print the current state of the list? if showintermediate: print("swaps: %2d" % theseswaps, numlist[low:high+1]) def qsort(numlist): quicksort(numlist, 0, len(numlist)-1) # # generate a list of numbers # we just put the first nnums number into a list (0 .. nnums-1) # and then shuffle it 7 times # def loadnums(): # generate the list; use range and convert it numlist = list(range(nnums)) # now shuffle 7 times; in theory, this makes # it as random as possible for i in range(0, 7): random.shuffle(numlist) # and return the list! return numlist # # this puts it all together # def main(): # we need to print these global compares, swaps, copies, theseswaps # get the list # if it's empty, quit (just in case :) nums = loadnums() if nums == []: return # now the sorts: if do_bubblesort: swaps = 0 compares = 0 x = nums[:] print("Unsorted:", x) bubblesort(x) print(" Sorted:", x) print(f"Bubblesort took {compares} comparisons and {swaps} swaps") if do_selectsort: swaps = 0 compares = 0 x = nums[:] print("Unsorted:", x) selectsort(x) print(" Sorted:", x) print(f"Selectsort took {compares} comparisons and {swaps} swaps") if do_mergesort: copies = 0 compares = 0 x = nums[:] print("Unsorted:", x) mergesort(x) print(" Sorted:", x) print(f"Mergesort took {compares} comparisons and {copies} copyings") if do_quicksort: swaps = theseswaps = 0 compares = 0 x = nums[:] print("Unsorted:", x) qsort(x) print(" Sorted:", x) print(f"Quicksort took {compares} comparisons and {swaps} swaps") # # and we're off! # main()