Puolijärjestäminen

Annettuna on lista, jossa on jokin lukujen $1 \dots n$ permutaatio, jossa $n$ on parillinen. Saat jokaisella siirrolla vaihtaa kaksi vierekkäistä lukua keskenään. Tehtäväsi on järjestää lista siten, että listan puolivälistä katsottuna kaikki alkupuolen luvut ovat pienempiä kuin kaikki loppupuolen luvut. Mikä on pienin määrä siirtoja?

Voit olettaa, että $n$ on enintään $10^5$. Tavoitteena on, että algoritmin aikavaativuus on $O(n)$ tai $O(n \log n)$.

Toteuta tiedostoon semisort.py funktio solve, joka antaa pienimmän siirtojen määrän.

def solve(t):
    # TODO

if __name__ == "__main__":
    print(solve([2, 1, 4, 3])) # 0
    print(solve([5, 3, 4, 1, 6, 2])) # 6
    print(solve([6, 5, 4, 3, 2, 1])) # 9
    print(solve([10, 1, 9, 2, 8, 3, 7, 4, 6, 5])) # 15

Selitys: Listalla $[2,1,4,3]$ alkupuoliskon luvut eli $2$ ja $1$ ovat jo valmiiksi kaikki pienempiä kuin loppupuolen luvut $4$ ja $3$. Listalla $[5, 3, 4, 1, 6, 2]$ tarvitaan ainakin $6$ siirtoa. Tässä on yksi optimaalinen ratkaisu: $[5, 3, 4, 1, 6, 2]$ $\rightarrow$ $[5, 3, 4, 1, 2, 6]$ $\rightarrow$ $[3, 5, 4, 1, 2, 6]$ $\rightarrow$ $[3, 5, 1, 4, 2, 6]$ $\rightarrow$ $[3, 1, 5, 4, 2, 6]$ $\rightarrow$ $[3, 1, 5, 2, 4, 6]$ $\rightarrow$ $[3, 1, 2, 5, 4, 6]$