Proxmap

A Synopsis of ProxmapSort & ProxmapSearch

• • invented late 1980's by Thomas A. Standish, Prof. Emeritus, Dept. of Informatics, UC Irvine for in-depth discussion see ““Using O(n) ProxmapSort and O(1) ProxmapSearch to motivate CS2 students (Part 1)” http://portal.acm.org/citation.cfm?id=1113847.1113874 and “…(Part II)” http://portal.acm.org/citation.cfm?id=1138403.1138427

The Proxmap • Basic strategy Given an array: — map a key to a part of—a subarray of—the destination array A2 by applying a "mapkey" function to each array item — figure out how many keys will map to the same subarray this is an array of "hit counts," H — figure out where each subarray will begin so that each subarray is exactly the right size to hold all the keys that will map to it this is an array of "proxmaps," P — for each key, compute the subarray into which it will map this is an array of "locations," L — For each key, look up its location place it in that cell of A2 if it "collides" with an key already in that position, insert the key into the subarray at position that maintains the order of the keys, moving keys > this key to the right one cell in order to free up a space for this key: Since the subarray is large enough to hold all keys that map to it, such movement will never cause the keys to move into the following subarray. Example and associated pseudocode: cell indices begin at 0 6.7 5.9 8.4 1.2 7.3 3.7 11.5 1.1 4.8 0.4 10.5 6.1 1.8

• A

lastUsed – A.length – 1; MapKey(K) = floor(K) ; largestMapKey = 11; for i = 0 to largestMapKey H[i] = 0; for i = 0 to lastUsed { pos = MapKey(A[i]); H[pos] = H[pos] + 1; } A 6.7 H 1 5.9 3 8.4 0 1.2 1 7.3 1

// last used position of array of keys to sort // MapKey(K) will range from 0 to 11, so define H, P to be of size 12 // compute hit counts

3.7 1

11.5 2

1.1 1

4.8 1

0.4 0

10.5 1

6.1 1

1.8

runningTotal = 0; // compute proxmap – location of start of each subarray for i = 0 to largestMapKey if H[i] = 0 P[i] = -9;...