forked from OmkarPathak/pygorithm
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathshell_sort.py
More file actions
28 lines (23 loc) · 774 Bytes
/
shell_sort.py
File metadata and controls
28 lines (23 loc) · 774 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
# Author: OMKAR PATHAK
# Created On: 31st July 2017
# Best Case O(n logn); Average Case O(depends on gap sequence); Worst Case O(n^2)
# shell sort algorithm
def sort(List):
gap = len(List) // 2
while gap > 0:
for i in range(gap, len(List)):
currentItem = List[i]
j = i
while j >= gap and List[j - gap] > currentItem:
List[j] = List[j - gap]
j -= gap
List[j] = currentItem
gap //= 2
return List
# time complexities
def time_complexities():
return '''Best Case: O(nlogn), Average Case: O(depends on gap sequence), Worst Case: O(n)'''
# easily retrieve the source code of the sort function
def get_code():
import inspect
return inspect.getsource(sort)