Lista sisältää luvut jossakin järjestyksessä. Saat jokaisella siirrolla vaihtaa kaksi vierekkäistä lukua keskenään. Tehtäväsi on järjestää lista siten, että kaikki alkupuoliskon luvut ovat pienempiä kuin kaikki loppupuoliskon luvut. Mikä on pienin mahdollinen määrä siirtoja?
Algoritmin aikavaativuuden tulee olla . Voit olettaa, että on parillinen kaikissa testeissä.
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 alkupuoliskon luvut eli ja ovat jo valmiiksi kaikki pienempiä kuin loppupuolen luvut ja . Listalla tarvitaan ainakin siirtoa. Tässä on yksi optimaalinen ratkaisu: