pygorithm/pygorithm/sorting/shell_sort.py at master · OmkarPathak/pygorithm · GitHub

History

50 lines (40 loc) · 1.01 KB

Raw

"""

Author: OMKAR PATHAK

Created On: 31st July 2017

- Best Case O(n log n)

- Average Case O(depends on gap sequence)

- Worst Case O(n^2)

"""

import inspect

def sort(_list):

"""

Shell sort algorithm

:param _list: list of integers to sort

:return: sorted list

"""

gap = len(_list) // 2

while gap > 0:

for i in range(gap, len(_list)):

current_item = _list[i]

j = i

while j >= gap and _list[j - gap] > current_item:

_list[j] = _list[j - gap]

j -= gap

_list[j] = current_item

gap //= 2

return _list

# TODO: Are these necessary?

def time_complexities():

"""

Return information on functions

time complexity

:return: string

"""

return "Best Case: O(nlogn), Average Case: O(depends on gap sequence), Worst Case: O(n ^ 2)"

def get_code():

"""

easily retrieve the source code

of the sort function

:return: source code

"""

return inspect.getsource(sort)

pygorithm/pygorithm/sorting/shell_sort.py at master · OmkarPathak/pygorithm · GitHub

Expand file tree

Breadcrumbs

shell_sort.py

Latest commit

History

Breadcrumbs

shell_sort.py

File metadata and controls