Counting Sort (հաշվարկային տեսակավորում)
Նման ալգորիթմները, օրինակ Merge Sort (միաձուլման տեսակավորում), կատարում են գործողություններ, որպեսզի տեսակավորեն տրված էլեմենտների հաջորդականությունը։ Շատ ծրագրավորման լեզուներում ներկառուցված
sort()-ի ֆունկցիոնալությունը նույնպես աշխատում է մոտավորապես բարդությամբ։ Ուստի հաճախ առաջանում է հարց, թե արդյոք առկա՞ է ավելի արագ տեսակավորման alguma։Մեկ հիմնական ալգորիթմ, որը տեսակավորում է էլեմենտների հաջորդականությունը գծային ժամանակում (և ըստ այդմ կատարում է գործողություններ), Counting Sort-ն է։ Այն բավականին արդյունավետ է, երբ անհրաժեշտ է տեսակավորել այնպիսի թվեր, որոնք ամբողջ են և կանխորոշված դիապազոն ունեն։
Counting Sort-ի հիմնական գաղափարն է օգտագործել «հիստոգրամայի» նման կառուցվածք՝ հաշվելու, թե ներմուծված հավաքածուի յուրաքանչյուր արժեք քանի անգամ է հանդիպում։ Այնուհետև այդ ինֆորմացիան օգտագործվում է սկզբնական էլեմենտները ցանկալի դասավորվածությամբ կրկին տեղաբաշխելու համար։
Այսպես, եթե պետք է տեսակավորենք
[7, 3, 5, 5, 1, 1, 6, 3, 4, 4, 3, 3, 7, 7, 1, 2, 5, 7, 4, 1, 7, 2, 1, 5, 5, 3, 1, 4, 8, 7] զանգվածը, ապա նախ կկազմենք հիստոգրամ, որը ցույց կտա, թե որ արժեքը քանի անգամ է հանդիպում։ Օրինակ, եթե այն տալիս է [6, 2, 5, 4, 5, 1, 6, 1], ապա կարելի է հասկանալ, որ 1-ը տեղի է ունեցել 6 անգամ, 2-ը՝ 2 անգամ, 3-ը՝ 5 անգամ և այլն (պատկերի մեջ պատկերվածի պես)։
a = ...
bottom, top = min(a), max(a) + 1 # Determine the range
hist = [0] * (top - bottom) # Fill the range with 0s => no counts
for num in a: # Iterate through the array
hist[num - bottom] += 1 # Increase the histogram value
res = [] # Initialize the result array
for num in range(bottom, top): # Iterate over the range
res += [num] * hist[num - bottom] # Add as many nums to result as the value in the histogramԻ վերջո,
res զանգվածը կդառնա [1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 7, 7, 7, 7, 7, 7, 8]։Նկատեք, որ այս տեսակավորումը գործում է միայն թվերի համար (հատկապես փոքր դիապազոնի), մինչդեռ այլ ալգորիթմներ, օրինակ Bubble sort (պղպջակային տեսակավորում) կամ Merge sort (միաձուլման տեսակավորում), կարող են աշխատել առավել լայն իմաստով՝ համեմատելով կամայական օբյեկտներ։
Այսպիսով, ալգորիթմը կատարում է գործողություններ, որտեղ
n-ը սկզբնական զանգվածի էլեմենտների քանակն է, իսկ r-ը արժեքների դիապազոնի չափը։ Եթե արժեքների դիապազոնը փոքր է, սա հաճախ ավելի արագ է, քան օրինակ Merge sort-ը։🤔
Իսկ գոյություն ունե՞ն այլ գծային ժամանակով տեսակավորման ալգորիթմներ։
Այո, կարող եք ծանոթանալ Radix-sort ալգորիթմին, թեև այն աշխատում է միայն թվերի համար։
Եթե խոսքը վերաբերում է համեմատության վրա հիմնված (comparison-based) ալգորիթմներին, որոնք աշխատում են կամայական տիպի էլեմենտների հետ (պահանջելով միայն, որ դրանք համեմատելի լինեն), ապա ամենաարդյունավետ ալգորիթմը չի կարող գերազանցել բարդությունը։
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ )։Հաջորդ տողում տրված են
n ամբողջ թվեր (-100 ≤ ≤ 100)։Ելք
Ծրագիրը պետք է տպի այդ
n թվերը աճման կարգով, բաժանված բացատներով։Օրինակներ
Մուտք | Ելք |
5
-3 5 -1 2 10 | -3 -1 2 5 10 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 5 MB