I've reviewed the sorting algorithms I can found, but I didn't see any kind of algorithm uses bits of numbers. I think, I create a new type of sorting algorithm. I named Bitsort. Descriptions are in github.
Do you know any sorting algorithm like this?
Complexity is O (nk). k is bit size of an element of array. Array order is not important. Every time complexity is O (nk). But it using a little bit much memory. It depends on N. But when N is increasing, memory is decreasing relatively. if N is 1, it is maximum memory ratio(R = Node/N)(=bitsize). if N is max, memory ratio decreasing to R = 2. So R*N is how many node is neccessery to store whole bit tree. If N is equal maximum ->(2^32 for integer) we need 2N node to store all array. Every node has 2 adress pointer.
Meanwhile N is not count of numbers in array. N is unique count of numbers.
if all elements in array is same, N is equal 1.
Summarize
Memory = P*N*R (P: pointer size, N: unique count, R: NodeCount(C)/N)
I create a formula for R for 32 bit integer.
R = 31 - 3.3*LOG10(N)
I put the numbers to binary tree from MSB(most significant bit) to LSB(Least significant bit). If they was added before, I am increasing the count of the leaf of value.
I only 1 time move on source array from begin to end and "sorting tree" has being filled.
void bitSort(int * array, int arraySize) {
int i, j;
Block* block;
clock_t start, end;
//create a buffer. root node is first node in buffer.
root = initBlockBuffer();
const unsigned long long digit = ((unsigned long long) 1) << (ARRAY_ELEMENT_TYPE_SIZE_1);
//for every array element (n !IMPORTANT)
for (i = 0; i < arraySize; i++) {
// start at root
Block* activeBlock = root;
register int value = array[i];
register int bit;
//for every bit of value (k !IMPORTANT)
for (j = 0; j < ARRAY_ELEMENT_TYPE_SIZE_1; j++){
//from msb to lsb get the bit
bit = (digit & (value << j)) >> (ARRAY_ELEMENT_TYPE_SIZE_1);
// get the related node from bit
block = activeBlock->node[bit];
// if the node is not exists
if (block == 0) {
// get next blank node from the buffer.
block = nextFreeBlock();
//connect new node to previous node
activeBlock->node[bit] = block;
}
// jump to new node.
activeBlock = block;
}
//after all last node is leaf.
//Getting from last bit of value
if(activeBlock->cnt[value & 1] == 0) leafCount++;
//and count of this leaf, increasing 1
activeBlock->cnt[value & 1]++;
}
}
Some results
if we create an array has 1000000(one million) 4bytes integer number as: - Same number - Increasing from 1 to 1000000 - Random uniform distribution
Same numbers
Leaf Count : 1
Node Count : 31
Node Size : 16 byte
Total Memory : 512 byte
Duration Sort : 178721 us (0.02s)
Duration Read : 4994 us (0.005s)
Increasing from 1 to 1000000
Leaf Count : 1000000
Node Count : 1000018
Node Size : 16 byte
Total Memory : 16000304 byte (16MB)
Duration Sort : 218556 us (0.2s)
Duration Read : 14321 us (0.01s)
Random uniform distribution
Leaf Count : 999768 (uniq numbers, >%0,02 repetition)
Node Count : 11181318
Node Size : 16 byte
Total Memory : 178913456 byte (179MB)
Duration Sort : 1460578 us (1.4s)
Duration Read : 666933 us (0.7s)
Is there an algorithm like that you know?
Example
Example: We suppose that we have 3 bit length numbers.
array = {7, 3, 2, 5, 0, 7, 3, 2, 7};
L : level
msb : most significant bit
lsb : least significant bit
msb lsb
L1 L2 L3
7 = 111 --> 1 1 1
3 = 011 --> 0 1 1
2 = 010 --> 0 1 0
5 = 101 --> 1 0 1
0 = 000 --> 0 0 0
7 = 111 --> 1 1 1
3 = 011 --> 0 1 1
2 = 010 --> 0 1 0
7 = 111 --> 1 1 1
firstly binary tree has only root node.
0_____________________|_____________________1
/ \
first number is added to binary tree using own bits from msb to lsb. (adding number: 7 =>(111)(3bit space))
0_____________________|_____________________1
L1 -----> \
0_________\_________1
L2 -----------------------------------------> \
0___\___1
L3 ----------------------------------------------------------> \
[1]
Then others sequently. (adding numbers: 3, 2, 5, 0)
0_____________________|_____________________1
/ \
0_________/_________1 0_________\_________1
/ \ / \
0___/___1 0___\___1 0___/___1 0___\___1
/ / \ \ \
[1] [1] [1] [1] 1
if a number is already in tree, its count is increased 1. (numbers: 7, 3, 2, 7)
0_____________________|_____________________1
/ \
0_________/_________1 0_________\_________1
/ \ / \
0___/___1 0___\___1 0___/___1 0___\___1
/ / \ / \ / \
[1] [2] [2] [1] [3]
When it is read recursively, can be get sorted array.
sorted_array = [1x(000), 2x(010), 2x(011), 1x(101), 3x(111)]
sorted_array = [1x0, 2x2, 2x3, 1x5, 3x7]
sorted_array = [0, 2, 2, 3, 3, 5, 7, 7, 7]
