"""
for ini = 1 to ⌊𝑛/2⌋
    fim = 𝑛 − ini + 1 # fim
    min = ini
    max = ini
    for 𝑖 = ini to fim
        if 𝐴[𝑖] < 𝐴[min]
            min = 𝑖
        if 𝐴[𝑖] > 𝐴[max]
            max = 𝑖
    swap(𝐴[ini], 𝐴[min])
    if max == ini
        max = min
    swap(𝐴[fim], 𝐴[max])


n = 9
A = [5, 7, 6, 1, 2, 4, 3, 9, 8]

ini = 1, fim = 9, min = 1, max = 9
A = [1,     | 7, 6, 5, 2, 4, 3, 8,  | 9]

ini = 2, fim = 8, min = 2, max = 8
A = [1, 2,  | 6, 5, 7, 4, 3,    |  8, 9]

ini = 3, fim = 7, min = 3, max = 7
A = [1, 2, 3,   | 5, 7, 4, 6,    | 8, 9]
A = [1, 2, 3,   | 5, 6, 4,    | 7, 8, 9]
"""

def borderSort(array):
    mostMinCount, mostMaxCount, mostMaxIniCount = 0,0,0
    minCount, maxCount, maxIniCount = 0,0,0
    n = len(array)
    for ini in range(0, (n // 2)+1):
        fim = n - ini - 1
        min = ini
        max = ini
        for i in range(ini, fim + 1):
            if array[i] < array[min]:
                min = i
                minCount+=1
            if array[i] > array[max]:
                max = i
                maxCount+=1
        temp = array[min]
        array[min] = array[ini]
        array[ini] = temp
        print(array, "\n-\n")
        if max == ini:
            max = min
            maxIniCount+=1

        temp = array[max]
        array[max] = array[fim]
        array[fim] = temp

        # Aqui é só para fazer a contagem de quantas vezes os if's entraram
        print(array, "\n---\n")
        if minCount > mostMinCount:
            mostMinCount = minCount
        if maxCount > mostMaxCount:
            mostMaxCount = maxCount
        if mostMaxIniCount > maxIniCount:
            mostMaxIniCount = maxIniCount
    print("Min: ", mostMinCount,"\nMax: ", mostMaxCount,"\nIni=Max: ", mostMaxIniCount,"\nTOTAL: ",mostMaxIniCount+mostMaxCount+mostMinCount)
    return array


# print("Ordenando por Border-Sort\n")
array = [9,8,7,6,5,4,3,2,1,0] # 25
# array = [0,1,2,3,4,5,6,7,8,9] # 25
#array = [9,8,7,6,5,0,1,2,3,4] #19
#array = [5,4,3,2,1,0,9,8,7,6] #21
# array = [1,1,1,1,1,1,1,1,1,1] #0
# array = [5,5,5,5,5,5,5,5,5,5,5] #0
# array = [9,8,7,6,9,8,7,6] #0
#array = [1,2,1,2,1,2,1,2,1,2] #5
# array = [9,0,8,1,7,2,6,3,5,4] #10
# array = [0,9,1,8,2,7,3,6,4,5] #10
print(array, "\n---\n")
array = borderSort(array)
print("Array Ordenado:\n",array)