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]