Գաճաճային դասակարգում - Վիքիպեդիա՝ ազատ հանրագիտարան
Գաճաճային դասակարգում
Գաճաճային դասակարգումը, որը սկզբնապես առաջարկվել էր Համիդ Սաբազի-Ազադի կողմից 2000 թ.-ին և կոչվել է ‹‹հիմար›› դասակարգում, որից հետո նկարագրվել է Դիք Գրյունի կողմից և անվանվել գաճաճային,[1] դասակարգման ալգորիթմ է, որը հատուկ է ներդրմամբ դասակարգմանը, բացառությամբ էլեմենտի տեղաշարժելը ավարտվում է բազում փոխանակումներով, ինչպես պղպջակայինում է։
Շատ պարզ է, պարունակում է ոչ խճճված հանգույցներ (loop)։ Գործողություն կատարելու ժամանակը O(n²) է, բայց ձգտում է O(n), ի, եթե ցանկը սկզբնապես գրեթե դասակարգված է։[2] Գործնականում ալգորիթմը կարող է գործել այնպես արագ ինչպես ներդրմամբ դասակարգումը. Գործողություն կատարելու միջին ժամանակը .[3]
Ալգորիթմը միշտ գտնում է առաջին տեղամասը, որտեղ 2 կից էլեմենտներ սխալ հերթականությամբ են դասավորված և տեղափոխում դրանք։ Դա առավելություն է վերցնում այն փաստից, որ տեղափոխություն իրականացնելը կարող է առաջացնել մի նոր դասավորությունից անկախ ու կից զույգ, որը կգտնվի 2 տեղափոխված էլեմենտներից անմիջապես առաջ կամ հետո։ Չի ենթադրվում, որ տվյալ դիրքից առաջ գտնվող էլեմենտները դասակարգված են, այսպիսով պետք է միայն ստուգվի տեղափոխված էլեմենտներից անմիջապես առաջ գտնվող դասավորությունը։
2 Օպտիմիզացում
Ահա և գաճաճային դասակարգման pseudocode ը, որը օգտագործում է zero-based array։
if (a[pos] &gt;= a[pos-1])
Օրինակ[խմբագրել]
Տրված է ոչ դասակարգված հերթականություն` a = [5, 3, 2, 4], գաճաճային դասաակարգումը պետք է կատարի հետևյալ քայլերը while/loop հրամանի ժամանակ։ ‹‹Ընթացիկ դիրքը›› գրված է bold-ով։
Ընթացիկ փոփոխություն
Կատարվելիք գործողություն
[5, 3, 2, 4]
a[pos] < a[pos-1], տեղափոխություն։
a[pos] >= a[pos-1], աճում է դիրքը։
a[pos] < a[pos-1], տեղափոխվում է հաջորդ դիրքին, նվազում է դիրքը։
[3, 2, 5, 4]
[2, 3, 5, 4]
a[pos] >= a[pos-1], աճում է դի