text: Sort an array according to count of set bits | a utility function that returns total set bits count in an integer ; Function to sort according to bit count This function assumes that there are 32 bits in an integer . ; Traverse through all bit counts ( Note that we sort array in decreasing order ) ; Utility function to pran array ; Driver Code
code: def countBits ( a ) : NEW_LINE INDENT count = 0 NEW_LINE while ( a ) : NEW_LINE INDENT if ( a & 1 ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT a = a >> 1 NEW_LINE DEDENT return count NEW_LINE DEDENT def sortBySetBitCount ( arr , n ) : NEW_LINE INDENT count = [ [ ] for i in range ( 32 ) ] NEW_LINE setbitcount = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT setbitcount = countBits ( arr [ i ] ) NEW_LINE count [ setbitcount ] . append ( arr [ i ] ) NEW_LINE DEDENT for i in range ( 31 , - 1 , - 1 ) : NEW_LINE INDENT v1 = count [ i ] NEW_LINE for i in range ( len ( v1 ) ) : NEW_LINE INDENT arr [ j ] = v1 [ i ] NEW_LINE j += 1 NEW_LINE DEDENT DEDENT DEDENT def printArr ( arr , n ) : NEW_LINE INDENT print ( * arr ) NEW_LINE DEDENT arr = [ 1 , 2 , 3 , 4 , 5 , 6 ] NEW_LINE n = len ( arr ) NEW_LINE sortBySetBitCount ( arr , n ) NEW_LINE printArr ( arr , n ) NEW_LINE