Вечер добрый! Есть двумерный массив, в котором содержится 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
То есть получается поразрядная сортировка. Как же мне её реализовать?
Не помещается у меня ответ в комментарий.
Чтоб сортировать поразрядно, нужны 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()
.
Возьмите 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
Трудно угодать какие понятия доступны. Если можно использовать функторы, то поможет такой:
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;
}
};
В программе создаете массив указателей на первый элемент строк вашего двумерного массива. Созданный массив сортируете по функтору (передавая ей количество столбцов) и получаете желаемый результат.
Частный дом престарелых в Киеве: комфорт, забота и профессиональный уход
Вопрос в шапке (C++, Visual Studio 17, Console Application) Сейчас понаедут знатоки которое напишут 2-3 слова "в кратце" но мне нужно ПОДРОБНОСпасибо
Кто нибудь знает как работает hVNC? Интересует именно создание параллельной сессии на пк которым нужно управлятьОчень удобно было бы работать...