Проксмап сортирање

Проксмап сортирање

Insertion sorting into buckets during proxmap. Пример сортирања уметањем листе случајних бројева.
Класа	Алгоритам сортирања
Структура података	Низ
Најгора перформанца	$O(n^{2})$
Најбоља перформанца	$O(n)$
Најгора просторна комплексност	$O(n)$

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