Binar--Binar Sort, Binar Shuffle, and Binar Search the Big Three of Algorithms

The three areas of algorithms are sort (order data into a specific permutation), shuffle (scramble data into random permutation), search (structure data into indexed permutation).

Binar

Two of three algorithms are in the "binar" category. By binar is meant "binarY" not the two associations often with the word "binar" which are: The Bynar aliens from Startrek The Next Generation The Goa'uld Bynarr from Stargate SG-1.

Binar Algorithms

The binar sort orders any datum using a bit extraction function to partition the datum into M-partitions by exchange of the N-elements. The binar sort is like a quick sort in partitioning, only no pivot element, and from 2 <= M < N sub-arrays.

The binar shuffle scrambles datum by using a bit extraction function, but to randomly move and exchange data elements. One interesting property of the binar shuffle is reversibility--the binar shuffle is invertible. The final permutation can be returned to the original permutation (something I need to add, along with a basic proof in the research monograph) by an inverse function.

Binar Search

The simplest search is to use the binar sort to organize that data elements into an ordered permutation, and then use a binary search to find an element. The Big-Oh for such an algorithm is O(c*N) + O(M*lg N) where M is the number of searches, and N is the number of elements.

Consider the following values:

• 2048-search operations, M=2048 or 2^12
• 65536-elements, N=65536 or 2^16, lg N = 16 = 2^4

• Complexity: O(c*2^16) + O(2^12 * 2^4) = O(c*2^16) + O(2^16) = O(2*c*2^16) or 2*c*2^16 or c*2^17

Thus the binar sort is efficient, but for a sufficiently large data set, and many searches the complexity of the binar sort-binary search approaches that of twice sorting the data elements. If the value of M increases beyond the value of N (which is logical to presume...more searches on the data set once ordered) the binary search becomes linearithmic when M >= N, or O(c*N) + O(N * lg N).

Variation of Shuffle and Sort

The binar search is a variation upon the binar sort and binar shuffle. The actual bit extraction function is changed--instead of creating an ordered or random permutation, the bit function will map data elements, or create an index an organize the data elements accordingly. The array of data elements is unorganized initially, in a random permutation. The binar search will arrange the elements by an index computed by the bit extraction function, and position each element by the index--hash the elements into a hash table.

Search and Sort

This might seem unusual, but the proxmap sort by Standish also has a proxmap search. The binar sort simply puts data elements into an ordered permutation where the organization is dependent upon the predecessor and successor element in the permutation. The binar search first maps the data elements, and then each data element is accessed or searched for after the mapping.

The complexity of searching involves:

1. index data, pre-process, create permutation - O(N)
2. search data, use search function -- constant O(c)

For the number of searches M, there are two possibilities:

1. O(c*N) + O(M*c) when M < N
2. O(c*N) + O(c*M) = O(2*c*N) when M >= N (doesn't become linearithmic)

Searching

A search after mapping the data in an array can use the same bit extraction function to find data elements. With the right design of a bit extraction function, data elements related by the mapping function mapped into a partition are accessible. Instead of a complete bit extraction function at a constant time c, a lesser constant k < c is useful to find a data element, or a group of data elements.

Thus the complexity when M < N is O(c*N) + O(k*M) for a search, or O(c*N) + O(k*N) when M >= N. More simply, O((c+k)*N) for a search function that does not require the entire bit extraction function to find an element.

Bit Extraction Function

The core of a binar search is the bit extraction function to map a data element to an index, and then use the bit extraction function to access an element or elements. In effect, a search is an insert--but instead of putting an element into the array, it is a virtual insert to verify if an element is in the array.

Number of Permutations

For the number of permutations, each operation has a number of significant, possible permutations.

1. Sort - create ordered permutation ( 2-permutations) only ascending/descending
2. Shuffle - create random permutation ((N!-2)-permutations) exclude sorted 2-permutations
3. Search - create indexed permutation ( N!-permutations) any possible permutation

The ranking of permutations is 2 < N!-2 < N! which is an interesting relationship among the permutations. Consider permutation rankings is sort < shuffle < search.

Binar Search--the Missing Algorithm

The binar sort algorithm was the first binar algorithm, but with the right bit extraction function, could also unsure or shuffle, the second binar algorithm. The third algorithm is the binar search, and using the bit extraction function can take an array of elements and map them into a particular permutation that can be searched after processing. Hence searching, shuffling, and sorting are the same algorithm, a binar algorithm--just change or modify the bit extraction function.

Someday I'll have to write a research monograph about the binar search, just as I have for the binar sortand the binar shuffle. Until that day then...someday