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

м
Разне исправке
м (Разне исправке)
м (Разне исправке)
 
=== Генерички 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. {{page|year=2001|id=ISBN 0-262-03293-7|pages=}} Section 8.4: Bucket sort,. ppстр. 174-177.</ref> Међутим, перформансе овог сортирања опадају са повећањем броја кључева у кофама; уколико су вредности збијене, биће сврстане у исту кофу и перформасе ће бити значајно умањене. Ова особина важи и за ProxmapSort: уколико су кофе превелике, перформансе ће значајно опасти.
== Референце ==
 
== Литература ==
* {{cite book|authorref= harv|last=Standish|first=Thomas A. Standish|title=Data Structures in Java.|location=|publisher=Addison Wesley Longman|year=1998|id=ISBN 0-201-30564-X|pages=}} Section 10.6. стр. 394-405.
 
* Thomas A. Standish and Norman Jacobson [http://portal.acm.org/ft_gateway.cfm?id=1138427&type=pdf "Using O(n) ProxmapSort and O(1) ProxmapSearch to Motivate CS2 Students (Part I)"] from [[Donald Bren School of Information and Computer Sciences]] at [[University of California, Irvine|UC Irvine]].
1.572.075

измена