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

Садржај обрисан Садржај додат
Нема описа измене
Нема описа измене
Ред 2:
{{Infobox Algorithm-lat
|class=[[Алгоритми_сортирања|Алгоритам сортирања]]
|imageslika=[[File:Insertion Sorting during proxmap.PNG|none|315px|Insertion sorting into buckets during proxmap.]]
|captionime=Пример сортирања уметањем листе случајних бројева.
|datastruktura=[[Низ_(структура_података)|Низ]]
|timevkompleksnost=<math>O(n^2)</math>
|best-timesrednja vk=<math>O(n)</math>
|spacemkompleksnost=<math>O(n)</math>
}}
'''Проксмапсорт''' или '''Проксмап сортирање''' је врста [[Алгоритми_сортирања|алгоритма сортирања]], који ради тако што подели [[Низ_(структура_података)|низ]] података, или кључева, на мањи број поднизова. Име је скраћеница од рачунања "proximity map"-е, која одређује, за сваки кључ К, почетак подниза у коме ће се К налазити у коначном поретку. Кључеви су постављени у сваки подниз коришћењем [[Sortiranje_ubacivanjem|сортирања уметањем]]. Уколико су кључеви добро распоређени кроз поднизове, временска сложеност сортирања је линеарна, што је много брже од [http://en.wikipedia.org/wiki/Comparison_sort Comparison sort] сортирања, које не може бити боље од О(nlogn). Процене [[Теорија_комплексности|теорије комплексности]] укључују број поднизова и proximity mapping функцију. То је облик [[Алгоритми_сортирања#Bucket_sort|Bucket sort-а]] и [[Алгоритми_сортирања#Radix_sort|Radix sort-а]]. Алгоритам не постаје много комплекснији како количина података расте.