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

Question

[Dmitriy_Gultiaev]

Доброго времени суток, возник вопрос как сделать сортировку двухмерного массива по столбцам (пример ниже). Обязательное условие: не использовать дополнительные массивы и файлы.

Заранее спасибо за помощь!

Answer 1

[Wataru]

Работайте с массивом как с одномерным. Занумеруйте его так: первые индексы - это первый столбец сверху вниз. Потом идут индексы с ячейками второго столбца и т.д.

Вам осталось по одному числу - индексу в этом виртуальном одномерном массиве получать индексы исходного двумерного массива.

Номер столбца будет i / M, Где M - количество строк. Номер строки будет i % M.

Вам надо только написать алгоритм сортировки одномерного массива и везде, где там идет обращение к [i], вам надо сделать [i % M][i / M].

Comments

[Dmitriy_Gultiaev]

К сожалению, это тоже запрещено. Вот полная формулировка задания( Выполнить сортировку, совершая обход непосредственно по элементах заданного двумерного массива, не используя дополнительных массивов и преобразований индексов)

[Wataru]

Dmitriy_Gultiaev, Бред какой-то. Ну тогда вместо явного преобразования индексов расписывайте руками.

Допустим, сортировка выбором: пишите два цикла (сначала по строке, потом по столбцу), которые перебирают текущую заполняемую позицию. Затем сначала ищите минимум в текущем столбце, потом во всех остальных столбцах справа. Потом этот минимум меняете местами с текущим элементом.

Т.е. вместо двух циклов по i, которое раскалывается на i%M и i/M вы пишите 2 цикла по k и j так, чтобы они проходили те же числа в той же полседовательности.

Пузырек делается также. Два цикла в нужном порядке обходят весь массив. Меняете текущий элемент с элеменом ниже, если они не в том порядке. Если же текущий элемент - самый нижний, то сравнивайте и меняйте с первым элементом в следующей строке. Можно вместо if-ов гнать цикл до M-1 а не до M и отдельно обрабатывать этот самый самый нижний элемент в столбце.

Фактически, алгоритм будет делать тоже самое, что и с преобразованием индексов, но формально там будут 2 прямо использоваемых индекса.

[Dmitriy_Gultiaev]

Wataru, А не могли бы, пожалуйста, привести пример кода, допустим для пузырька

[Дмитрий]

а порядок не побьется при i%M?

[Wataru]

Dmitriy_Gultiaev, как-то так:

for(j=0; j < cols; ++j) {
  for(i=0; i < rows-1; ++i) {
    if (a[i][j] > a[i+1][j]) {
      std::swap(a[i][j], a[i+1][j]));
    }
  }
  if (j < cols-1 && a[rows-1][j] > a[0][j+1]) {
    std::swap(a[rows-1][j], a[0][j+1]);
  }
}

Это внутренний цикл, его надо сколько-то раз повторить. Можно хоть NM раз - будет не совсем оптимально. Можно циклом задом-наперед также отсчитывать индесксы конца и в этом цикле break-аться если дошли до конца.

[Wataru]

Дмитрий, А с чего бы ему биться? Строки проходят от 0 до M-1, потом опять от 0 до M-1, но уже в следующем столбце. Как раз как i%M себя вдет.