Kак сортировать стрoку, которая содержит 0 и 1?

Question

[Vahe Dandanyan]

Есть строка, которая содержит 0 и 1, пример. 00010111010, надо сортировать строку, 2 пары могут измениться местами в каждом этапе, пример
0. 00010111010
1. 00001111100
2. 00000011111
вопрос в том что надо перемешать ДВА ПАР символов в каждом этапе, я отлично знаю caunt_sort, но задания такаяа, что могу перемешать только парами.
в этом примере все ок, но в этом этот алгоритм не работает
010101

The correct sequence could be:
1. 010101
2. 100011
3. 001011
4. 011001
5. 000111
заранее спасибо

Comments

[AlexP11223]

Что за этапы? По-моему символы просто отсортированы по возрастанию.

[Vahe Dandanyan]

могу изменить местами толька два пара в каждом этапе цикла

[Push Pull]

@dvva
ничего не понятно, нужно поэтапно сортировать?
нельзя сразу по возрастанию?

[Vahe Dandanyan]

нужно сортировать по возрастанию, но надо сровнить только
парами!

[Миша Кринкин]

@dvva а вы в курсе, что отсортировать последовательность таким образом не всегда возможно? Например, 010 или 0101 или 1010, может вы чего-то забыли из условий задания?

[ManWithBear]

@kmu1990 всё нормально сортируется, 010 - первая пара 01, вторая 10

[Миша Кринкин]

@ManWithBear и как вы в последовательности 010 предлагаете менять местами две пересекающие пары? Не очень понимаю, что это за операция такая

[ManWithBear]

@kmu1990 ваша правда, не совсем понял условие.

[Миша Кринкин]

@ManWithBear ну или я его не совсем понял, в данном случае все возможно :)

[ManWithBear]

@dvva автор, напишите полное дословное условие задачи, либо расскажите для чего вам это нужно, возможно смысл задания немного другой

[AlexP11223]

@dvva задание на английском что ли было? Ну и скинул бы на нем, а не рождал всякие "два пар".

[Vahe Dandanyan]

да я думал в этом форуме строго на русском@AlexP11223

[Vahe Dandanyan]

@AlexP11223 но сейчас понятно или нет??

[AlexP11223]

@dvva неа, странное задание все равно, не хватает деталей. Выше вон, например, написали о невозможности сортировки 1010 таким образом.

Answer 1

[Vahe Dandanyan]

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.

Comments

[ManWithBear]

@dvva what will you do with strings like 0101 and 01010?

Answer 2

[Александр Таратин]

Я, наверное, чего-то недопонял, но почему просто не подсчитать количество 1 и 0 в строке и не вывести потом сразу сначала все 0, а потом 1.

Comments

[Никита Маркелов]

Так называемая сортировка черпаком.
P.S. это на заметку ТС.

Answer 3

[Кирилл]

Страка
Не надо Страку сортировать. А то Страка обидится и клюшкой надает

Автор, вы можете подробнне описать задачу? Лучше переписать слово в слово.

Comments

[Vahe Dandanyan]

ок

Answer 4

[Push Pull]

php sort
c qsort

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

Comments

[deleted]

единственный достойный ответ

[jcmvbkbc]

не единственный, @zayac_agito , подсчёт нулей и единиц тоже хорош.

Answer 5

[Миша Кринкин]

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

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 занимает не очень много времени, но возможно есть и более разумный вариант сортировки коротких последовательностей. Вообще говоря все несортируемые последовательности легко перечислить.

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

Answer 6

[Сергей Мельников]

у автора проблемы с русским языком?

Comments

[Push Pull]

большие, реквестирую жалобы на вопрос

[Vahe Dandanyan]

А что непонятно?

[Push Pull]

@dvva все понятно, но ваш вопрос нарушал правила русского языка
вам не подходит sort?

[Vahe Dandanyan]

я могу затаь вапрос на англиском или на немецком, как вам удобно?

[Push Pull]

@dvva "я могу затаь вапрос " - какой ваш родной язык?
я ответил на ваш вопрос, что вам не нравится?

Answer 7

[drozdVadym]

Еще вариант:

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

Comments

[Vahe Dandanyan]

@dvva спасибо за ответ, но вопрос в том что надо перемешать два пара символа в каждом этапе, я отлично знаю caunt_sort, но задания такаяа, что могу перемешать только парами