-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathinsertion-sort.py
55 lines (48 loc) · 1.6 KB
/
insertion-sort.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# Insertion Sort
# 🟢 Easy
#
# https://www.algoexpert.io/questions/insertion-sort
#
# Tags: Sorting
import timeit
from typing import List
# The problem asks us to implement this naive sorting algorithm.
#
# Time complexity: O(n^2) - Nested loops that iterate over n elements.
# Space complexity; O(1) - Only extra constant space.
class Naive:
def insertionSort(self, array: List[int]) -> List[int]:
# Start sorting from index i to the end.
for i in range(1, len(array)):
# Check value pairs starting at the last on the sorted
# section and moving back to the first two.
for j in range(i, 0, -1):
if array[j] < array[j - 1]:
array[j], array[j - 1] = array[j - 1], array[j]
return array
def test():
executors = [
Naive,
]
tests = [
[[1], [1]],
[[1, 2], [1, 2]],
[[8, 5, 2, 9, 5, 6, 3], [2, 3, 5, 5, 6, 8, 9]],
]
for executor in executors:
start = timeit.default_timer()
for _ in range(1):
for col, t in enumerate(tests):
sol = executor()
result = sol.insertionSort(t[0])
exp = t[1]
assert result == exp, (
f"\033[93m» {result} <> {exp}\033[91m for"
+ f" test {col} using \033[1m{executor.__name__}"
)
stop = timeit.default_timer()
used = str(round(stop - start, 5))
cols = "{0:20}{1:10}{2:10}"
res = cols.format(executor.__name__, used, "seconds")
print(f"\033[92m» {res}\033[0m")
test()