This is a bit based sorting algorithm for integer and float numbers. This follows counting sort principle. This one behaves as a set and uses bitset. This is the old version of BitBasedSortingAlgorithm.cpp

BitBasedSortingAlgorithmSetBitsetOLD.cpp

/**
 * By: Asif Ahmed
 * TODO: Instead of set increment val_count to reflect duplicate values.
 */



#include<bits/stdc++.h>
using namespace std;

#define TOTALBITS 6
#define N 16


typedef struct alist anode;
struct alist{
    int val_count;
    int val;
    anode *next;
    anode *prev;
};

typedef struct bstree bnode;
struct bstree{
    int bit;
    bnode *left;
    bnode *right;
    anode *p;
};


void printGivenLevelLeft(bnode* root, int level)
{
    if (root == NULL)
        return;
    if (level == 1)
        printf("%d ", root->p->val);
    else if (level > 1)
    {
        printGivenLevelLeft(root->left, level-1);
        printGivenLevelLeft(root->right, level-1);
    }
}

int executionCount = 0;
void printGivenLevelRight(bnode* root, int level)
{
    ++executionCount;
    if (root == NULL)
        return;
    if (level == 1)
        printf("%d ", root->p->val);
    else if (level > 1)
    {
        printGivenLevelRight(root->left, level-1);
        printGivenLevelRight(root->right, level-1);
    }
}


int main(){

    bitset<TOTALBITS> S;
    int unsorted[N] = {2,3,0,10,7,31,27,54,29,7,9,1,9,3,2,7};


    // create R root
    bnode *R;
    R = new bnode();


    // access inside main
    anode* aroot;


    // For the first time this is needed but can be avoided
    if(unsorted[0]){
        S = unsorted[0];
        cout << S << endl;

        // create anode beforehand for the first time
        aroot = new anode();
        aroot->val = unsorted[0];
        aroot->val_count = 1;
        aroot->prev = NULL;
        aroot->next = NULL;

        // create temp root
        bnode* r = R;


        // For each of the bits create node and connect to tree
        for(int i = TOTALBITS - 1; i >= 0; --i){
            bnode *temp = new bnode();
            temp->bit = S[i];
            temp->p = aroot;
            if(S[i]){
                r->right = temp;
            }else{
                r->left = temp;
            }
            r = temp;
        }
        r->left = NULL;
        r->right = NULL;
    }


    // hold bottom level alist root in a temporary root
    anode *arootTemp = aroot;


    // For all other inputs
    for(int j = 1; j < N; ++j){
        S = unsorted[j];

        // create temp root
        bnode* r = R;

        //
        bool createOnce = true;
        anode *an;

        //
        cout << "==================\n";
        cout << "USING: " << S << "\n";

        // For each of the bits create node and connect to tree
        for(int i = TOTALBITS - 1; i >= 0; --i){

            cout << "USING BIT: " << S[i] << "\n";

            // If bit is zero then go left otherwise go right
            if(S[i]){
                if(r->right != NULL){
                    cout << "FOLLOWING LAID OUT PATH RIGHT: " << "\n";
                    r = r->right;
                }else{
                    cout << "CREATING NEW NODE RIGHT: " << "\n";
                    if(createOnce){
                        an = new anode();
                        an->next = NULL;
                        an->prev = NULL;
                        an->val = unsorted[j];
                        an->val_count = 1; // If this is done it acts as a set
                        createOnce = false;
                    }
                    bnode *tmp = new bnode();
                    tmp->left = NULL;
                    tmp->right = NULL;
                    tmp->p = an;

                    // now mark tmp as the new r
                    r->right = tmp;
                    r = tmp;
                }
            }else{
                if(r->left != NULL){
                    cout << "FOLLOWING LAID OUT PATH LEFT: " << "\n";
                    r = r->left;
                }else{
                    cout << "CREATING NEW NODE LEFT: " << "\n";
                    if(createOnce){
                        an = new anode();
                        an->next = NULL;
                        an->prev = NULL;
                        an->val = unsorted[j];
                        an->val_count = 1; // If this is done it acts as a set
                        createOnce = false;
                    }
                    bnode *tmp = new bnode();
                    tmp->left = NULL;
                    tmp->right = NULL;
                    tmp->p = an;

                    // now mark tmp as the new r
                    r->left = tmp;
                    r = tmp;
                }
            }
        }
    }
    printf("===================\nDone\n===================\n");


    // now run DFS to sort
    // r is a node* that was defined above
    bnode* r;
    r = R->left;
    printGivenLevelLeft(r, TOTALBITS);
    r = R->right;
    printGivenLevelRight(r, TOTALBITS);

    printf("\n===========================================\n");
    printf("\nLOOP EXECUTION COUNT: %d \n", executionCount);

    return 0;
}