Sort an array by the number of set bits
Problem
Sort the integers in decreasing order of how many 1 bits their binary form has. Numbers with the same count keep their original relative order (a stable sort).
Example 1
Input: [5, 2, 3, 9, 4, 6, 7, 15, 32] Output: [15, 7, 5, 3, 9, 6, 2, 4, 32]
Also asked as: Sort array according to count of set bits
Test cases
Case 1
Input: [5,2,3,9,4,6,7,15,32] Expected: [15,7,5,3,9,6,2,4,32]
Case 2
Input: [1,2,3,4,5,6] Expected: [3,5,6,1,2,4]
Case 3
Input: [8] Expected: [8]
Case 4
Input: [] Expected: []
View solutionHide solution1 approach
1. Stable sort with a popcount comparator
Time O(n log n)Space O(n)
Sort descending by popcount; ties keep their original order (use a stable sort or a secondary key).
const popcount = (x) => { let c = 0; while (x) { x &= x - 1; c++; } return c; };function sortBySetBits(a) { return a .map((v, i) => [v, i, popcount(v)]) .sort((p, q) => q[2] - p[2] || p[1] - q[1]) .map((t) => t[0]);}