제목:

파이썬으로 퀵 정렬 알고리즘 구현하기 2

날짜: Posted on

파이썬으로 퀵 정렬 알고리즘 구현하기 포스트에서 간단하기 퀵 정렬 알고리즘을 구현하여 보았습니다.

이번에는 같은 알고리즘으로 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원

이와 같이 키값을 기준으로 정렬이 됨을 알 수 있습니다.

답글 남기기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다