# Sort function

• Input: a list of values
• Operation: sort the list
• Output: a sorted list of values
``````

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)

``````
``````

Running test with a list of 10 items.
CPU times: user 17 µs, sys: 1 µs, total: 18 µs
Wall time: 21 µs

Running test with a list of 100 items.
CPU times: user 603 µs, sys: 1 µs, total: 604 µs
Wall time: 608 µs

Running test with a list of 1000 items.
CPU times: user 8.1 ms, sys: 109 µs, total: 8.21 ms
Wall time: 8.13 ms

``````
``````

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)

``````
``````

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

``````