Որոշել ամենաօպտիմալ ալգորիթմը
Ձեզ տրված է
n ամբողջ թվերի մի շարք, և խնդիրը պահանջում է պարզել, թե առաջարկված երեք ալգորիթմներից (Selection, Insertion կամ Bubble sort) որն է աշխատում ամենաօպտիմալ կերպով՝ ելնելով տեսակավորման ընթացքում կատարվող տարրերի տեղերով փոխելու քանակից։ Այլ կերպ ասած, դուք պետք է հաշվեք, թե յուրաքանչյուր ալգորիթմ քանի անգամ տարրերը տեղերով կփոխի աշխատանքի ընթացքում, ապա ելքում տպել այդ փոփոխությունների քանակը։Մուտք
Մուտքի առաջին տողում տրված է
n ամբողջ թիվը (1 ≤ n ≤ )։Հաջորդ տողում տրված են
n ամբողջ թվեր ( ≤ ≤ )՝ բաժանված բացատներով։Ելք
Ծրագիրը պետք է տպի (հետևյալ հերթականությամբ)
Insertion, Selection և Bubble ալգորիթմների անվանումները, ինչպես նաև ամեն մի ալգորիթմի կողմից կատարվող գործողությունների ընդհանուր քանակը։Օրինակներ
Մուտք | Ելք |
4
1 4 3 2 | Insertion - 3
Selection - 1
Bubble - 3 |
Հուշում
Օգտագործեք նախորդ առաջադրանքներում կիրառված տեսակավորման ալգորիթմները, որպեսզի հաշվեք տարրերի տեղերով փոխելու իրական քանակը:
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB