Skip to content

Instantly share code, notes, and snippets.

@tirinox
Created January 28, 2019 15:30
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save tirinox/e21dad629a68d6585037cde43b1414a8 to your computer and use it in GitHub Desktop.
Save tirinox/e21dad629a68d6585037cde43b1414a8 to your computer and use it in GitHub Desktop.
# this is Radix sort prove of O(n) time complexity
import random
import matplotlib.pyplot as plt
import time
def radix_sort(a_list, radix=10):
max_length_achieved = False
tmp, placement = -1, 1
while not max_length_achieved:
# declare and initialize buckets
buckets = [[] for _ in range(radix)]
# split a_list between lists
max_length_achieved = True
for i in a_list:
tmp = i // placement
buckets[tmp % radix].append(i)
if max_length_achieved and tmp > 0:
max_length_achieved = False
# empty lists into aList array
a = 0
for b in range(radix):
buck = buckets[b]
for i in buck:
a_list[a] = i
a += 1
# move to next digit
placement *= radix
def gen_data(data_size):
return [random.randint(0, 10000) for _ in range(data_size)]
def test_radix_sort(start_size=10, mult_size=1.5, steps=20, tries_number=100):
x, y = [], []
data_size = start_size
for _ in range(steps):
t0 = time.time()
for _ in range(tries_number):
data = gen_data(data_size)
radix_sort(data)
t1 = time.time()
time_per_try = (t1 - t0) / tries_number
x.append(data_size)
y.append(time_per_try)
print('Data size: {}'.format(data_size))
print('Time: {} sec\n'.format(time_per_try))
data_size = int(data_size * mult_size)
plt.plot(x, y, '--bo')
plt.xlabel('Number of items')
plt.ylabel('Time, sec')
plt.show()
if __name__ == '__main__':
test_radix_sort()
@tirinox
Copy link
Author

tirinox commented Jan 28, 2019

Plot:
screen shot 2019-01-28 at 18 28 45

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment