def bubble_sort(A):
    for iteration in range(len(A)):
        for i in range(iteration):
            if A[i] > A[i + 1]:
                A[i], A[i + 1] = A[i + 1], A[i]

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key 

def quick_sort(L, U, A):
    if L >= U: return
    if A[L] < A[U]:
        A[L], A[U] = A[U], A[L]
    P = A[U]
    B = L
    T = U
    while B < T:
        A[B], A[T] = A[T], A[B]
        B += 1
        T -= 1
        while A[B] < P: B += 1
        while A[T] > P: T -= 1
    A[L], A[T] = A[T], A[L]
    quick_sort(L, T - 1, A)
    quick_sort(T + 1, U, A)

def lomuto_quick_sort(L, U, Data):
    if L >= U: return
    pivot = Data[L]
    l = L
    for i in range(L + 1, U + 1):
        if Data[i] < pivot:
            Data[l + 1], Data[i] = Data[i], Data[l + 1]
            l += 1
    Data[L], Data[l] = Data[l], Data[L]
    lomuto_quick_sort(L, l - 1, Data)
    lomuto_quick_sort(l + 1, U, Data)