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

44 lines (35 loc) · 904 Bytes

"""

Author: OMKAR PATHAK

Created On: 31st July 2017

- Best = Average = O(n log(n))

- Worst = O(n ^ 2)

"""

import inspect

def sort(_list):

"""

quick_sort algorithm

:param _list: list of integers to sort

:return: sorted list

"""

if len(_list) <= 1:

return list(_list)

pivot = _list[len(_list) // 2]

left = [x for x in _list if x < pivot]

middle = [x for x in _list if x == pivot]

right = [x for x in _list if x > pivot]

return sort(left) + middle + sort(right)

# TODO: Are these necessary?

def time_complexities():

"""

Return information on functions

time complexity

:return: string

"""

return '''Best Case: O(nlogn), Average Case: O(nlogn), Worst Case: O(n ^ 2)'''

def get_code():

"""

easily retrieve the source code

of the sort function

:return: source code

"""

return inspect.getsource(sort)

Expand file tree