MENU
import numpy as np

def bubble_sort(score):
    l = len(score)
    for i in range(l - 1):
        for j in range(l - i - 1):
            if score[j] > score[j + 1]:
                score[j], score[j + 1] = score[j + 1], score[j]
    return score

'''
def quick_sort(L, left, right):
    if left > right:
        return
    key = L[left]
    i, j = left, right
    while i < j:
        while L[j] >= key and i < j:
            j = j - 1
        while L[i] <= key and i < j:
            i = i + 1
        if i < j:
            L[i], L[j] = L[j], L[i]
    L[left], L[i] = L[i], L[left]

    quick_sort(L, left, i - 1)
    quick_sort(L, i + 1, right)
    return L
'''


def quick_sort(L):

    def _q_sort(L, left, right):
        if left < right:
            pivot = _partition(L, left, right)

            _q_sort(L, left, pivot - 1)
            _q_sort(L, pivot + 1, right)
        return L

    def _partition(L, left, right):
        pivotkey = L[left]

        while left < right:
            while left < right and L[right] >= pivotkey:
                right -= 1
            L[left] = L[right]
            while left < right and L[left] <= pivotkey:
                left += 1
            L[right] = L[left]

        L[left] = pivotkey
        return left

    return _q_sort(L, 0, len(L) - 1)



def merge_sort(L):

    def _merge(left, right):
        i, j = 0, 0
        result = []
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                result.append(left[i])
                i = i + 1
            else:
                result.append(right[j])
                j = j + 1
        result += left[i:]
        result += right[j:]
        return result

    if len(L) < 2:
        return L
    mid = len(L) // 2
    left = merge_sort(L[:mid])
    right = merge_sort(L[mid:])
    return _merge(left, right)


# def merge(left, right):
#     i, j = 0, 0
#     result = []
#     while i < len(left) and j < len(right):
#         if left[i] < right[j]:
#             result.append(left[i])
#             i = i + 1
#         else:
#             result.append(right[j])
#             j = j + 1
#     result += left[i:]
#     result += right[j:]
#     return result


def shell_sort(L):
    gap = len(L) // 2
    while gap:
        for i in range(gap, len(L), gap):
            for j in range(i, 0, -gap):
                if L[j - gap] > L[j]:
                    L[j - gap], L[j] = L[j], L[j - gap]
                else:
                    break
        gap //= 2
    return L





if __name__ == '__main__':

    # print(bubble_sort(score))
    # print(merge_sort(score))
    # print(shell_sort(score))
    # print(quick_sort(score, 0, len(score)-1))
    L = np.random.randint(0, 100, size=[20])
    print(L)
    print(quick_sort(L))