Գաճաճային դասակարգում
Գաճաճային դասակարգում, որը սկզբնապես առաջարկվել էր Համիդ Սաբազի-Ազադի կողմից 2000 թ.-ին և կոչվել է ‹‹հիմար›› դասակարգում, որից հետո նկարագրվել է Դիք Գրյունի կողմից և անվանվել գաճաճային[1], դասակարգման ալգորիթմ է, որը հատուկ է ներդրմամբ դասակարգմանը, բացառությամբ էլեմենտի տեղաշարժելը ավարտվում է բազում փոխանակումներով, ինչպես պղպջակայինում է։
Գաճաճային դասակարգում | |
---|---|
Տեսակ | կայուն տեսակավորման ալգորիթմ |
Վատագույն դեպքում կատարումը | |
Լավագույն դեպքում կատարումը | |
Օգտագործում է | զանգված |
Շատ պարզ է, պարունակում է ոչ խճճված հանգույցներ (loop)։ Գործողություն կատարելու ժամանակը O(n²) է, բայց ձգտում է O(n), ի, եթե ցանկը սկզբնապես գրեթե դասակարգված է[2]։ Գործնականում ալգորիթմը կարող է գործել այնպես արագ ինչպես ներդրմամբ դասակարգումը. Գործողություն կատարելու միջին ժամանակը .[3]
Ալգորիթմը միշտ գտնում է առաջին տեղամասը, որտեղ 2 կից էլեմենտներ սխալ հերթականությամբ են դասավորված և տեղափոխում դրանք։ Դա առավելություն է վերցնում այն փաստից, որ տեղափոխություն իրականացնելը կարող է առաջացնել մի նոր դասավորությունից անկախ ու կից զույգ, որը կգտնվի 2 տեղափոխված էլեմենտներից անմիջապես առաջ կամ հետո։ Չի ենթադրվում, որ տվյալ դիրքից առաջ գտնվող էլեմենտները դասակարգված են, այսպիսով պետք է միայն ստուգվի տեղափոխված էլեմենտներից անմիջապես առաջ գտնվող դասավորությունը։
Նկարագրություն խմբագրել
Ահա և գաճաճային դասակարգման pseudocode ը, որը օգտագործում է zero-based array։
procedure gnomeSort(a[])
pos := 1
while pos < length(a)
if (a[pos] >= a[pos-1])
pos := pos + 1
else
swap a[pos] and a[pos-1]
if (pos > 1)
pos := pos - 1
else
pos := pos + 1
end if
end if
end while
end procedure
Օրինակ խմբագրել
Տրված է ոչ դասակարգված հերթականություն՝ a = [5, 3, 2, 4], գաճաճային դասաակարգումը պետք է կատարի հետևյալ քայլերը while/loop հրամանի ժամանակ։ ‹‹Ընթացիկ դիրքը›› գրված է bold-ով։
Ընթացիկ փոփոխություն | Կատարվելիք գործողություն |
---|---|
[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), ավարտ։ |
Օպտիմիզացում խմբագրել
Գաճաճային դասակարգումը կարող է օպտիմիզացվել ներկայացվելով փոփոխական մեծության տեսքով, որպեսզի պահպանի իր դիրքը մինչ տեղաշարժվելը դեպի ցանկի սկիզբ։ Դա ‹‹գաճաճին›› թույլ կտա teleport կատարի հետ` իր նախկին դիրքին։ Այս օպտիմիզացիայի շնորհիվ գաճաճային դասակարգումը կդառնա ներդրմամբ դասակարգման։
Ահա և օպտիմիզացված գաճաճային դասակարգման pseudocode ը, որը օգտագործում է zero-based array։
procedure optimizedGnomeSort(a[])
pos := 1
last := 0
while pos < length(a)
if (a[pos] >= a[pos-1])
if (last != 0)
pos := last
last := 0
end if
pos := pos + 1
else
swap a[pos] and a[pos-1]
if (pos > 1)
if (last == 0)
last := pos
end if
pos := pos - 1
else
pos := pos + 1
end if
end if
end while
end procedure
Ծանոթագրություններ խմբագրել
- ↑ http://www.cs.vu.nl/~dick/gnomesort.html
- ↑ Paul E. Black. «gnome sort». Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Վերցված է 2010 թ․ հունվարի 20-ին.
- ↑ «What is the Average Big-O Complexity of Gnome sort?». StackOverflow.