-
Notifications
You must be signed in to change notification settings - Fork 636
Expand file tree
/
Copy pathP26_InsertionSort.py
More file actions
25 lines (20 loc) · 817 Bytes
/
P26_InsertionSort.py
File metadata and controls
25 lines (20 loc) · 817 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
#Author: OMKAR PATHAK
#This program shows an example of insertion sort using Python
# Insertion sort is good for collections that are very small
# or nearly sorted. Otherwise it's not a good sorting algorithm:
# it moves data around too much. Each time an insertion is made,
# all elements in a greater position are shifted.
# Best O(n); Average O(n^2); Worst O(n^2)
def insertionSort(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
if __name__ == '__main__':
List = [3, 4, 2, 6, 5, 7, 1, 9]
print('Sorted List:',insertionSort(List))