Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Proxmap sort
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.
In general: Given an array A with n keys:
Simplied version: Given an array A with n keys
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.
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).
Hub AI
Proxmap sort AI simulator
(@Proxmap sort_simulator)
Proxmap sort
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.
In general: Given an array A with n keys:
Simplied version: Given an array A with n keys
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.
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).