Python. Как отсортировать двухмерный список?

Question

[Роман Томченко]

Требуется отсортировать двухмерный список чисел размером __COLS x __ROWS по возрастанию всех элементов не разворачивая его в одномерный. Вариант с разворачиванием сделан и работает.
Функция для этой цели адекватно работает в C++ и в Java, но в Питоне, где нумерация тоже с 0 выдает ошибку индекса.

def swap_sort(a):
    for k in range(__ROWS * __COLS - 1):
        for i in range(__ROWS):
            for j in range(__COLS):
                if i >= __ROWS - 1 and j >= __COLS - 1:
                    continue
                if a[i][j] > a[i][j + 1]:
                    a[i][j], a[i][j + 1] = a[i][j + 1], a[i][j]

Что я делаю не так?
Заранее спасибо.

Answer 1

[Vindicar]

Если j == __COLS - 1, но i < __ROWS - 1, то ты попытаешься обратиться к элементу a[i][__COLS - 1 + 1], т.е. a[i][__COLS]. Я полагаю, в этом и дело.
Не знаю насчёт Java, но в C++ вполне возможно, что у тебя строки матрицы лежат в памяти подряд, так что ты фактически нечаянно обращаешься к a[i+1][0], тем самым корректно "склеивая" строки.

Comments

[Роман Томченко]

Хм... То есть в Питоне из-за структуры списка не склеивая его в одномерный сортировать невозможно?
Просто именно задача стоит таким образом - не должно быть явного разворачивания списка в одномерный.

[Vindicar]

Роман Томченко, ну почему же невозможно.
У тебя ведь вся задача - для заданной пары индексов i,j получить индексы следующего элемента k,l, а потом уже делать сравнение и обмен.
А k,l рассчитываются тривиально, догадаешься как?

[Роман Томченко]

Vindicar,
То ли я тупой, то ли не совсем тривиально.
Если логически подумать, при достижении конца строки индекс столбца должен меняться на 0, а индекс строки - на (i + 1) - то бишь на следующую...
При этом, если эта строка - последняя, то переходим к следующей итерации...

def swap_sort(a):
    for k in range(__ROWS * __COLS - 1):
        for i in range(__ROWS):
            for j in range(__COLS):
                m, n = i, (j + 1)
                if n == __COLS:
                    n = j
                    m = i + 1
                if m == __ROWS:
                    continue
                if a[i][j] > a[m][n]:
                    a[i][j], a[m][n] = a[m][n], a[i][j]

Однако на выходе получаем набор отсортированных внутри себя строк.
Может я чего-то в основе не понял?

[Vindicar]

Роман Томченко, Просто есть три варианта, на самом деле.

if j < __COLS - 1: # не конец строки
    m, n = i, j + 1
elif i < __ROWS - 1: # конец строки, но не последней
    m, n = i + 1, 0
else: # конец последней строки - сравниваем элемент с самим собой, это ничего не изменит
    m, n = i, j

[Роман Томченко]

Vindicar, О... теперь понял... я вместо последнего условия пропуск шага пытался делать... выходило странно.
Спасибо. все заработало )

[Vindicar]

Роман Томченко,

if n == __COLS:
    n = j
    m = i + 1

n = 0, а не j. А пропуск можно делать, почему нет...

Answer 2

[PavelMos]

if i >= __ROWS - 1 and j >= __COLS - 1:
                    continue

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

Comments

[Роман Томченко]

В теории она должна при совпадении перескакивать на следующий шаг, пропуская все в текущем...

[PavelMos]

Роман Томченко, сорри, ошибся, перепутал с выходом из цикла.