Why is my code to compare the runtime of two different sorting algorithms displaying the same numbers multiple times?

user_14757943 0
Viewed 91

I am trying to compare the running time between bubble sort and insert sort. It does this on 10 different lists with the first list containing 1000 numbers and then increases by 1000 each time.

The following loop creates the lists and times each list using both methods. It is SUPPOSED to assign each time to a list, and then to another list because the goal is to have a list of lists that I can later use as data points for a graph. Assume sort_1 and sort_2 are implemented sorting algorithms

counter = 0
empty_list = []
list_limit = 1000
data_point = []
list_of_data_points = []

while list_limit <= 10000:

    while counter < list_limit:
        num = random.randint(1, 10000)
        empty_list.append(num)
        counter += 1
    
    copied_list = list(empty_list)
    bubble_time = sort_1(copied_list)
    insert_time = sort_2(copied_list)

    data_point.clear()
    data_point.append(bubble_time)
    data_point.append(insert_time)
    list_of_data_points.append(data_point)
    print(list_of_data_points)
    list_limit += 1000

Now the reason print(list_of_data_points) is in the loop is because this is where the error is happening. Everything else is working perfectly, but this is what I get when I run the loop:

[[0.10695279999999996, 0.00023099999999998122]]
[[0.43489919999999993, 0.0004752999999999563], [0.43489919999999993, 0.0004752999999999563]]
[[0.9825091000000001, 0.0007314000000000487], [0.9825091000000001, 0.0007314000000000487], [0.9825091000000001, 0.0007314000000000487]]

As you can see, it will calculate the times just fine. However, each time it is supposed to add the data_point into the list, it seems to be clearing the current list and making each data point the same value.

I am confused because I thought the append() method was supposed to just add the current data point list into the larger list of lists (i.e. list_of_data_points. Is there something wrong with my while loop or is this a list issue that I am misunderstanding?

sorting python performance
3 Answers

Just replace

data_point.clear()

by

data_point = []

When you do:

a = [1,2,3]
b = a

the assignment to b copies the reference to the list, not the actual list.

So, if you latter change a, such as a[0] = 100, b will become [100,2,3], as well.

When doing data_point = [], you a creating a new list with the new values.

So, in the first time, list_of_data_points will be: [first_list_under_the_name_of_data_point]

The second time: [first_list_under_the_name_of_data_point, second_list_under_the_name_of_data_point]

And so on.

On the other hand, when you do data_point.clear(), you do not create a new list, so, in the first time:

[first_list_under_the_name_of_data_point]

The second time:

[first_list_under_the_name_of_data_point_but_with_updated_values, first_list_under_the_name_of_data_point_but_with_updated_values]

user_57852500

data_point gets cleared, then you append the bubble_time and the insert_time, bubble_time is the same as insert_time but the sort method is a different one.

that means you append the same data 2 time (i guess you just sort it in a different way), but hey if that's what you want, you can do this:

data_point = [bubble_time, insert_time] #replace datapoint.clear() with this and don't use the append method

i am not that good with english but i am glad if that helped, if i got something wrong feel free to write a comment so i can help as much as i can

Admin1

Try that:

import random
import numpy as np
    
data_point = []
    
for i in range(10):
    num_size = (i+1) * 1000
    random_numbers = list(np.random.randint(low = 1, high = 1000, size=num_size))
    bubble_time = len(random_numbers)
    insert_time = len(random_numbers)
    data_point.insert(i, [bubble_time, insert_time])

Maybe, it would be even better for you to work with a dictionary in this case:

import random
import numpy as np
    
data_dict = {}
    
for i in range(10):
    num_size = (i+1) * 1000
    random_numbers = list(np.random.randint(low = 1, high = 1000, size=num_size))
    bubble_time = sum(random_numbers)
    insert_time = len(random_numbers)
    data_dict[num_size]= [bubble_time, insert_time]
print(data_dict)

# Output of print(data_dict)
{'1000': [527103, 1000], '2000': [994513, 2000], '3000': [1490553, 3000], '4000': [2007809, 4000], '5000': [2539145, 5000], '6000': [3039272, 6000], '7000': [3501393, 7000], '8000': [4011519, 8000], '9000': [4526147, 9000], '10000': [5053926, 10000]}

I chose len() and sum() in order to have two substitutes for your functions.

Working with this dict enables you to plot the data_points with the correct labels easily, for example:

import matplotlib.pyplot as plt

lists = sorted(data_dict.items()) # sorted by key, return a list of tuples
x, y = zip(*lists) # unpack a list of pairs into two tuples
plt.plot(x, [i[0] for i in y])
plt.plot(x, [i[1] for i in y])
plt.show()

This might seem a little bit overwhelming; I just wanted to give you a piece of concise, working code. If you are interested into certain aspects/lines/methods that don't make sense to you just ask me!

user_104812690
Related