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])) # 15Selitys: 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]$