«Gnome sort»–ի խմբագրումների տարբերություն
No edit summary |
չNo edit summary |
||
Տող 1. | Տող 1. | ||
'''Գաճաճային դասակարգումը''', որը սկզբնապես առաջարկվել էր Համիդ Սաբազի-Ազադի կողմից 2000 թ.-ին և կոչվել է [http://sina.sharif.edu/~azad/stupid-sort.PDF ‹‹հիմար›› դասակարգում], որից հետո նկարագրվել է Դիք Գրյունի կողմից և անվանվել գաճաճային,<ref>http://www.cs.vu.nl/~dick/gnomesort.html</ref> [ |
'''Գաճաճային դասակարգումը''', որը սկզբնապես առաջարկվել էր Համիդ Սաբազի-Ազադի կողմից 2000 թ.-ին և կոչվել է [http://sina.sharif.edu/~azad/stupid-sort.PDF ‹‹հիմար›› դասակարգում], որից հետո նկարագրվել է Դիք Գրյունի կողմից և անվանվել գաճաճային,<ref>http://www.cs.vu.nl/~dick/gnomesort.html</ref> [[դասակարգման ալգորիթմ]] է, որը հատուկ է [[ներդրմամբ դասակարգմանը]], բացառությամբ էլեմենտի տեղաշարժելը ավարտվում է բազում տեղափոխանակումներով, ինչպես [http://en.wikipedia.org/wiki/Bubble_sort պղպջակայինում] է: |
||
շատ պարզ է, պարունակում է ոչ խճճված հանգույցներ (loop): Գործողություն կատարելու ժամանակը [ |
շատ պարզ է, պարունակում է ոչ խճճված հանգույցներ (loop): Գործողություն կատարելու ժամանակը [[notation O]](''n''²) է, բայց հակված է O(''n'')-ի նկատմամբ, եթե ցանկը սկզբնապես գրեթե դասակարգված է:<ref>{{cite web | |
||
url=http://www.itl.nist.gov/div897/sqg/dads/HTML/gnomeSort.html | |
url=http://www.itl.nist.gov/div897/sqg/dads/HTML/gnomeSort.html | |
||
title=gnome sort| |
title=gnome sort| |
||
Տող 17. | Տող 17. | ||
== Նկարագրություն == |
== Նկարագրություն == |
||
Ահա և գաճաճային դասակարգման [ |
Ահա և գաճաճային դասակարգման [[pseudocode]]ը, որը օգտագործում է [[Array_data_type#Index_origin zero-based array]]: |
||
<code> |
<code> |
||
Տող 78. | Տող 78. | ||
==Օպտիմիզացում== |
==Օպտիմիզացում== |
||
Գաճաճային դասակարգումը կարող է օպտիմիզացվել ներկայացվելով փոփոխական մեծության տեսքով, որպեսզի պահպանի իր դիրքը մինչ տեղաշարժվելը դեպի ցանկի սկիզբ: Դա ‹‹գաճաճին›› թույլ կտա [ |
Գաճաճային դասակարգումը կարող է օպտիմիզացվել ներկայացվելով փոփոխական մեծության տեսքով, որպեսզի պահպանի իր դիրքը մինչ տեղաշարժվելը դեպի ցանկի սկիզբ: Դա ‹‹գաճաճին›› թույլ կտա [[teleport]] կատարի հետ` իր նախկին դիրքին: Այս օպտիմիզացիայի շնորհիվ գաճաճային դասակարգումը կդառնա[[ներդրմամբ դասակարգման]]: |
||
Ահա և օպտիմիզացված գաճաճային դասակարգման [ |
Ահա և օպտիմիզացված գաճաճային դասակարգման [[pseudocode]]ը, որը օգտագործում է zero-based array: |
||
<code> |
<code> |
||
procedure optimizedGnomeSort(a[]) |
procedure optimizedGnomeSort(a[]) |
||
Տող 112. | Տող 112. | ||
==Արտաքին հղումներ== |
==Արտաքին հղումներ== |
||
* [http://www.cs.vu.nl/~dick/gnomesort.html Gnome sort] |
* [http://www.cs.vu.nl/~dick/gnomesort.html Gnome sort] |
||
[[ca:Gnome-sort]] |
|||
[[de:Gnomesort]] |
|||
[[es:Gnome sort]] |
|||
[[fa:مرتبسازی گورزاد]] |
|||
[[hy:Գաճաճային դասակարգում]] |
|||
[[it:Gnome sort]] |
|||
[[hu:Kertitörpe-rendezés]] |
|||
[[ja:ノームソート]] |
|||
[[pl:Sortowanie gnoma]] |
|||
[[pt:Gnome sort]] |
|||
[[ru:Гномья сортировка]] |
|||
[[tr:Cüce sıralaması]] |
|||
[[uk:Сортування гнома]] |
01:23, 20 Հոկտեմբերի 2011-ի տարբերակ
Գաճաճային դասակարգումը, որը սկզբնապես առաջարկվել էր Համիդ Սաբազի-Ազադի կողմից 2000 թ.-ին և կոչվել է ‹‹հիմար›› դասակարգում, որից հետո նկարագրվել է Դիք Գրյունի կողմից և անվանվել գաճաճային,[1] դասակարգման ալգորիթմ է, որը հատուկ է ներդրմամբ դասակարգմանը, բացառությամբ էլեմենտի տեղաշարժելը ավարտվում է բազում տեղափոխանակումներով, ինչպես պղպջակայինում է:
շատ պարզ է, պարունակում է ոչ խճճված հանգույցներ (loop): Գործողություն կատարելու ժամանակը notation O(n²) է, բայց հակված է O(n)-ի նկատմամբ, եթե ցանկը սկզբնապես գրեթե դասակարգված է:[2] Գործնականում ալգորիթմը կարող է գործել այնպես արագ ինչպես ներդրմամբ դասակարգումը. Գործողություն կատարելու միջին ժամանակը .[3]
Ալգորիթմը միշտ գտնում է առաջին տեղամասը, որտեղ 2 կից էլեմենտներ սխալ հերթականությամբ են դասավորված և տեղափոխում դրանց: Դա առավելություն է վերցնում այն փաստից, որ տեղափոխում իրականացնելը կարող է ներկայացնել մի նոր դասավորությունից անկախ ու կից զույգ 2 տեղափոխված էլեմենտներից միմիայն անմիջապես առաջ կամ հետո: Չի ենթադրվում, որ տվյալ դիրքից առաջ գտնվող էլեմենտները դասակարգված են, այսպիսով պետք է միայն ստուգվի տեղափոխված ելեմենտներից անմիջապես առաջ գտվող դիրքը:
Նկարագրություն
Ահա և գաճաճային դասակարգման pseudocodeը, որը օգտագործում է Array_data_type#Index_origin 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-01-20-ին.
- ↑ «What is the Average Big-O Complexity of Gnome sort?». StackOverflow.