Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
MSB radix sort solution in Speedy category for Count Inversions by ale1ster
def count_inversion(seq):
#Normalize sequence
d = min(seq)
seq = [el - d for el in seq]
#Find maximum _on_ bit, which will decide the iteration depth
bitlen = max(map(lambda n: n.bit_length(), seq)) - 1
#Calculate groups and partial disorders
displaced, seq_list = 0, [seq]
while bitlen >= 0:
next_seqlist = []
for part in seq_list:
cur_part_split = {0: [], 1: []}
previous_1s_in_part = 0
for num in part:
cur_dig = 1 if (num & (2 ** bitlen)) else 0
previous_1s_in_part += cur_dig
cur_part_split[cur_dig].append(num)
displaced += previous_1s_in_part * (cur_dig == 0)
next_seqlist.extend(cur_part_split.values())
seq_list = [subseq for subseq in next_seqlist if len(subseq) > 1]
bitlen -= 1
return displaced
Sept. 3, 2014
Comments: