Сортировка строк двумерного массива

180
17 апреля 2018, 04:25

Вечер добрый! Есть двумерный массив, в котором содержится 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

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

Answer 1

Не помещается у меня ответ в комментарий.
Чтоб сортировать поразрядно, нужны 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().

Answer 2

Возьмите 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
Answer 3

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

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

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

READ ALSO
Как закрыть процесс не затрагивая его дочерние процессы?

Как закрыть процесс не затрагивая его дочерние процессы?

Вопрос в шапке (C++, Visual Studio 17, Console Application) Сейчас понаедут знатоки которое напишут 2-3 слова "в кратце" но мне нужно ПОДРОБНОСпасибо

190
Сортировка массива структуры

Сортировка массива структуры

У меня есть структура

204
Подробный принцип работы hide VNC (hVNC)

Подробный принцип работы hide VNC (hVNC)

Кто нибудь знает как работает hVNC? Интересует именно создание параллельной сессии на пк которым нужно управлятьОчень удобно было бы работать...

259