Պղպջակային տեսակավորում
| Այս հոդվածն աղբյուրների կարիք ունի։ Դուք կարող եք բարելավել հոդվածը՝ գտնելով բերված տեղեկությունների հաստատումը վստահելի աղբյուրներում և ավելացնելով դրանց հղումները հոդվածին։ Անհիմն հղումները ենթակա են հեռացման։ |
Պղպջակային տեսակավորում (անգլ bubble sort), տեսակավորման պարզ ալգորիթմ, որը կարգավորում է զանգվածը շարունակաբար անցնելով զանգվածի վրայով և տեղերով փոխանակելով սխալ հերթականթյամբ շարված հարևան էլեմենտները[1]։ Սա շարունակվում է այնքան, մինչև այլևս կարիք չլինի փոխանակել էլեմենտները, ինչը կնշանակի, որ զանգվածը կարգավորված է։ Քանի որ ալգորիթմը համեմատության եղանակով է տեսակավորում, այն համարվում է համեմատության ալգորիթմ (comparison sort). Թեպետ ալգորիթմը պարզունակ է, այն երբեմն ձեռնտու է փոքր ծավալի տվյալներ կարգավորելիս, ի տարբերություն այլ ալգորիթմների, որոնք ավելի արագ են մեծ ծավալի տվյալների վրա աշխատելիս։
| Պղպջակային տեսակավորում | |
|---|---|
 Պղպջակային տեսակավորում Խմբագրված գույն | |
| Տեսակ | տեսակավորման ալգորիթմ, կայուն տեսակավորման ալգորիթմ և համեմատություններով դասակարգում |
| Տվյալների կառուցվածք | |
| Վատագույն դեպքում կատարումը | |
| Լավագույն դեպքում կատարումը | |
| Օգտագործում է | զանգված |
| Անվանված է | bubble? |
Կատարում խմբագրել
«Bubble sort»-ը ունի worst-case և միջին աստիճանի բարդություն, որն արտահայտվում է հետևյալ կերպ՝ О(n²), որտեղ n-ը սորտավորվող էլեմենտների քանակն է։ Շրջանառության մեջ կան այլ ալգորիթմներ, որոնք նույն բարդության աստիճանի դիմաց ավելի էֆեկտիվ են։ Նույնիսկ այլ О(n²) -ի կարգի սորտավորման ալգորիթմներ, օրինակ՝ «insertion sort»-ը, ավելի լավ են իրենց առջև դրված խնդիրը լուծում, քան «bubble sort»-ը։ Հետևաբար «bubble sort»-ը հարմար չէ օգտագործել, երբ n-ը մեծ թիվ է։ Միակ առավելությունը, որ «bubble sort»-ը ունի այլ սորտավորող ալգորիթմների նկատմամբ (օրինակ «quicksort»-ից), այն է, որ «bubble sort»-ը կարողանում է հասկանալ, թե երբ է տրված ինֆորմացիան ամբողջապես սորտավորված։
Երբ տրված էլեմենտները սորտավորված են (best-case), «bubble sort»-ի բարդության ասիտճանը ընդամենը O(n)-է։ Համեմատության համար շատ այլ ալգորիթմներ, նույնիսկ այն ալգորիթմները, որոնք ավելի հաջող (average case) բարդություն ունեն ամբողջ սորտավորման գործընթացը կատարում են(on the set) և հետևաբար ավելի բարդ են։ Էլեմենտների դիրքերը «bubble sort»-ում շատ մեծ դեր են տանում սորտավորման լավ կատարման մեջ։ Մեծ արժեքի էլեմենտներ շարքի սկզբում խնիդրներ չեն առաջացնում, քանի որ շատ արագ նրանք փոխանակվում են։ Թերևս փոքր արժեքի էլեմենտները, որոնք գտնվում են շարքի վերջում, մեծ դժվարությամբ և դանդաղ են շարժվում դեպի շարքի վերջը։ Սրա պատճառով էլ այսպիսի էլեմենտները կոչվում են ճագարներ և կրիաներ։ Բազմաթիվ ջանքեր են գործադրվել, որպեսզի վերացվեն կրիաները և ալգորիթմի գործողությունները ավելի արագ կատարվեն։ «Cocktail sort»-ը երկկողմանի «bubble sort» է, որը շարքը նախ մեկ ծայրից մյուսն է անցնում, ապա հետ դառնում և կրկնում հակառակ ծայրից։ Այն կրիաներին բավականին լավ է տեղաշարժում, բայց մնում է O(n²) worst-case բարդության աստիճանի։ «Comb sort»-ը համեմատում է այնպիսի էլեմենտներ, որոնք բաժանված են և միմյանց միջև մեծ տարածք ունեն բաց թողնված։ Այն շատ արագ կարող է կրիաների տեղաշարժել։ Այս ալգորիթմի միջին արագությունը համեմատելի է շատ ավելի արագ ալգորիթմերի արագությունների հետ, օրինակ՝ «quicksort»-ի։
Կիրառություն խմբագրել
Թեև «bubble sort»-ը ամենապարզ սորտավորման ալգորիթմներից է հասկանալու և օգտագործելու համար, O(n²) բարդությունը նշանակում է, որ նրա ՕԳԳ-ն միանգամից նվազում է, երբ քիչ քանակով էլեմենտներ են շարքում։ Նույնիսկ պարզ O(n²) սորտավորման ալգորիթմները (insertion sort) հիմնականում ավելի լավ ՕԳԳ են ցուցաբերում։ Պարզության պատճառով «bubble sort»-ը հաճախ օգտագործվում է, որպեսզի աշակերտներին ներկայացվի ալգորիթմի կոնցեպտը և ծրագրավորման նախնական ու ամենապարզ տեսակը։ Թերևս, որոշ ուսումնասիրողներ՝ ինչպես Owen Astrachan-ը, երկար ուոսումնասիրություներից հետո գտնում են, որ այն չպետք է այլևս դասավանդվի։ «Jargon file»-ը, որը ավելի հայտնի է bogosort անվանմամբ (“the archetypical [sic] perversely awful algorithm”) նաև «bubble sort»-ը անվանում է "the generic badalgorithm"։ Դոնալդ Կնութը իր «The Art of Computer Programming» գրքում գրել է. "թվում է, թե "bubble sort"-ը չունի ոչ մի երաշխավորագիր, բացի գրավիչ անվանումից և այն փաստից, որ այն հանգեցնում է բազմաթիվ հետաքրքիր տեսական խնդիրների", որոնցից մի քանիսը նա հետո քննարկում է։
"Bubble sort"–ը ասիմպտոտիկ համարժեք է insertion sort-ին աշխատացման ժամանակ ամենավատ դեպքում, բայց երկու ալգորիթմները զգալիորեն տարբերվում են փոխանակումների թվի հետ։ Էքսպերիմենտալ արդյուննքերը ինչպես Astrachan-ինը, նաև ցույց են տվել զգալիորեն լավն են նույնիսկ պատահական ցուցակներում։ Այդ պատճառներով էլ շատ ժամանակակից ալգորիթմային դասագրքերում խուսափում են օգտագործել bubble sort-ալգորիթմը insertion sort-ի օգտին։ Bubble sort-ը նաև փոքր-ինչ փոխազդում է ժամանակակից CPU սարքավորումների հետ։ Այն պահանջում է ամենաքիչը երկու անգամ շատ գրառում insertion sort-ից, երկու անգամ շատ գաղտնագրեր և ասիմպտոտիկորեն շատ branch misprediction-ներ են բացակայում։
Պսևդոկոդ խմբագրել
Ահա պղպջակային տեսակավորման ալգորիթմի պսևդոկոդը (զանգվածը համարակալված է 0-ից սկսած)
procedure bubbleSort( A : list of sortable items )
n = length(A)
repeat
swapped = false
for i = 1 to n-1 inclusive do
/* եթե այս զույգը սխալ հերթականությամբ է */
if A[i-1] > A[i] then
/* տեղերով փոխանակել և հիշել, որ ինչ-որ բան է փոխվել*/
swap( A[i-1], A[i] )
swapped = true
end if
end for
until not swapped
end procedureԾանոթագրություններ խմբագրել
 | Վիքիպահեստն ունի նյութեր, որոնք վերաբերում են «Պղպջակային տեսակավորում» հոդվածին։ |