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

Վիքիպեդիայից՝ ազատ հանրագիտարանից

Գաճաճային դասակարգումը, որը սկզբնապես առաջարկվել էր Համիդ Սաբազի-Ազադի կողմից 2000 թ.-ին և կոչվել է ‹‹հիմար›› դասակարգում, որից հետո նկարագրվել է Դիք Գրյունի կողմից և անվանվել գաճաճային,[1] դասակարգման ալգորիթմ է, որը հատուկ է ներդրմամբ դասակարգմանը, բացառությամբ էլեմենտի տեղաշարժելը ավարտվում է բազում փոխանակումներով, ինչպես պղպջակայինում է։

Շատ պարզ է, պարունակում է ոչ խճճված հանգույցներ (loop)։ Գործողություն կատարելու ժամանակը O(n²) է, բայց ձգտում է O(n), ի, եթե ցանկը սկզբնապես գրեթե դասակարգված է։[2] Գործնականում ալգորիթմը կարող է գործել այնպես արագ ինչպես ներդրմամբ դասակարգումը. Գործողություն կատարելու միջին ժամանակը 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։ http://www.itl.nist.gov/div897/sqg/dads/HTML/gnomeSort.html։ Վերցված է 2010-01-20։ 
  3. «What is the Average Big-O Complexity of Gnome sort?»։ StackOverflow։ http://stackoverflow.com/questions/2066541/what-is-the-average-big--complexity-of-gnome-sort։ 

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