«Գաճաճային դասակարգում»–ի խմբագրումների տարբերություն

Content deleted Content added
No edit summary
չ clean up, replaced: → (44), է: → է։ (2), բ: → բ։, ը: → ը։ (8), կ: → կ։, ն: → ն։ (3), ո: → ո։, տ: → տ։, ք: → ք։, ): → )։ oգտվելով ԱՎԲ
Տող 1.
'''Գաճաճային դասակարգումը''', որը սկզբնապես առաջարկվել էր Համիդ Սաբազի-Ազադի կողմից 2000 թ.-ին և կոչվել է [http://sina.sharif.edu/~azad/stupid-sort.PDF ‹‹հիմար›› դասակարգում], որից հետո նկարագրվել է Դիք Գրյունի կողմից և անվանվել գաճաճային,<ref>http://www.cs.vu.nl/~dick/gnomesort.html</ref> [http://en.wikipedia.org/wiki/Sorting_algorithm դասակարգման ալգորիթմ] է, որը հատուկ է [http://en.wikipedia.org/wiki/Insertion_sort ներդրմամբ դասակարգմանը], բացառությամբ էլեմենտի տեղաշարժելը ավարտվում է բազում փոխանակումներով, ինչպես [http://en.wikipedia.org/wiki/Bubble_sort պղպջակայինում] է: է։
 
Շատ պարզ է, պարունակում է ոչ խճճված հանգույցներ (loop): ։ Գործողություն կատարելու ժամանակը [http://en.wikipedia.org/wiki/Big_O_notation O](''n''²) է, բայց ձգտում է O(''n''), ի, եթե ցանկը սկզբնապես գրեթե դասակարգված է:է։<ref>{{cite web |
url=http://www.itl.nist.gov/div897/sqg/dads/HTML/gnomeSort.html |
title=gnome sort|
Տող 14.
}}</ref>
 
Ալգորիթմը միշտ գտնում է առաջին տեղամասը, որտեղ 2 կից էլեմենտներ սխալ հերթականությամբ են դասավորված և տեղափոխում դրանք:դրանք։ Դա առավելություն է վերցնում այն փաստից, որ տեղափոխություն իրականացնելը կարող է առաջացնել մի նոր դասավորությունից անկախ ու կից զույգ, որը կգտնվի 2 տեղափոխված էլեմենտներից անմիջապես առաջ կամ հետո:հետո։ Չի ենթադրվում, որ տվյալ դիրքից առաջ գտնվող էլեմենտները դասակարգված են, այսպիսով պետք է միայն ստուգվի տեղափոխված էլեմենտներից անմիջապես առաջ գտնվող դասավորությունը:դասավորությունը։
 
== Նկարագրություն ==
Տող 38.
 
===Օրինակ===
Տրված է ոչ դասակարգված հերթականություն` a = [5, 3, 2, 4], գաճաճային դասաակարգումը պետք է կատարի հետևյալ քայլերը while/loop հրամանի ժամանակ:ժամանակ։ ‹‹Ընթացիկ դիրքը›› գրված է '''bold'''-ով:
 
{| class="wikitable"
Տող 45.
! Կատարվելիք գործողություն
|-
| [5, '''3''', 2, 4]
| a[pos] < a[pos-1], տեղափոխություն:տեղափոխություն։
|-
| [3, '''5''', 2, 4]
| a[pos] >= a[pos-1], աճում է դիրքը:դիրքը։
|-
| [3, 5, '''2''', 4]
| a[pos] < a[pos-1], տեղափոխվում է հաջորդ դիրքին, նվազում է դիրքը:դիրքը։
|-
| [3, '''2''', 5, 4]
| a[pos] < a[pos-1], տեղափոխություն:տեղափոխություն։
|-
| [2, '''3''', 5, 4]
| a[pos] >= a[pos-1], աճում է դիրքը:դիրքը։
|-
| [2, 3, '''5''', 4]
| a[pos] >= a[pos-1], աճում է դիրքը:դիրքը։
|-
| [2, 3, 5, '''4''']
| a[pos] < a[pos-1], տեղափոխվում է հաջորդ դիրքին, նվազում է դիրքը:դիրքը։
|-
| [2, 3, '''4''', 5]
| a[pos] >= a[pos-1], աճում է դիրքը:դիրքը։
|-
| [2, 3, 4, '''5''']
| a[pos] >= a[pos-1], աճում է դիրքը:դիրքը։
|-
| [2, 3, 4, 5]
| pos == length(a), ավարտ:ավարտ։
|-
|}
 
==Օպտիմիզացում==
Գաճաճային դասակարգումը կարող է օպտիմիզացվել ներկայացվելով փոփոխական մեծության տեսքով, որպեսզի պահպանի իր դիրքը մինչ տեղաշարժվելը դեպի ցանկի սկիզբ: սկիզբ։ Դա ‹‹գաճաճին›› թույլ կտա [http://en.wikipedia.org/wiki/Teleport teleport] կատարի հետ` իր նախկին դիրքին:դիրքին։ Այս օպտիմիզացիայի շնորհիվ գաճաճային դասակարգումը կդառնա [http://en.wikipedia.org/wiki/Insertion_sort ներդրմամբ դասակարգման]:
 
Ահա և օպտիմիզացված գաճաճային դասակարգման [http://en.wikipedia.org/wiki/Pseudocode pseudocode] ը, որը օգտագործում է [http://en.wikipedia.org/wiki/Array_data_type#Index_origin zero-based array]:
Տող 116.
 
{{DEFAULTSORT:Գաճաճային դասակարգում }}
[[CategoryԿատեգորիա:Sorting algorithms]]
[[CategoryԿատեգորիա:Comparison sorts]]
[[CategoryԿատեգորիա:Stable sorts]]