Sorting arrays - least steps-CodePudding

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!!

CodePudding user response：

ar = [0,0,0,1,0,1,0]
ar.sort()
print(ar)

CodePudding user response：

If you don't want to use .sort() or similar stuff I can think of that solution:

arr = [0,0,0,1,0,1,0]
print([0] * arr.count(0)   [1] * arr.count(1))

Which ends up in [0, 0, 0, 0, 0, 1, 1]

Edit:

l = len(arr)
z = arr.count(0)
print([0]*z   [1] * (l - z))

seems to be faster with timeit.timeit

CodePudding user response：

Many languages have their own implementation.

Example for javascript:

[0,0,0,1,0,1,0].sort();

returns

[ 0, 0, 0, 0, 0, 1, 1 ]

Edited: adding my own implementation on javascript.

The strategy was navigate from the begin and stop when found 1, and then navigate from the end to found 0 to swap.

It's one of multiple possible implementations.

function sortBinaryArray(binArr){
    let i = 0;
    let j = binArr.length;
    let swapCount = 0;
    while(i < j){
        if(binArr[i] === 0) {
            // found 0 on  position i. Its sorted until now.
            i  ;
            continue;
        }
        // Found 1 on posittion i. Search from the end for 0 to swap
        j--;
        while(i < j){
            if (binArr[j] === 0) {
                // Found position to swap
                binArr[i] = 0;
                binArr[j] = 1;
                swapCount  ;
                break;
            }
            j--
        }
    }
    console.log('swapCount=' swapCount);
}

var myArr = [0,0,0,1,0,1,0];
sortBinaryArray(myArr);
console.log(myArr)

output:

swapCount=1
Array(7) [ 0, 0, 0, 0, 0, 1, 1 ]

CodePudding user response：

You don't need to sort a binary array, especially with python's small integer interning.

The count of ones is given by

ones = sum(lst)

The count of zeros is the length minutes that:

zeros = len(lst) - ones

You can construct the right list with

[0] * zeros   [1] * ones