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

м
Бот: исправљена преусмерења
м (Разне исправке)
м (Бот: исправљена преусмерења)
}}
[[Датотека:Bucket sort 1.png|right|frame|Елементи су распоређени међу кофама]]
[[Датотека:Bucket sort 2.png|right|frame|Насупрот bucket sort-ирању које се врши након што су кофе напуњене, елементу су [[Sortiranjesortiranje ubacivanjemumetanjem|сортирани уметањем]] како су убацивани]]
'''Проксмапсорт''' или '''Проксмап сортирање''' је врста [[Алгоритми сортирања|алгоритма сортирања]], који ради тако што подели [[Низ (структура података)|низ]] података, или кључева, на мањи број поднизова. Име је скраћеница од рачунања "proximity map"-е, која одређује, за сваки кључ К, почетак подниза у коме ће се К налазити у коначном поретку. Кључеви су постављени у сваки подниз коришћењем [[Sortiranjesortiranje ubacivanjemumetanjem|сортирања уметањем]]. Уколико су кључеви добро распоређени кроз поднизове, временска сложеност сортирања је линеарна, што је много брже од [http://en.wikipedia.org/wiki/Comparison_sort Comparison sort] сортирања, које не може бити боље од О(nlogn). Процене [[Теорија комплексности|теорије комплексности]] укључују број поднизова и proximity mapping функцију. То је облик [[Алгоритми сортирања#Bucket sort|Bucket sort-а]] и [[Алгоритми сортирања#Radix sort|Radix sort-а]]. Алгоритам не постаје много комплекснији како количина података расте.
 
Када је проксмап сортирање завршено '''ProxmapSearch''' може бити коришћено за проналазак кључева у сортираном низу за временску сложеност О(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-177.</ref> Међутим, перформансе овог сортирања опадају са повећањем броја кључева у кофама; уколико су вредности збијене, биће сврстане у исту кофу и перформасе ће бити значајно умањене. Ова особина важи и за ProxmapSort: уколико су кофе превелике, перформансе ће значајно опасти.
== Референце ==
256.217

измена