Գաճաճային դասակարգում

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search
Գաճաճային դասակարգում
Sorting gnomesort anim.gif
Տեսակկայուն տեսակավորման ալգորիթմ
Վատագույն դեպքում կատարումը
Լավագույն դեպքում կատարումը
Օգտագործում էզանգված

Գաճաճային դասակարգում, որը սկզբնապես առաջարկվել էր Համիդ Սաբազի-Ազադի կողմից 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

Հղումներ[խմբագրել | խմբագրել կոդը]

  1. http://www.cs.vu.nl/~dick/gnomesort.html
  2. Paul E. Black։ «gnome sort»։ Dictionary of Algorithms and Data Structures։ U.S. National Institute of Standards and Technology։ Վերցված է 2010 թ․ հունվարի 20 
  3. «What is the Average Big-O Complexity of Gnome sort?»։ StackOverflow 

Արտաքին հղումներ[խմբագրել | խմբագրել կոդը]