Cserélgetős rendezés

A rendezés fontos szerepet játszik az informatikában. Szinte minden probléma hatékonyabban oldható meg, ha rendezett adatokkal dolgozunk. Van pár kitűnő rendező algoritmus, amelyek már elérték az n · log n-es alsó bonyolultsági korlátot. Ebben a feladatban egy új rendezési módszerről lesz szó. Ennél a módszernél csak egy művelet (a csere) használható, amellyel két szomszédos elemet tudunk megcserélni egymással. Ha utánagondolunk, láthatjuk, hogy bármilyen számsorozatot rendezhetünk így.

Egész számok adott sorozatát szeretnénk növekvő sorrendbe rendezni a fenti módszerrel. Meg kell határoznod a rendezéshez szükséges cserék minimális számát. Az 1, 2, 3 sorozat rendezéséhez például egyetlen csere sem szükséges, míg a 2, 3, 1 sorozat rendezéséhez legalább 2 cserére van szükség.

A bemenet specifikációja

A bemenet számos tesztesetet tartalmaz. Minden teszteset egy N pozitív egész számmal kezdődik (N ≤ 1000). A következő néhány sorban N egész szám szerepel, ezek alkotják a rendezendő sorozatot. A bemenetet az állományvégjel (EOF) zárja.

A kimenet specifikációja

Minden tesztesetre egy sort kell a kimenetre írni, amely a

„Minimum exchange operations : M”

szöveget tartalmazza, ahol M a sorozat rendezéséhez szükséges cserék minimális száma.

Példa bemenet

1. 3
2. 1 2 3
3. 3
4. 2 3 1

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. Minimum exchange operations : 0
2. Minimum exchange operations : 2

letöltés szöveges állományként