# 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 ECS 36A, Winter 2019
#
#
# 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 = True
#
# 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
# set the number of swaps and comparisons to 0
swaps = 0
compares = 0
#
# 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
# continue looping until no numbers are swapped
while swapped:
# print the current state of the list (visually see the sorting)
if showintermediate:
print(" ", numlist)
# 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
swaps += 1
swapped = True
# and here is the swap
numlist[i-1], numlist[i] = numlist[i], numlist[i-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
# get the list
# if it's empty, quit (just in case :)
nums = loadnums()
if nums == []:
return
# print the initial list
print("Unsorted:", nums)
# sort the list
bubblesort(nums)
# print the sorted list and the relevant statistics
print(" Sorted:", nums)
print("This took {} comparisons and {} swaps".format(compares, swaps))
#
# and we're off!
#
main()