Programming 102 Week 3 Tasks (Python)

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”

my_list = [5,9,5,8,1,3]
my_2nd_list = [100,99,44,77,1000,3,6,78,93]
def bubble_sort(list_to_sort):
sorted= list_to_sort[:]
sort_flag = True
while sort_flag ==True:
sort_flag = False
for i inrange(len(sorted)-1):
ifsorted[i] >sorted[i+1]:
sorted[i],sorted[i+1] =sorted[i+1],sorted[i]
sort_flag = True
return(print(sorted))
bubble_sort(my_list)
bubble_sort(my_2nd_list)

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:

Merge took:
0.008249939000961604
Bubble took:
0.0019174459994246718

A list of 10 random integers:

Merge took:
0.01677630500125815
Bubble took:
0.006191377000504872

A list of 100 random integers:

Merge took:
0.21991850700214854
Bubble took:
0.31299215400213143

A list of 1000 random integers:

Merge took:
1.7861479469975166
Bubble took:
36.700165668997215

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:

list_to_sort=[]
for x in range(1,1000):
list_to_sort.append(x)
print(list_to_sort)

And the results show that in this instance, the Bubble method completes faster than the Merge method.

Merge took:
1.5132878329968662
Bubble took:
0.032028548997914186

Q. What happens if the lists are nearly sorted?

A. I again modified the list so that a few values where out of sequence:

list_to_sort=[]
for x in range(1,1000):
list_to_sort.append(x)
list_to_sort[2]=list_to_sort[89]
list_to_sort[1]=list_to_sort[998]
print(list_to_sort)

Merge took:
1.6626074119994882
Bubble took:
0.1568922320002457

Q. What happens when the lists are sorted in reverse order?

A. I used the list.reverse() function to reverse the list.

list_to_sort=[]
for x in range(1,1000):
list_to_sort.append(x)
list_to_sort2 = list_to_sort.reverse
print(list_to_sort2)
Merge took:
1.4028495110032964
Bubble took:
0.031765455001732334

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:

ts = lambda: sorted(list_to_sort)
And making the “list_to_sort” variable a list of 1000 random integers between 1 and 100000. Sorted came out as the fastest:
Merge took:
1.8507144780014642
Bubble took:
38.15972470500128
Python sort took:
0.043297118001646595