In [1]:
'''
Running test with a list of 10 items.
CPU times: user 17 µs, sys: 0 ns, total: 17 µs
Wall time: 20 µs
Running test with a list of 100 items.
CPU times: user 388 µs, sys: 1 µs, total: 389 µs
Wall time: 391 µs
Running test with a list of 1000 items.
CPU times: user 6.21 ms, sys: 167 µs, total: 6.37 ms
Wall time: 6.31 ms
'''
from numpy import random as rd
def sort_list(list_to_sort):
if not isinstance(list_to_sort, list): # Not a list error
raise NameError('Error: arg shouls be a list.')
if len(list_to_sort) < 2: # empty or 1-element list
return list_to_sort
new_list = []
new_list.append(list_to_sort[0])
for i in list_to_sort[1:]:
if i > new_list[-1]: # if biggest number, append it and continue
new_list.append(i)
continue
elif len(new_list) < 10: # new list (still) small, doesn't need optimisation
for j in range(0, len(new_list)):
if i <= new_list[j]: # if smaller or equal than element at index j, insert before j
new_list.insert(j, i)
break
else: # search for the middle, ...
left_boundary = 0
right_boundary = len(new_list)-1
positionFound = False
while positionFound == False:
# mid ~= median of new list
mid = int(left_boundary + (right_boundary - left_boundary) / 2)
if right_boundary - left_boundary < 2:
new_list.insert(right_boundary, i)
positionFound = True
break
elif i == new_list[mid]:
new_list.insert(mid, i)
positionFound = True
break
elif i > new_list[mid]: # => narrow to the right
left_boundary = mid
elif i < new_list[mid]: # => narrow to the left
right_boundary = mid
return new_list
sample_lists = []
ranges = [10, 100, 1000]
for r in ranges:
sample_lists.append((rd.rand(1, r)*100)[0].tolist())
for sample in sample_lists:
print("\nRunning test with a list of", len(sample), "items.")
%time sort_list(sample)
In [1]:
# really slow sort function, bad for long lists - just to give a try
'''
Running test with a list of 10 items.
CPU times: user 17 µs, sys: 0 ns, total: 17 µs
Wall time: 20 µs
Running test with a list of 100 items.
CPU times: user 1.54 ms, sys: 1 µs, total: 1.54 ms
Wall time: 1.54 ms
Running test with a list of 1000 items.
CPU times: user 182 ms, sys: 239 µs, total: 182 ms
Wall time: 182 ms
'''
from numpy import random as rd
def sort_list(list_to_sort):
sort_completed = False
while sort_completed == False:
sort_completed = True
for idx in range(0, len(list_to_sort)-1):
if list_to_sort[idx] > list_to_sort[idx+1]:
sort_completed = False
list_to_sort[idx], list_to_sort[idx+1] = list_to_sort[idx+1], list_to_sort[idx]
sample_lists = []
ranges = [10, 100, 1000]
for r in ranges:
sample_lists.append((rd.rand(1, r)*100)[0].tolist())
for sample in sample_lists:
print("\nRunning test with a list of", len(sample), "items.")
%time sort_list(sample)