2

Вечер добрый! Есть двумерный массив, в котором содержится n-ое количество строк. Каждая строка представляет собой последовательность нулей и единиц, к примеру:

0 1 1 0 1 0 1
1 0 0 0 1 1 0
0 0 0 0 1 1 0
1 0 0 0 1 0 0
1 1 1 1 0 0 1
1 1 1 0 1 0 1

Надо отсортировать его построчно, но не каждую строку отдельно, а просто разместить строки по вертикали в нужном порядке. К примеру, для этого массива сортировка будет выглядеть так:

1 1 1 1 0 0 1
1 1 1 0 1 0 1
1 0 0 0 1 1 0
1 0 0 0 1 0 0
0 1 1 0 1 0 1
0 0 0 0 1 1 0

То есть получается поразрядная сортировка. Как же мне её реализовать?

4
  • Как обычно - начинаете с последнего разряда, сортируете, переходя постепенно справа налево... Только сортировка должна быть устойчивой! Если, конечно, не хотите просто перевести строки в числа и отсортировать их :) Или просто сортировать строки какой-нибудь стандартной сортировкой типа sort...
    – Harry
    14 апр 2018 в 17:39
  • @Harry, нет, сортировка с первого разряда, так как я заполнял строки с конца. 14 апр 2018 в 17:42
  • Ну что ж, наверное, вам виднее. Когда ничего не получится - пишите :)
    – Harry
    14 апр 2018 в 17:54
  • @Harry, уже час бьюсь.Не могу :) 14 апр 2018 в 17:56

3 ответа 3

3

Не помещается у меня ответ в комментарий.
Чтоб сортировать поразрядно, нужны 1) устойчивая сортировка и 2) сортировка, начиная с последнего разряда к первому.

Ваш исходный массив:

0 1 1 0 1 0 1
1 0 0 0 1 1 0
0 0 0 0 1 1 0
1 0 0 0 1 0 0
1 1 1 1 0 0 1
1 1 1 0 1 0 1

После сортировки по 7 разряду:

0 1 1 0 1 0 1
1 1 1 1 0 0 1
1 1 1 0 1 0 1
1 0 0 0 1 1 0
0 0 0 0 1 1 0
1 0 0 0 1 0 0

После сортировки по 6 разряду:

1 0 0 0 1 1 0
0 0 0 0 1 1 0
0 1 1 0 1 0 1
1 1 1 1 0 0 1
1 1 1 0 1 0 1
1 0 0 0 1 0 0

После сортировки по 5 разряду:

1 0 0 0 1 1 0
0 0 0 0 1 1 0
0 1 1 0 1 0 1
1 1 1 0 1 0 1
1 0 0 0 1 0 0
1 1 1 1 0 0 1

После сортировки по 4 разряду:

1 1 1 1 0 0 1
1 0 0 0 1 1 0
0 0 0 0 1 1 0
0 1 1 0 1 0 1
1 1 1 0 1 0 1
1 0 0 0 1 0 0

После сортировки по 3 разряду:

1 1 1 1 0 0 1
0 1 1 0 1 0 1
1 1 1 0 1 0 1
1 0 0 0 1 1 0
0 0 0 0 1 1 0
1 0 0 0 1 0 0

После сортировки по 2 разряду:

1 1 1 1 0 0 1
0 1 1 0 1 0 1
1 1 1 0 1 0 1
1 0 0 0 1 1 0
0 0 0 0 1 1 0
1 0 0 0 1 0 0

После сортировки по 1 разряду:

1 1 1 1 0 0 1
1 1 1 0 1 0 1
1 0 0 0 1 1 0
1 0 0 0 1 0 0
0 1 1 0 1 0 1
0 0 0 0 1 1 0

Похоже на то, что вам нужно?

Это - если вам преподаватель сказал помучиться. Если же нужно дело сделать - проще воспользоваться стандартной std::sort().

9
  • Да, именно это мне и нужно. 14 апр 2018 в 18:03
  • Значит, начинать нужно с последнего (самого правого) разряда...
    – Harry
    14 апр 2018 в 18:04
  • Помучиться надо ;) 14 апр 2018 в 18:04
  • Тогда главное - сохранить относительный порядок строк с одинаковыми числами в разряде сортировки. В каком хоть виде представлена матрица? Массив, вектор векторов, словом, какой вид она в программе имеет?
    – Harry
    14 апр 2018 в 18:06
  • Двумерный массив (int). 14 апр 2018 в 18:08
1

Возьмите QuickSort и примените его принципы к свой задаче. Для этого достаточно выполнять процедуру partition не относительно разделяющего элемента (pivot), а на каждом уровне рекурсии (L) обменивать строки с 1 или 0 в L-ом столбце.

Вот модифицированный псевдокод из вики для n строк и m столбцов.

 algorithm quicksort(A, lo, hi, level) is
    if lo < hi then
        p := partition(A, lo, hi, level)

        if level < m - 1
            quicksort(A, lo, p – 1, level + 1)
            quicksort(A, p, hi, level + 1)

 algorithm partition(A, lo, hi, level) is
    i := lo
    j := hi    
    while i <= j do
        while A[i][level] = 1 do
          i := i + 1 
        while A[j][level] = 0 do
          j := j - 1 
        if i <= j then
            swap A[i] with A[j]
            i := i + 1
            j := j - 1
    return i
5
  • Желательно показать это в коде. 14 апр 2018 в 18:01
  • Покажите. Посмотрим и поправим, если что.
    – MBo
    14 апр 2018 в 18:03
  • @ДаниилЧижевский ДАВАЙТЕ КАК ВЫ САМИ НАПИШИТЕ КОД 14 апр 2018 в 18:05
  • От минусов была бы польза, если бы минусаторы пояснили, что не так.
    – MBo
    15 апр 2018 в 1:49
  • @MBo, думаю кто то не понел что вы написали или хотели сказать 15 апр 2018 в 21:55
0

Трудно угадать, какие понятия доступны. Если можно использовать функторы, то поможет такой код:

class CmpBinary {
    const size_t n;
public:
    CmpBinary(const int column) : n(column){}
    bool operator()(bool* b1, bool* b2)
    {
        for (size_t i = 0; i < n; ++i) {
            if (b1[i] == b2[i]) continue;
            return (b1[i] > b2[i]) ? true : false;
        }
        return true;
    }
};

В программе создаете массив указателей на первый элемент строк вашего двумерного массива. Созданный массив сортируете по функтору (передавая ей количество столбцов) и получаете желаемый результат.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.