Proximity Map Sorting

Created on 2023-07-11T08:23:53-05:00

Return to the Index

This card can also be read via Gemini.

Array size: number of buckets in the proximity map.

Hit count: count of items that hashed to a particular bucket.

Location: Location[x] correlates to a record in Data[x]; but this stores which hash bucket the element belongs to.

Proximity map: Holds the first index (of the Data array) for an element that hashes to this bucket. Elements defined in ProxMap[x] have an above zero value in HitCount[x]

Data: array which holds the elements within the map

Step 1: initialize memory, helper arrays.

Step 2: hash members of unsorted array to find the buckets they will belong to and count memberships

Step 3: insertion sort elements of the unsorted array to their neighborhood in the sorted array


ProxMaps want a hash function where keys can be kept in ascending order as well as spread evenly across the buckets.

The college paper uses a technique: