#/usr/bin/python3
# ===================================================================
# my attempt at a bubble sort
#
# During each pass through the list the largest value "sinks" to
# the bottom of the list and the smaller values "bubble" toward
# the top of the list. The list is then shortened (by 1) and the
# new list processed. If no values have been swapped during a pass
# the list is sorted and the function returns. If the list length
# becomes too short the list is sorted and the function returns.
# ===================================================================
import time
import random
from itertools import repeat
def BubbleSort(x):
k = len(x) # starting list length
while k > 1: # enough entries in the list to sort?
##print('[k=%d] %s' % (k,str(x[0:k])))
swapped = False # values swapped flag
i = 0 # starting i index
j = i+1 # starting j index
# bubble the greatest value to the bottom of the list
while j < k:
if x[i] > x[j]: # swap values?
tmp = x[j]
x[j] = x[i]
x[i] = tmp
swapped = True # values swapped
i += 1
j += 1
if not swapped: # any values swapped?
break # no, we are done
k -= 1 # reduce list length
return
if __name__ == "__main__":
# test lists
#x = []
#for i in range(0,10):
# x.append(random.randint(0,100))
#x = []
#x = [32]
#x = [400,300]
#x = [1,2,3,4,5,6,7,8,9]
#x = [9,8,7,6,5,4,3,2,1]
x = [ 9,9,8,7,6,5,4,4,3,2,1 ]
print("Test list before " + str(x))
start = time.time()
for _ in repeat(None,40000): # do it a lot of times
#xx = x.copy() # copy test list (python3 only)
xx = list(x) # copy test list
BubbleSort(xx) # sort copy of test list
stop = time.time()
print("test list sorted " + str(xx))
print("test list after " + str(x))
print("elapsed time %f" % (stop-start))