Home | Projects | Notes > Problem Solving > LC - E - 1356. Sort Integers by The Number of 1 Bits (struct, qsort, bubble sort)

LC - E - 1356. Sort Integers by The Number of 1 Bits (struct, qsort, bubble sort)

Solutions in C

Solution 1

This solution uses struct and the C standard library function qsort.

Complexity Analysis:

• $T=O(n\log n)$$T = O(n\log n)$ where $n$$n$ is the length of the given array arr (qsort governs the time complexity)

• $S=O(n)$$S = O(n)$ since an array parr of size $n$$n$ is used

Solution:

xxxxxxxxxx
54
1
/**
2
 * Note: The returned array must be malloced, assume caller calls free().
3
 */
4

5
#include <stdlib.h> // qsort
6

7
typedef struct pair_t
8
{
9
    int elem;
10
    int bitcnt;
11
} pair_t;
12

13
int countBits(int n);
14
void sort(pair_t *parr, int arrSize);
15
int comp(const void *pair1, const void *pair2);
16

17
int* sortByBits(int* arr, int arrSize, int* returnSize){
18
    int i;
19
    *returnSize = arrSize;
20
    pair_t parr[arrSize];
21

22
    for (i = 0; i < arrSize; i++)
23
    {
24
        parr[i].elem = arr[i];
25
        parr[i].bitcnt = countBits(arr[i]);
26
    }
27

28
    // quick sort (T = O(nlogn))
29
    qsort(parr, arrSize, sizeof(pair_t), comp);
30

31
    for (i = 0; i < arrSize; i++)
32
        arr[i] = parr[i].elem;
33
    
34
    return arr;
35
}
36

37
int countBits(int n)
38
{
39
    int count = 0;
40

41
    while (n)
42
    {
43
        n &= (n - 1);   // clear least set bit of n
44
        count++;
45
    }
46

47
    return count;
48
}
49

50
int comp(const void *pair1, const void *pair2)
51
{
52
    pair_t *p1 = pair1, *p2 = pair2;
53
    return (p1->bitcnt != p2->bitcnt) ? (p1->bitcnt - p2->bitcnt) : (p1->elem - p2->elem);
54
}

Solution 2

This solution uses bubble sort.

Complexity Analysis:

• $T=O(n^2)$$T = O(n^2)$ where $n$$n$ is the length of the given array arr (bubble sort governs the time complexity)

• $S=O(n)$$S = O(n)$ since an array bits of size $n$$n$ is used

Solution:

xxxxxxxxxx
56
1
/**
2
 * Note: The returned array must be malloced, assume caller calls free().
3
 */
4
void swap(int *arr, int *bits, int i, int j);
5
int countBits(int n);
6

7
int* sortByBits(int* arr, int arrSize, int* returnSize){
8
    //int *bits = (int *)calloc(*returnSize, sizeof(int)); // array containing the number of bits
9
    int bits[arrSize];
10
    int i, j;
11
    
12
    *returnSize = arrSize;
13
    
14
    for (i = 0; i < arrSize; i++)
15
        bits[i] = countBits(arr[i]);
16

17
    // bubble sort (T = O(n^2))
18
    for (i = 0; i < arrSize; i++)
19
    {
20
        for (j = i + 1; j < arrSize; j++)
21
        {
22
            if (bits[i] > bits[j])
23
                swap(arr, bits, i, j);
24
            else if (bits[i] == bits[j] && arr[i] > arr[j])
25
                swap(arr, bits, i, j);
26
        }
27
    }
28

29
    return arr;
30
}
31

32
void swap(int *arr, int *bits, int i, int j)
33
{
34
    int temp;
35

36
    temp = arr[i];
37
    arr[i] = arr[j];
38
    arr[j] = temp;
39

40
    temp = bits[i];
41
    bits[i] = bits[j];
42
    bits[j] = temp;
43
}
44

45
int countBits(int n)
46
{
47
    int count = 0;
48

49
    while (n)
50
    {
51
        n &= (n - 1);
52
        count++;
53
    }
54

55
    return count;
56
}