def partition(arr, start, end):
    """Moving elements to left and right to pivot to make sure arr[pi] is at the right position
Input: 
    - arr: array to be sorted
    - start: start position/index
    - end: end position/index
Return: pi"""
    # ----_small-----start--------------------end-----------
    #----------------a[i]-------small---------a[i]----end--
    #----------------a[i]-------end(pivot)----a[i]---------
    # Return _small = positiion of Pivot = new position of end value
    _pi = arr[end] #pivot as last element
    _small = start - 1 # smaller index indicator (=0 at the start)
    for i in range(start, end):
        # run a loop for a whole array
        if arr[i] <= _pi:
            # Increase the index (room) for smaller value
            _small = _small+1
            # moving smaller values to the left by swapping
            arr[_small], arr[i] = arr[i], arr[_small]
    # Finally, moving elemet with pivot value (last one) to the middle (end of smaller)
    _small = _small+1
    arr[_small], arr[end] = arr[end], arr[_small]
    # return value
    return _small