How to sort a string that contains 0 and 1?

Question

JavaScript

There is a string that contains 0 and 1, example. 00010111010, you need to sort the string, 2 pairs can change places in each stage, example
0. 000 10 111 01 0
1. 0000 11 111 00
2. 00000011111
the question is that you need to shuffle TWO PAIRS of characters in each stage, I know caunt_sort very well, but the tasks are such that I can only mix in pairs.
in this example everything is ok, but this algorithm does not work in this example
010101
The correct sequence could be:
1. 01 0 10 1
2. 10 00 11
3. 00 1 01 1
4. 0 11 00 1
5. 000111
thanks in advance

Answer 1

See Flickity for examples , there is a similar example of a carousel towards the end.

Answer 2

Start by having a counter that keeps track of how many adjacent 1's you have at the back of the string.
Ie, 00110101111 => adjacent 1's = 4.
Try to find a pair that is 11. Swap that in front of the adjacent 1's and increment the counter by 2.
Ie, 100110101111 => 100100111111. Do this until there are non remaining.
Try to find a pair that is 01. Swap that in front of the adjacent 1's and increment the counter by 1. If the 01 is one character away from the adjacent 1's, you'll need to swap it forwards first.
Ie, 100010111111 => 101000111111 => 100001111111. Do this until there are non remaining.
If the string starts with a 10, swap it backwards, and move the resulting 01 in front of the adjacent 1's and increment the counter by 1. Ie, 100001111111 => 001001111111 => 000011111111.
This run's in O(n^2) operations average I beleive. I think there exists an algorithm that runs in O(n) operations however.

Answer 3

I probably misunderstood something, but why not just count the number of 1 and 0 in the line and then immediately print all 0 and then 1.

Answer 4

Straka
No need to sort Straka. And then Straka will be offended and hit
the author with a stick. Can you describe the task in more detail? It's better to write word for word.

Answer 5

php sort
c qsort

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}
 qsort (values, 6, sizeof(int), compare);

Answer 6

Outline of the algorithm:

int sort(char *line)
{
    unsigned prefix = strlen(line);
    while (prefix > 5 && !sorted(line)) {
        prefix = prefix - 1;
        if (*(line + prefix) == '0') {
            char const * at = stdchr(line, '1');
            if (at == line) {
                swap(line, line + 2);
                swap(line + 1, line + length - 1);
            }
            else {
                swap(at - 1, line + length - 1);
            }
        }
    }
    if (!sorted(line) && !bruteforce(line, prefix))
        return 0;
    return 1;
}

There are not enough:
1. The necessary headers
2. The implementation of the sorted function, which returns 0 if the string is already sorted, and not 0 otherwise
3. The implementation of the swap function, which swaps two non-intersecting pairs by pointers
4. The implementation of the bruteforce function, which sorts the prefix a string no longer than 5 characters by iterating over permutations, and returns 0 if the prefix could not be sorted (for example, for the string "101" or "1010"), and not 0 if it was possible to sort.
The invariant of the algorithm is simple, prefix is ​​the length of the unsorted part of the string. Moreover, all characters outside the prefix are equal to '1'. We decrease the prefix length by 1 each time until we sort the sequence, or until the prefix is ​​equal to or less than 5.
Where does the number 5 come from? All sequences of length 5 or more can be sorted by changing pairs, for smaller sequences this is not always possible.
There are 62 sequences of length <= 5 (32 + 16 + 8 + 4 + 2), so bruteforce does not take very long, but perhaps there is a smarter way to sort short sequences. Generally speaking, all unsortable sequences are easy to enumerate.
The algorithm is clearly not optimal.

Answer 7

Does the author have problems with the Russian language?

Answer 8

Another option:

#include <stdio.h>
#include <string.h>


bool sort_bin(char *aString);

int main()
{
    char str[] = "00010111010";

    printf("Before sort:\t%s\n", str);
    sort_bin(str);
    printf("After sort:\t%s\n", str);

    return 0;
}

bool sort_bin(char *aString)
{
    size_t len, zeros, sc;

    len = strlen(aString);
    zeros = 0;

    for (sc = 0; sc < len; ++sc) {
        if (aString[sc] == '0')
            zeros++;
        else if (aString[sc] != '1')
            return false;
    }

    memset(aString, '0', zeros);
    memset(aString + zeros, '1', len - zeros);

    return true;
}