행렬(matrix)을 다루다 보면 행과 열에 흩어져 있는 모든 요소를 하나의 정렬된 순서로 확인해야 하는 경우가 있습니다. 하지만 행렬은 행과 열의 구조로 되어 있기 때문에 일반적인 정렬 알고리즘을 그대로 적용하기는 어렵습니다. 이럴 때는 아래와 같이 직접 정의한 함수를 활용하면 행렬의 요소들을 간단하게 정렬할 수 있습니다.
힙 정렬(Heap Sort) 기반 정렬 함수
다음 예제는 힙 정렬의 원리를 이용해 주어진 값들을 오름차순으로 정렬하는 사용자 정의 함수입니다. heapq 함수는 최대 힙(max heap)을 유지하는 역할을 하고, 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])코드 동작 방식
- heapq 함수: 특정 인덱스를 루트로 하는 서브트리에서 부모 노드가 자식 노드보다 작으면 값을 교환하고, 재귀 호출을 통해 힙 속성을 유지합니다.
- Sort 함수: 먼저 전체 배열을 최대 힙으로 만든 후, 루트(최댓값)를 배열 끝으로 옮기고 힙 크기를 줄여가며 반복 정렬합니다.
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
실행 결과
Sorted values are 2 3 4 9 11 15 32 50 75
2차원 행렬에 적용하기
실제 2차원 행렬의 모든 요소를 정렬하려면 먼저 행렬을 1차원 리스트로 펼친(flatten) 후 위의 Sort 함수를 적용하면 됩니다.
matrix = [[12, 7, 3], [4, 5, 18], [2, 9, 11]] flat = [v for row in matrix for v in row] Sort(flat) print(flat)
이 코드는 행렬의 모든 요소를 [2, 3, 4, 5, 7, 9, 11, 12, 18]처럼 오름차순으로 정렬해 줍니다. 힙 정렬의 시간 복잡도는 O(n log n)으로, 요소 개수가 많은 행렬에서도 안정적인 성능을 기대할 수 있습니다. 참고로 간단한 처리에는 파이썬 내장 함수인 sorted()나 itertools.chain을 활용하는 방법도 있지만, 정렬 과정을 직접 제어하고 싶다면 위와 같은 사용자 정의 함수가 유용합니다.