bubble_sort_test.py

# ===================================================================
# my attempt at a bubble sort
#
# During each pass through the list the greatest value is
# "bubbled" to the bottom 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 botton 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))