CareerCup

Bucketize numbers based on the number of bits set on them. Then sort each of the buckets individually in normal sorting fashion and then just print them with 0-32 bucket. This avoid repeated computation of the set bits in numbers and also potentially reduces sorting time as each bucket could be as small as initial set /32, but of course not in place.

Replace number n by (number_of_bits(n), n). Now do a lexicographic sort using the tuples.

1. traverse through the number, for each number, reset the lowest bit using n & (n - 1), if the number becomes zero, append it to the result list.
2. And then traverse through the number again, if the number is not zero, do the same operation.
3. repeat 2 until the result list length equals to n

def sort_by_bits2(n):
	array = [x + 1 for x in range(n)]
	result = []
	while len(result) != n:
		for i in range(len(array)):
			if array[i] != 0:
				array[i] &= (array[i] - 1)
				if array[i] == 0:
					result.append(i + 1)
	return result

it will take O(n*log(n)*log(d)) time, and can't be done in less number of operation, you apply any sort : heap sort, merge sort, quick sort, etc., you always have to compare two element, not two element are not of single length, their length can be up to log(d), so every comparison will take log(d) operation, and all comparison sort take O(n*log(n)) comparison, now you can calculate the complexity

Traverse the numbers from 1 to n... whenever you see a number that is a power of 2 (including 2^0 = 1), output it... now traverse again, and print all the numbers that are not powers of 2, in the same order...

for example, if n = 8, the output would be 1, 2, 4, 8, 3, 5, 6, 7

def sort_by_bits(n):
	array = sorted([(get_bit_number(x + 1), x + 1) for x in range(n)])
	return [x[1] for x in array]
	
def get_bit_number(n):
	result = 0
	while n != 0:
		n = n & (n - 1)
		result += 1
	return result

int maxNumOfBits=-1
for i=1 to n
maxNumOfBits=max(maxNumOfBits,numOfBits(num[i]));
//create an array of linkedLists, the size will for the list is maxNumOfBits
Array<LinkedList> list=new List<LinkedList>[maxNumOfBits];
for i=1 to n
list[numOfBits(num[i])].appendToTheEnd(num[i]);

for n=1 to n
print list[n];

Could be done effectively and easily with the use of heaps.
Rule should be to use # of bits and if bits are equal, then base 10 value.

First heapify and then dismantle heap. All done.

O(nlog(n).

n(log n) solution due to heapsort.

public class SortBits {

    public static void main(String args[]) {
        SortBits t = new SortBits();
        t.sort(5);
    }

  void sort(int n) {
      Heap heap = new Heap(n);
      for(int i = 1; i <= n; i++) {
         Num num = new Num();
         num.value = i;
         num.numBits = getNumBits(i);
         heap.insert(num);
      }
      for(int i = 1; i <= n; i++) {
         Num num = heap.extractMin();
         System.out.println(num.numBits+", "+num.value);
     }
  }
  int getNumBits(int n) {
      int count = 0;
      while(n>0) {
          if(n%2==1)
              count++;
          n = n/2;
      }
      return count;
  }
}

class Num {
    public int numBits;
    public int value;
}

class Heap {
    int s;
    int size;
    Num[] array;

    public Heap(int size) {
        this.size = size;
        s = 0;
        array = new Num[size];
    }

    public void insert(Num num) {
        array[s] = num;
        s++;
        bubbleUp(s-1);
    }

    public Num extractMin() {
        Num num = array[0];
        s--;
        array[0] = array[s];
        bubbleDown(0);
        return num;
    }

    void bubbleUp(int i) {
        if(i<=0)
            return;
        if(i>=s)
            return;
        if(isSmaller(i, getParent(i))) {
            swap(i, getParent(i));
            bubbleUp(getParent(i));
        }
    }
    void swap(int i, int j) {
        Num temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    int getParent(int i) {
        return i/2;
    }
    int getYoungChild(int i) {
        return 2*i+1;
    }
    void bubbleDown(int i) {
        if(i<0)
            return;
        if(i>=s)
            return;
        int c1 = getYoungChild(i);
        int c2 = c1+1;
        int minIndex = 0;
        if(c1>=s)
          return;
        if(c1==s-1)
            minIndex = c1;
        else {
            if(isSmaller(c1, c2))
                minIndex = c1;
            else
                minIndex = c2;
        }


        if(isSmaller(minIndex, i)) {
            swap(minIndex, i);
            bubbleDown(minIndex);
        }

    }
    boolean isSmaller(int i, int j) {
        if(array[i].numBits < array[j].numBits)
            return true;
        else if(array[i].numBits > array[j].numBits)
            return false;
        else if(array[i].value <= array[j].value)
            return true;
        else
            return false;
    }
}

how about this :
for i = 1 to n:
put i into a bucket_(#bits_in_i) (a queue that you would add i to )
then result = read bucket_1, bucket_2,...bucket_(ceiling of log_2 (n))

bucket_(#bits_in_i) is a queue that has those numbers i that have #bits_in_i set bits
I think that this is O(n)

generate the numbers with i set bits not greater than n from 2 ^ i - 1

ideone.com/qajp85

public int[] sort(int n)
        {
                int[] a = new int[n];
                int k = 0;
                for(int i = 1; i <= n; i = ((i + 1) << 1) - 1) 
                        for(int j = i; j <= n; j = next(j)) 
                                a[k++] = j;
                return a;
        }
 
        private int next(int n)
        {
                //n       1 0001 1100
                //s       0 0000 0100 n & (-n)
                //r       1 0010 0000 n + s
                //ones    0 0011 1100 n ^ r
                //ones    0 0000 0011 (ones >> 2) / s
                //return  1 0010 0011 r + ones  
                int smallest = n & (-n);
                int ripple = n + smallest;
                int ones = n ^ ripple;
                ones = (ones >> 2) / smallest;
                return ripple + ones;
        }

Below is a linear algorithm

void sortOnBits(int N) {
  int maxBits = ceil(log N);
  int mask=0;
  for (int i=1; i<=maxBits; i++) {
    mask=(mask<<1)|1;
    if (mask>N) break;
    temp=mask;
    while(temp<N) {
       cout << temp;
       temp=temp<<1;
    }
  }
}

Logic:
- Print all numbers that have one bit set, then two bits and so on
- To get the numbers in increasing order which have the same number of bits set, we start by initializing the least significant bits, and then keep shifting right until N