forked from OmkarPathak/pygorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathinsertion_sort.py
More file actions
31 lines (25 loc) · 742 Bytes
/
insertion_sort.py
File metadata and controls
31 lines (25 loc) · 742 Bytes
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
# Author: OMKAR PATHAK
# Created On: 31st July 2017
# Best O(n); Average O(n^2); Worst O(n^2)
# insertion sort algorithm
def sort(List):
for i in range(1, len(List)):
currentNumber = List[i]
for j in range(i - 1, -1, -1):
if List[j] > currentNumber :
List[j], List[j + 1] = List[j + 1], List[j]
else:
List[j + 1] = currentNumber
break
return List
# time complexities
def bestcase_complexity():
return 'O(n)'
def averagecase_complexity():
return 'O(n ^ 2)'
def worstcase_complexity():
return 'O(n ^ 2)'
# easily retrieve the source code of the sort function
def get_code():
import inspect
return inspect.getsource(sort)