Bogosort

Մենք հաճախ ենք աշխատել ցուցակներ սորտավորելու (տեսակավորելու) հետ տարբեր խնդիրներում: Մենք օգտագործել ենք ներկառուցված ֆունկցիաներ՝ զանգվածների տեսակավորման համար: Սակայն, թե իրականում այդ ներկառուցված ֆունկցիաները ինչպես են աշխատում «կուլիսների հետևում», միշտ չէ որ պարզ է երևում: Այս գլուխում կանդրադառնանք ամենահայտնի տեսակավորման (սորտավորման) ալգորիթմներից մի քանիսին, որոնք կիրառվում են տարբեր իրավիճակներում՝ կախված դեպքից:
Առաջին ալգորիթմը, որի մասին կխոսենք, տեսակավորման ալգորիթմներից ամենաաբսուրդալն է։ Այն կոչվում է Bogosort: Այն իրական ծրագրերում երբեք չի կիրառվում, և դուք շուտով կհասկանաք, թե ինչու։
Ենթադրենք տրված է n թվերի շարք: Bogosort ալգորիթմը պատահականորեն խառնում է այդ թվերը, ապա ստուգում, արդյոք ստացված ցանկը դասավորված է ըստ աճման հերթականության, թե ոչ.
from random import shuffle

a = [3, 1, -2, 5, 6]            # Սկզբնական թվեր
while True:                     # կրկնել, մինչ զանգվածը կդասավորվի
    is_sorted = True
    for i in range(1, len(a)):  # ցիկլ՝ ստուգելու համար, արդյոք զանգվածը սորտավորված է
        if a[i] < a[i-1]:       # եթե հանդիպում ենք տարր, որը փոքր է նախորդից => զանգվածը սորտավորված չէ
            is_sorted = False   # փոփոխականին տալիս ենք False արժեքը և դադարեցնում ցիկլը
            break
    if is_sorted:               # եթե զանգվածը սորտավորված է => կանգ ենք առնում
        break
    else:                       # այլապես կրկին խառնում ենք զանգվածը
        shuffle(a)

print(a)                        # վերջում տպում ենք ստացված զանգվածը
Այս ալգորիթմը պատահական է և կարող է անվերջ ժամանակ խլել։ Այդ պատճառով այն վտանգավոր և անարդյունավետ կլինի իրական նախագծերում կիրառել։
Ձեզ խնդրում են հաշվել, թե քանի կրկնություն կպահանջվի Bogosort ալգորիթմից, մինչև այն գտնի լուծումը։

Մուտք

Մուտքի առաջին տողում տրված է n ամբողջ թիվը (1 ≤ n ≤
Հաջորդ տողում տրված են n ամբողջ թվեր (

Ելք

Ծրագիրը պետք է տպի, թե քանի կրկնություն է պահանջվում Bogosort ալգորիթմին, որպեսզի ավարտի աշխատանքը։

Օրինակներ

Մուտք
Ելք
5 5 -1 2 3 9
10

Բացատրություն

10 թիվը պատահական է. այն կարող էր լինել 2, կամ 200։ Հնարավոր է ամեն անգամ նույն մուտքային տվյալներով տարբեր արդյունքներ ստանալ, քանի որ ալգորիթմը պատահականության սկզբունքով է խառնում թվերը։
 

Այլ Աբսուրդային Տեսակավորման Ալգորիթմներ

Այլ տեսակավորման ալգորիթմների վիզուալ օրինակներ կարող եք դիտել ներքևում ներկայացված Ardens YouTube ալիքի տեսանյութում:
Video preview
Ardens: 10 FORBIDDEN Sorting Algorithms
 

Constraints

Time limit: 60 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue