Մենք հաճախ ենք աշխատել ցուցակներ սորտավորելու (տեսակավորելու) հետ տարբեր խնդիրներում: Մենք օգտագործել ենք ներկառուցված ֆունկցիաներ՝ զանգվածների տեսակավորման համար: Սակայն, թե իրականում այդ ներկառուցված ֆունկցիաները ինչպես են աշխատում «կուլիսների հետևում», միշտ չէ որ պարզ է երևում: Այս գլուխում կանդրադառնանք ամենահայտնի տեսակավորման (սորտավորման) ալգորիթմներից մի քանիսին, որոնք կիրառվում են տարբեր իրավիճակներում՝ կախված դեպքից:
Առաջին ալգորիթմը, որի մասին կխոսենք, տեսակավորման ալգորիթմներից ամենաաբսուրդալն է։ Այն կոչվում է 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 ալիքի տեսանյութում: