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

|image=[[Датотека:Insertion Sorting during proxmap.PNG|noneбез|315px|Insertion sorting into buckets during proxmap.]]

[[Датотека:Bucket sort 1.png|rightдесно|frameоквир|Елементи су распоређени међу кофама]]

[[Датотека:Bucket sort 2.png|rightдесно|frameоквир|Насупрот bucket sort-ирању које се врши након што су кофе напуњене, елементу су [[sortiranje umetanjem|сортирани уметањем]] како су убацивани]]

'''Проксмапсорт''' или '''Проксмап сортирање''' је врста [[Алгоритми сортирања|алгоритма сортирања]], који ради тако што подели [[Низ (структура података)|низ]] података, или кључева, на мањи број поднизова. Име је скраћеница од рачунања "proximity map"-е, која одређује, за сваки кључ К, почетак подниза у коме ће се К налазити у коначном поретку. Кључеви су постављени у сваки подниз коришћењем [[sortiranje umetanjem|сортирања уметањем]]. Уколико су кључеви добро распоређени кроз поднизове, временска сложеност сортирања је линеарна, што је много брже од [[Comparison sort]] сортирања, које не може бити боље од О(nlogn). Процене [[Теорија комплексности|теорије комплексности]] укључују број поднизова и proximity mapping функцију. То је облик [[Алгоритми сортирања#Bucket sort|Bucket sort-а]] и [[Алгоритми сортирања#Radix sort|Radix sort-а]]. Алгоритам не постаје много комплекснији како количина података расте.

Као 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. {{page|year=2001|id=ISBN 978-0-262-03293-73|pages=}} Section 8.4: Bucket sort. стр. 174-177.</ref> Међутим, перформансе овог сортирања опадају са повећањем броја кључева у кофама; уколико су вредности збијене, биће сврстане у исту кофу и перформасе ће бити значајно умањене. Ова особина важи и за ProxmapSort: уколико су кофе превелике, перформансе ће значајно опасти.

* {{cite book|ref= harv|last=Standish|first=Thomas A.|title=Data Structures in Java.|location=|publisher=Addison Wesley Longman|year=1998|id=ISBN 978-0-201-30564-X7|pages=}} Section 10.6. стр. 394-405.