Python Projects for Beginners a ten-Week Bootcamp Approach to Python Programming

Battle of the Algorithms

One of the most obvious ways to test time complexity is to run two algorithms against each other. This will allow us to really see the power behind an efficient algorithm. We’re going to test Bubble Sort against another sorting algorithm called Insertion Sort. Although Insertion Sort isn’t the most efficient algorithm when sorting, we’ll find out that it’s still much more powerful than Bubble Sort. Let’s go ahead and write out the two sorting algorithms within the first cell:

1| # testing bubble sort vs. insertion sort 3| def bubbleSort(aList):
4| for i in range( len(aList) ):
5| switched = False 6| for j in range( len(aList) – 1 ):
7| if aList[ j ] > aList[ j + 1 ]:
8| aList[ j ], aList[ j + 1 ] = aList[ j + 1 ], aList[ j ]
9| switched = True 10| if switched == False:
11| break
12| return aList 14| def insertionSort(aList):
15| for i in range( 1, len(aList) ):
16| if aList[ i ] < aList[ i – 1 ]:
17| for j in range( i, 0, -1 ):
18| if aList[ j ] < aList[ j – 1 ]:
19| aList[ j ], aList[ j + 1 ] = aList [ j + 1 ], aList[ j ] 20| else:
21| break
22| return aList

Go ahead and run the cell. Now that we’ve defined the two functions we need to call, let’s set up some random data to be sorted and set up a timer like we did in the previous section:

1| # calling bubble sort and insertino sort to test time complexity
2| from random import randint
4| nums = [ randint(0, 100) for x in range(5000) ]
6| start_time = time.time( ) # tracking time bubble sort
7| bubbleSort(nums)
8| end_time = time.time( ) – start_time
9| print( "Elapsed time for Bubble Sort: { }".format(end_time) )
11| start_time = time.time( ) # tracking time insertion sort
12| insertionSort(nums)
13| end_time = time.time( ) – start_time
14| print( "Elapsed time for Insertion Sort: { }".format(end_time) )

Go ahead and run the cell. It’s not even a contest. Insertion Sort is a more efficient algorithm than its counterpart. Although both use the concept of a double for loop, Bubble Sort’s steps are much more inefficient because it starts at the front of the list each time. It’s always important to keep time complexity in mind when designing your program and algorithms. If you’re ever unsure what’s best to use, try testing it like we have here.