Although it is still officially “week 1” of Programming 102: Think Like A Computer Scientist I’m onto week 3 as I’ve been enjoying the course and like the little programming tasks/challenges.
3.5 Implementing Bubble Sort
Task: “Now you’re going to write a bubble sort program in Python”
3.10 Merge Or Bubble, Which Is Best?
Task: ” Compare Merge sorting against Bubble Sorting”
Q. How does the size of the unsorted list affect the speed of the algorithms?
Using a list containing random integers between 1 and 100000.
A list of 5 random integers:
A list of 10 random integers:
A list of 100 random integers:
A list of 1000 random integers:
A. Merge becomes more efficient than Bubble as the list size increases.
Q. Do the algorithms perform differently on very small lists?
A. Yes, Bubble is faster when dealing with smaller lists.
Q. How do the algorithms perform when they are given an already sorted list?
A. I used a new list of 1 to 999 by modifying some of the Python:
And the results show that in this instance, the Bubble method completes faster than the Merge method.
Q. What happens if the lists are nearly sorted?
A. I again modified the list so that a few values where out of sequence:
Q. What happens when the lists are sorted in reverse order?
A. I used the list.reverse() function to reverse the list.
3.11 Comparing Efficiency
Task: “Can you add a Timsort function to your earlier program comparing the completion times of algorithms?”
This was quite easy as it just meant using the built in Python method of sorting:
Python sort took: