[Attempt] Binary array (1,0) sorting in O(1)

[Attempt] Binary array (1,0) sorting in O(1)

Here we try to sort a binary array consisting of zeros and ones. This sorting problem can be also considered as a list summation problem or ones counting problem.

Firstly, we use a uniformly distributed binary array generated by numpy as the raw test array.

# generate random binary list
p = 0.5
size = 10
test_arr = np.random.binomial(1, p, size).astype(np.str0)

Secondly, as a perporcessing step, we convert the list (array) to a decimal number. Unfortunately, this step cannot be guaranteed to be in time complexity O(1).

test_list = list(test_arr)
test_arr_string_int = int(''.join(test_list))

Then, we can count ones in the decimal number by adding the digits. To make the adding process in O(1), the summation is calculated as follows.

digit sum = (num_value-1) % 9 + 1
Leetcode 258.

# count ones in the list
test_arr_ones_count = (test_arr_string_int-1) % 9 + 1

Finally, the array of desired order can be generated by the number of ones.

# zeros after ones
res_arr_1 = np.ones(test_arr.shape)
res_arr_1[test_arr_ones_count:] *= 0
# ones after zeros
res_arr_0 = np.ones(test_arr.shape)
res_arr_0[:test_arr_ones_count] *= 0

Example result

numpy random seed: 0
generate random binary list: 
['1' '1' '1' '1' '0' '1' '0' '1' '1' '0']
convert list to (string) to int:(no guarantee of O(1)
['1', '1', '1', '1', '0', '1', '0', '1', '1', '0']
1111010110
count ones in the list:
7
generate new list of desired order:
[1. 1. 1. 1. 1. 1. 1. 0. 0. 0.]
[0. 0. 0. 0. 0. 0. 0. 1. 1. 1.]

After numbers of test, we found the time consumptions of different length (vaules) of arrays are not exactly the same. This might mean that the whole process is not strictly O(1). This could be due to the following reasons.

1. String, integer converting process.
2. Numpy array slicing process.
3. Instability of the machine.

Complete code

import numpy as np
import time
# np.random.seed(0)
# print('generate random binary list: ')
# generate random binary list
for i in range(100):
    p = 0.5
    size = np.random.randint(100)
    test_arr = np.random.binomial(1, p, size).astype(np.str0)
    # print(test_arr)
    # print('convert list to (string) to int:(no guarantee of O(1)')
    # convert list to (string) to int:(no guarantee of O(1)
    test_list = list(test_arr)
    # print(test_list)
    test_arr_string_int = int(''.join(test_list))
    start = time.time()
    # print(test_arr_string_int)
    # print('count ones in the list:')
    # count ones in the list
    test_arr_ones_count = (test_arr_string_int-1) % 9 + 1
    # print(test_arr_ones_count)
    # print('generate new list of desired order:')
    # zeros after ones
    res_arr_1 = np.ones(test_arr.shape)
    res_arr_1[test_arr_ones_count:] *= 0
    # ones after zeros
    res_arr_0 = np.ones(test_arr.shape)
    res_arr_0[:test_arr_ones_count] *= 0
    # print(res_arr_1)
    # print(res_arr_0)
    print("{} th test, array len:{}, time usage: {}".format(i, size, time.time()-start))