I wonder what is the best algorithm to sort binary array with least swaps? (having array eg [0,0,0,1,0,1,0] to become [0,0,0,0,0,1,1]).
I implemented some bubble sorts but wonder what is the optimisation for those?
My code is in python, but any language is welcomed, if anyone has a solution for the least swaps that would really improve my program and i would really appreciate!!
If you really want to do it using swaps, you can start from both ends and swap the 1s you find on the left side going forward with the 0s you find on the right side going backward.
A = [0,0,0,1,0,1,0] left1s = (i for i,b in enumerate(A) if b==1) right0s = (len(A)-j for j,b in enumerate(reversed(A),1) if b==0) swapCount = 0 for i,j in zip(left1s,right0s): if i>=j:break A[i],A[j] = A[j],A[i] swapCount += 1 print(A) # [0, 0, 0, 0, 0, 1, 1] print(swapCount,"swaps") # 1 swaps