Проксмап сортирање — разлика између измена

м
нема резимеа измене
м
м
# '''Прикупљање''': прођи кроз поднизове редом и постави све елементе у оригинални низ, или простије, користи '''A2'''.
Напомена: кључеви могу садржати и друге податке, на пример, инстанца низа објекта Студент садржи кључ, али и индекс студента и име. ProxMapSort је погодан за организацију група објеката, а не само кључева.
 
===Пример===
Узмимо пун низ: '''A'''[''0'' до ''n-1''] са ''n'' кључева. Нека је ''i'' индекс низа A. Сортирај кључеве '''A'''' у низ '''A2''' исте величине.
[[File:ProxMapSortDemo.gif|A demonstration of ProxMapSort, a bucket sort variant that uses intermediate parallel arrays to efficiently index and size its sublists.]]
<br clear=all>
 
===Псеудокод===
<source lang="java">
</source>
Овде, '''A''' је низ који се сортира, а mapKey функција одређује број поднизова који се користе. На пример, floor(K) ће просто доделити онолико поднизова колико има целих бројева у '''A'''. Дељење кључа константом смањује број поднизова; Различите функције се могу користити да преведу домен елемената '''A''' у поднизове, као што су замена слова A–Z са 0–25 или враћање првог елемента (0–255) за дати стринг. Поднизови се сортирају како подаци пристижу, а не када су сви подаци смештени у подниз, као што је случај у типичном [[Алгоритми_сортирања#Bucket_sort|Bucket sort-у]].
 
==Proxmap Претрага==
ProxmapSearch користи '''proxMap''' низ, генерисан претходно проксмап сортирањем, како би се пронашли кључеви у сортираном низу '''A2''' у константном времену.
 
===Основна стратегија===
*Сортирај кључеве користећи ProxmapSort, чувајући '''MapKey''' функцију и '''P''' и '''A2''' низове.
*Секвенцијално претражи подниз; уколико је кључ пронађен, врати га; уколико се пронађе вредност већа од кључа, кључ није у подацима.
*Рачунање P[MapKey(k)] је O(1) временске сложености. Уколико је током сортирања коришћена мапа која даје добар распоред кључева, сваки подниз је ограничен одозого константом ''c'', тако да је највише ''c'' поређења потребно да се кључ пронађе, или да се сазна да ли је присутан; стога ProxmapSearch је O(1) временске сложености. Ако се користи најгора мапа, сви кључеви су у једном подстрингу и најгора временска сложеност је O(n) поређења.
 
===Псеудокод===
'''function''' mapKey(key)
'''if''' (sortedArray[i].key == key)
'''return''' sortedArray[i]
 
==Анализа==
===Перформансе===
 
Коришћење добре MapKey функције је важно за избегавање најгорег случаја. Морамо знати нешто о распореду података да бисмо дошли до доброг кључа.
 
===Oптимизације===
# Штедња времена: Сачувати MapKey(i) вредности, како се не би поново рачунале (као што су у коду изнад).
# Штедња простора: proxMaps могу бити чуване у hitCount низу, пошто он није више потребан када је проксмапа одређена; подаци могу бити сортирани у А, уместо коришћења А2, ако неко пожели да наведе које су вредности А до сада сортиране.
 
===Поређење са другим алгоритмима===
Пошто проксмап сортирање није само [[Алгоритми_сортирања|алгоритам сортирања]], доња граница Ω(''n'' log ''n'') није примењива. Брзина се може објаснити тиме што у основи није заснован на поређењу и што користи низове, уместо динамички алоцираних објеката и показивача који се морају пратити, као што је случај код [[Бинарно_стабло|бинарног стабла претраге]].
 
ProxmapSort омогућава употребу ProxmapSearch-а. Упркос сложености O(n), ProxMapSearch то надокнађује O(1) просечним временом приступа, што га чини привлачним за велике базе података. Уколико подаци не морају бити често ажурирани, време приступа може учинити ову функцију привлачнијом од осталих сортирања која [[нису заснована на поређењу]].
 
===Генерички bucket sort у вези са ProxmapSort-ом===
Као ProxmapSort, bucket sort уобичајено рукује листом од ''n'' нумеричких улаза, у границама од 0 до неког максималног кључа или вредности ''M'' и дели домен вредности у ''n'' кофа величине ''M''/''n''. Уколико је свака кофа сортирана користећи [[Алгоритми_сортирања#Insertion_sort|сортирање уметањем]], може се показати да ProxmapSort и bucket sort раде паралелном линеарном временском сложеношћу.<ref>[[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 8.4: Bucket sort, pp.174&ndash;177.</ref> Међутим, перформансе овог сортирања опадају са повећањем броја кључева у кофама; уколико су вредности збијене, биће сврстане у исту кофу и перформасе ће бити значајно умањене. Ова особина важи и за ProxmapSort: уколико су кофе превелике, перформансе ће значајно опасти.
==Референце==
<references />
 
* Norman Jacobson [http://www.ics.uci.edu/~jacobson/ics23/ProxmapHandout.pdf "A Synopsis of ProxmapSort & ProxmapSearch"] from Department of Computer Science, [[Donald Bren School of Information and Computer Sciences]], [[University of California, Irvine|UC Irvine]].
 
==Спољашње везе==
* http://www.cs.uah.edu/~rcoleman/CS221/Sorting/ProxMapSort.html