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”

Python - Bubble sort vs Merge sort; some code provided by FutureLearn / Raspberry Pi Foundation — Python – Bubble sort vs Merge sort; some code provided by FutureLearn / Raspberry Pi Foundation

2 Python - Bubble sort vs Merge sort; some code provided by FutureLearn / Raspberry Pi Foundation — 2 Python – Bubble sort vs Merge sort; some code provided by FutureLearn / Raspberry Pi Foundation

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)

Python - Merge VS Bubble methods with an already sorted list — Python – Merge VS Bubble methods with an already sorted list

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)

102_3_10_geektechstuff_sorted_with_some_out_of_seq — Python – Making a sorted list a little out of order

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)

Python - Sorted method — Python – Sorted method

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

Programming 102 Week 3 Tasks (Python)

Related

Published by Geek_Dude

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