파이썬으로 퀵 정렬 알고리즘 구현하기 포스트에서 간단하기 퀵 정렬 알고리즘을 구현하여 보았습니다.
이번에는 같은 알고리즘으로 2차원 배열을 정렬하는 상황을 가정해 봅시다.
unsorted = [[5, 7, 3], [3, 4, 5], [4, 2, 6], [2, 6, 4]]
for xx in unsorted:
print("%s" % xx)
print()
for xx in quicksort(unsorted):
print("%s" % xx)
이렇게 2차원 배열을 퀵 정렬 알고리즘으로 정렬해 본다면,
[5, 7, 3] [3, 4, 5] [4, 2, 6] [2, 6, 4] [2, 6, 4] [3, 4, 5] [4, 2, 6] [5, 7, 3]
이렇게 정렬이 됩니다. 앞의 것은 정렬되지 않은 데이터, 뒤의 것은 정렬된 데이터. 보다시피 2차원 배열의 제1열을 기준으로 정렬이 되어 있습니다.
이 배열을 제2열을 기준으로 정렬을 하고 싶습니다. 하지만, 이 방법으로는 제1열로밖에 정렬할 수 없습니다. 그러면 어떻게 하면 정렬이 가능해질까요?
다음과 같이 2차원 배열의 기준을 지정하여 정렬하는 알고리즘을 만들면 됩니다.
def array_quicksort(arr, nx = 0, desc = False): if len(arr) <= 1: return arr # only 2 or more i = len(arr) // 2 pivot = arr[i] less = []; equal = []; greater = [] # L/E/G array for x in arr: if x[nx] < pivot[nx]: less.append(x) # Less than pivot elif x[nx] == pivot[nx]: equal.append(x) # Equal to pivot elif x[nx] > pivot[nx]: greater.append(x) # Greater than pivot if desc: return array_quicksort(greater, nx, True) + equal + array_quicksort(less, nx, True) else: return array_quicksort(less, nx, False) + equal + array_quicksort(greater, nx, False)
이전 포스트에 구현하였던 것과 기본적인 구조는 같습니다. 다만, 몇 번째 열을 기준으로 정렬할 것인지를 지정할 수 있습니다. 만약 첫 번째 열을 기준으로 할 경우 nx에 해당하는 값을 0으로 하는 식입니다. 이는 배열끼리 정렬할 때 기준을 배열 자체로 놓을 경우 앞의 열 값부터 크고 작은가를 비교하기 때문입니다. 이런 경우 단점은 배열 기준이 첫 열이 아닐 경우 정렬에 어려움을 겪게 됩니다.
그래서 기준을 배열 자체가 아닌 그 배열의 특정 열을 기준으로 크고 작은가를 비교하는 과정이 필요합니다. 이를 위해서 배열을 통째로 추출하는 것이 아니라, 배열에서 특정 열의 값도 함께 추출하여 정렬 기준으로 삼는 것입니다.
여기서는 두 번째 열을 기준으로 정렬하므로 nx의 값을 1로 놓습니다. 이렇게 알고리즘을 정의하고 다시 실험해 봅시다.
unsorted = [[5, 7, 3], [3, 4, 5], [4, 2, 6], [2, 6, 4]]
for xx in unsorted:
print("%s" % xx)
print()
for xx in array_quicksort(unsorted, 1):
print("%s" % xx)
실행해 보면,
[5, 7, 3] [3, 4, 5] [4, 2, 6] [2, 6, 4] [4, 2, 6] [3, 4, 5] [2, 6, 4] [5, 7, 3]
이와 같이 제2열의 값을 기준으로 정렬이 되었음을 알 수 있습니다.
또한, 이 방식은 2차원 배열이 딕셔너리 형식으로 되어 있는 경우에도 적용이 가능합니다. 예를 들어, 다음의 경우를 봅시다.
products = [{"name": "새우깡", "price": 1000},
{"name": "도리토스", "price": 1400},
{"name": "콘칩", "price": 1300},
{"name": "꼬깔콘", "price": 1200},
{"name": "허니버터칩", "price": 1500},
{"name": "양파링", "price": 1100},
{"name": "포스틱", "price": 1150},
{"name": "꽃게랑", "price": 1250},
{"name": "포카칩", "price": 1350}]
for xx in array_quicksort(products, "price"):
print("%s: %d원" % (xx["name"], xx["price"]) )
print()
이 코드를 실행해 보면,
새우깡: 1000원 양파링: 1100원 포스틱: 1150원 꼬깔콘: 1200원 꽃게랑: 1250원 콘칩: 1300원 포카칩: 1350원 도리토스: 1400원 허니버터칩: 1500원
이와 같이 키값을 기준으로 정렬이 됨을 알 수 있습니다.