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

м
razne ispravke; козметичке измене
м (Renamed template)
м (razne ispravke; козметичке измене)
[[Датотека:Bucket sort 1.png|right|frame|Елементи су распоређени међу кофама]]
[[Датотека:Bucket sort 2.png|right|frame|Насупрот bucket sort-ирању које се врши након што су кофе напуњене, елементу су [[sortiranje umetanjem|сортирани уметањем]] како су убацивани]]
'''Проксмапсорт''' или '''Проксмап сортирање''' је врста [[Алгоритми сортирања|алгоритма сортирања]], који ради тако што подели [[Низ (структура података)|низ]] података, или кључева, на мањи број поднизова. Име је скраћеница од рачунања "proximity map"-е, која одређује, за сваки кључ К, почетак подниза у коме ће се К налазити у коначном поретку. Кључеви су постављени у сваки подниз коришћењем [[sortiranje umetanjem|сортирања уметањем]]. Уколико су кључеви добро распоређени кроз поднизове, временска сложеност сортирања је линеарна, што је много брже од [http://en.wikipedia.org/wiki/Comparison_sort [Comparison sort]] сортирања, које не може бити боље од О(nlogn). Процене [[Теорија комплексности|теорије комплексности]] укључују број поднизова и proximity mapping функцију. То је облик [[Алгоритми сортирања#Bucket sort|Bucket sort-а]] и [[Алгоритми сортирања#Radix sort|Radix sort-а]]. Алгоритам не постаје много комплекснији како количина података расте.
 
Када је проксмап сортирање завршено '''ProxmapSearch''' може бити коришћено за проналазак кључева у сортираном низу за временску сложеност О(1), уколико су кључеви добро распоређени током сортирања.
== Историја ==
* Изумели су га [http://www.ics.uci.edu/faculty/profiles/view_faculty.php?ucinetid=standish Томас А. Стандиш], Prof. Emeritus, Department of Informatics, [http://en.wikipedia.org/wiki/Donald_Bren_School_of_Information_and_Computer_Sciences [Donald Bren School of Information and Computer Sciences]], University of California, Irvine крајем осамедесетих.
 
== Преглед ==
1.572.075

измена