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 O ( 1 ) {\displaystyle O(1)} 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.
Overview
Basic strategy In general: Given an array A with n keys:
map a key to a subarray of the destination array A2, by applying the map key function to each array item determine how many keys will map to the same subarray, using an array of "hit counts," H determine where each subarray will begin in the destination array so that each bucket is exactly the right size to hold all the keys that will map to it, using an array of "proxmaps," P for each key, compute the subarray it will map to, using an array of "locations," L for each key, look up its location, place it into that cell of A2; if it collides with a key already in that position, insertion sort the key into place, moving keys greater than this key to the right by one to make a space for this key. Since the subarray is big enough to hold all the keys mapped to it, such movement will never cause the keys to overflow into the following subarray. Simplied version: Given an array A with n keys
Initialize: Create and initialize 2 arrays of n size: hitCount, proxMap, and 2 arrays of A.length: location, and A2. Partition: Using a carefully chosen mapKey function, divide the A2 into subarrays using the keys in A Disperse: Read over A, dropping each key into its bucket in A2; insertion sorting as needed. Collect: Visit the subarrays in order and put all the elements back into the original array, or simply use A2. Note: "keys" may also contain other data, for instance an array of Student objects that contain the key plus a student ID and name. This makes ProxMapSort suitable for organizing groups of objects, not just keys themselves.
Example Consider a full array: A[0 to n-1] with n keys. Let i be an index of A. Sort A's keys into array A2 of equal size. The map key function is defined as mapKey(key) = floor(K).
Pseudocode
Here A is the array to be sorted and the mapKey functions determines the number of subarrays to use. For example, floor(K) will simply assign as many subarrays as there are integers from the data in A. Dividing the key by a constant reduces the number of subarrays; different functions can be used to translate the range of elements in A to subarrays, such as converting the letters A–Z to 0–25 or returning the first character (0–255) for sorting strings. Subarrays are sorted as the data comes in, not after all data has been placed into the subarray, as is typical in bucket sorting.
Proxmap searching ProxmapSearch uses the proxMap array generated by a previously done ProxmapSort to find keys in the sorted array A2 in constant time.
Basic strategy Sort the keys using ProxmapSort, keeping the MapKey function, and the P and A2 arrays To search for a key, go to P[MapKey(k)], the start of the subarray that contains the key, if that key is in the data set Sequentially search the subarray; if the key is found, return it (and associated information); if find a value greater than the key, the key is not in the data set Computing P[MapKey(k)] takes O ( 1 ) {\displaystyle O(1)} time. If a map key that gives a good distribution of keys was used during the sort, each subarray is bounded above by a constant c, so at most c comparisons are needed to find the key or know it is not present; therefore ProxmapSearch is O ( 1 ) {\displaystyle O(1)} . If the worst map key was used, all keys are in the same subarray, so ProxmapSearch, in this worst case, will require O ( n ) {\displaystyle O(n)} comparisons.
Pseudocode function mapKey(key) is return floor(key)
proxMap ← previously generated proxmap array of size n A2 ← previously sorted array of size n function proxmap-search(key) is for i = proxMap[mapKey(key)] to length(array) − 1 do if sortedArray[i].key == key then return sortedArray[i]
Analysis
Performance Computing H, P, and L all take O ( n ) {\displaystyle O(n)} time. Each is computed with one pass through an array, with constant time spent at each array location.
… excerpt ends here. Continue reading the full article.
