Pythonで行・列ごとに並べられた行列の全要素をソート順に出力する方法

行列（マトリックス）のすべての要素をソートされた順序で取得したいケースはよくあります。しかし、行列は行と列という2次元の形式で構成されているため、通常のソートアルゴリズムをそのまま適用することはできません。そこで、以下のようにユーザー定義関数を作成し、それを使って要素を並べ替えます。

ここで紹介するのはヒープソートを利用した手法です。まずheapq関数で配列をヒープ構造に変換（ヒープ化）し、続くSort関数で実際のソート処理を実行します。

コード例

def heapq(a, k, i):
    greater = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < k and a[i] < a[l]:
        greater = l
    if r < k and a[greater] < a[r]:
        greater = r
    if greater != i:
        a[i], a[greater] = a[greater], a[i]
        heapq(a, k, greater)

def Sort(val):
    n = len(val)
    for i in range(n, -1, -1):
        heapq(val, n, i)
    for i in range(n - 1, 0, -1):
        val[i], val[0] = val[0], val[i]
        heapq(val, i, 0)

x = [11, 3, 50, 75, 4, 32, 9, 2, 15]
Sort(x)
n = len(x)
print("Sorted values are")
for i in range(n):
    print("%d" % x[i])

上記のコードを実行すると、次のような結果が出力されます。

実行結果

Sorted values are
2
3
4
9
11
15
32
50
75

このように、行と列に分かれたデータであっても、一度フラットなリストとして扱えば、ヒープソートなどのアルゴリズムを適用することで、すべての要素を昇順に並べ替えることができます。heapq関数は親ノードと子ノードを比較しながら部分木をヒープ化する役割を担い、Sort関数は先頭要素（最大値）を末尾と交換しながらヒープを再構築することで、全体を昇順に整列させます。