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

## Published by Geek_Dude

I'm a tech enthusiast that enjoys science, science fiction, comics and video games - pretty much anything geeky.
View all posts by Geek_Dude

## One thought on “Programming 102 Week 3 Tasks (Python)”

Comments are closed.