Не понимаю в чем ошибка в моем алгоритме сортировки матрицы

Question

Необходимо отсортировать матрицу из двумерного массива так, чтобы сначала шли числа отрицательные, при этом сохраняя порядок их следования, но у меня получается так, что они немного по другому заполняются, я не понимаю почему

int metka = 0;
for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        metka = 0;
        if (A[i][j] >= 0) {
            for (int k = i; k < N; k++) {
                if (metka == 1) {
                    break;
                }
                for (int l = j; l < M; l++) {
                    if (A[k][l] < 0) {
                        swap(A[i][j], A[k][l]);
                        metka = 1;
                        break;
                    }
                }
            }
        }
    }
}

Необходимо чтобы они по порядку стояли, а получается что они стоят по какой-то диагонали

Answer 1

По поводу вашего решения, на всех кроме первой итерациях цикла по l нужно начинать с нуля, а не с j.

Что-то как-то сложно у вас получилось. Мне алгоритм представляется простым:

// линеаризуем пространство матрицы, чтобы убрать лишние циклы
for (int index1 = 0; index1 < N*M; ++index1) {
    int i = index1 / M;
    int j = index1 % M;
    if (A[i][j] >= 0) { // Нашли неотрицательное
        for (int index2 = index1 + 1; index2 < N*M; ++index2) {
            int k = index2 / M;
            int l = index2 % M;
            if (A[k][l] < 0) { // Заменяем на первое попавшееся отрицательное
                swap(A[i][j], A[k][l]);
                break;
            }
        }
        // тут можно проверить, что отрицательное мы не нашли и выйти
    }
}

Можно ещё оптимизировать алгоритм, чтобы во внутреннем цикле не проходить уже просмотренные положительные значения.

Несмотря на то, что тут 2 цикла, по факту - это O(N):

auto len = N*M;
for (auto index1 = 0, index2 = 1; index1 < len && index2 < len; ++index1, ++index2) {
    auto i = index1 / M;
    auto j = index1 % M;
    if (A[i][j] >= 0) {
        for (; index2 < N*M; ++index2) {
            auto k = index2 / M;
            auto l = index2 % M;
            if (A[k][l] < 0) {
                swap(A[i][j], A[k][l]);
                break;
            }
        }
    }
}

cpp.sh

БЛОГ НА HUSL

Не понимаю в чем ошибка в моем алгоритме сортировки матрицы

Ответы (1 шт):