Programming 102 Week 3 Tasks (Python)

Python Bubble Sort

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)
Python Bubble Sort
Python Bubble Sort

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

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

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.