Vahe Dandanyan

Набросок алгоритма:

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;
}

Тут не хватает:

1. Нужных заголовков
2. Реализации функции sorted, которая возвращает 0, если строка уже отсортирована, и не 0 иначе
3. Реализации функции swap, которая меняет местами две неперсекающиеся пары по указателям
4. Реализации функции bruteforce, которая сортирует префикс строки длинной не более 5 символов перебором перестановок, и возвращает 0, если не удалось отсортировать префикс (например, для строки "101" или "1010"), и не 0, если удалось отсортировать.

Инвариант алгоритма простой, prefix - длина неотсортированной части строки. Более того все символы за пределами префикса равны '1'. Мы каждый раз уменьшаем длину префикса на 1, пока не отсортируем последовательность, либо пока префикс не станет равен или меньше 5.

Откуда берется число 5? Все последовательности длинны 5 и более можно отсортировать меняя пары, для меньших последовательностей это не всегда возможно.

Последовательностей длинны <= 5 всего 62 (32 + 16 + 8 + 4 + 2), так что bruteforce занимает не очень много времени, но возможно есть и более разумный вариант сортировки коротких последовательностей. Вообще говоря все несортируемые последовательности легко перечислить.

Алгоритм понятное дело не оптимальный.