ProxmapSort, or Proxmap sort, is a sorting algorithm that works by partitioning an array of data items, or keys, into a number of "subarrays" (termed buckets, in similar sorts). The name is short for computing a "proximity map," which indicates for each key K the beginning of a subarray where K will reside in the final sorted order. Keys are placed into each subarray using insertion sort. If keys are "well distributed" among the subarrays, sorting occurs in linear time. The computational complexity estimates involve the number of subarrays and the proximity mapping function, the "map key," used. It is a form of bucket and radix sort.
| Property |
Value |
| dbo:abstract |
ProxmapSort, or Proxmap sort, is a sorting algorithm that works by partitioning an array of data items, or keys, into a number of "subarrays" (termed buckets, in similar sorts). The name is short for computing a "proximity map," which indicates for each key K the beginning of a subarray where K will reside in the final sorted order. Keys are placed into each subarray using insertion sort. If keys are "well distributed" among the subarrays, sorting occurs in linear time. The computational complexity estimates involve the number of subarrays and the proximity mapping function, the "map key," used. It is a form of bucket and radix sort. Once a ProxmapSort is complete, ProxmapSearch can be used to find keys in the sorted array in time if the keys were well distributed during the sort. Both algorithms were invented in the late 1980s by Prof. Thomas A. Standish at the University of California, Irvine. (en) |
| dbo:thumbnail |
wiki-commons:Special:FilePath/Insertion_Sorting_during_proxmap.png?width=300 |
| dbo:wikiPageExternalLink |
http://www.cs.uah.edu/~rcoleman/CS221/Sorting/ProxMapSort.html https://web.archive.org/web/20120314220616/http:/www.cs.uml.edu/~giam/91.102/Demos/ProxMapSort/ProxMapSort.c https://web.archive.org/web/20120712094020/http:/www.valdosta.edu/~sfares/cs330/cs3410.a.sorting.1998.fa.html http://www.ics.uci.edu/~jacobson/ics23/ProxmapHandout.pdf |
| dbo:wikiPageID |
29554327 (xsd:integer) |
| dbo:wikiPageLength |
14283 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1105478763 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Non-comparison_sorting dbr:Binary_search_tree dbr:University_of_California,_Irvine dbr:Insertion_sort dbr:Analysis_of_algorithms dbr:Comparison_sort dbc:Articles_with_example_pseudocode dbc:Sorting_algorithms dbr:Array_data_structure dbc:Stable_sorts dbr:Donald_Bren_School_of_Information_and_Computer_Sciences dbr:Sorting_algorithm dbr:Bucket_(computing) dbr:Bucket_sort dbr:Radix_sort dbr:Bucket_sorting dbr:File:Bucket_sort_1.png dbr:File:Bucket_sort_2.png dbr:File:Insertion_Sorting_during_proxmap.PNG dbr:File:ProxMapSortDemo.gif |
| dbp:caption |
Example of insertion sort sorting a list of random numbers. (en) |
| dbp:class |
dbr:Sorting_algorithm |
| dbp:data |
dbr:Array_data_structure |
| dbp:wikiPageUsesTemplate |
dbt:Citation_needed dbt:Cite_journal dbt:Clear dbt:ISBN dbt:Math dbt:OR dbt:Infobox_Algorithm dbt:Sorting |
| dct:subject |
dbc:Articles_with_example_pseudocode dbc:Sorting_algorithms dbc:Stable_sorts |
| rdf:type |
yago:WikicatSortingAlgorithms yago:WikicatStableSorts yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Category105838765 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Event100029378 yago:Idea105833840 yago:Kind105839024 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:SortingAlgorithm105847658 |
| rdfs:comment |
ProxmapSort, or Proxmap sort, is a sorting algorithm that works by partitioning an array of data items, or keys, into a number of "subarrays" (termed buckets, in similar sorts). The name is short for computing a "proximity map," which indicates for each key K the beginning of a subarray where K will reside in the final sorted order. Keys are placed into each subarray using insertion sort. If keys are "well distributed" among the subarrays, sorting occurs in linear time. The computational complexity estimates involve the number of subarrays and the proximity mapping function, the "map key," used. It is a form of bucket and radix sort. (en) |
| rdfs:label |
Proxmap sort (en) |
| owl:sameAs |
freebase:Proxmap sort yago-res:Proxmap sort wikidata:Proxmap sort dbpedia-fa:Proxmap sort dbpedia-sr:Proxmap sort https://global.dbpedia.org/id/4u9Ct |
| prov:wasDerivedFrom |
wikipedia-en:Proxmap_sort?oldid=1105478763&ns=0 |
| foaf:depiction |
wiki-commons:Special:FilePath/Bucket_sort_1.png wiki-commons:Special:FilePath/Bucket_sort_2.png wiki-commons:Special:FilePath/Insertion_Sorting_during_proxmap.png wiki-commons:Special:FilePath/ProxMapSortDemo.gif |
| foaf:isPrimaryTopicOf |
wikipedia-en:Proxmap_sort |
| is dbo:wikiPageWikiLink of |
dbr:Interpolation_sort |
| is foaf:primaryTopic of |
wikipedia-en:Proxmap_sort |
