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

이 포스트에서는 파이썬에서 퀵 정렬 알고리즘을 구현한 포스트입니다.

여기서는 퀵 정렬 알고리즘을 병합 정렬 알고리즘 기반으로 구현하였습니다. 코드를 봅시다.

def quicksort(arr, desc = False):
	if len(arr) <= 1: return arr  # only 2 or more
	try:                          # numeric array
		pivot = (max(arr) + min(arr)) / 2
	except TypeError:             # non-numeric array
		i = len(arr) // 2
		pivot = arr[i]            # Below: L/E/G array
	less = []; equal = []; greater = []
	for x in arr:
		if x < pivot:     less.append(x)     # Less than pivot
		elif x == pivot:  equal.append(x)    # Equal to pivot
		elif x > pivot:   greater.append(x)  # Greater than pivot
	if desc:  return quicksort(greater, True) + equal + quicksort(less, True)
	else:     return quicksort(less, False) + equal + quicksort(greater, False)

이 코드는 퀵 정렬 함수를 정의하는 코드입니다.

2번 줄에서 우선 배열 크기를 검사해서 1 이하일 경우 그냥 그 값을 그대로 돌려주는 코드를 넣습니다. 배열이 쪼개지면서 재귀를 거듭하다 보면 종국에는 원소가 하나이거나 빈 배열로 쪼개지면서 정렬되기 때문에 이 단계까지 가면 정렬이 다 된 것으로 보고 정렬 알고리즘을 끝내기 위함입니다.

4번 줄은 기준값을 정하기 위한 코드입니다. 최댓값과 최솟값의 중간값을 기준값으로 하게 되어 있지만 만약 수치 배열이 아닐 경우는 예외처리가 발동하면서 6번 줄로 넘어가 배열의 중간 위치에 있는 값을 기준값으로 정합니다.

8번 줄은 기준값보다 작은 값, 같은 값, 큰 값을 분류하기 위한 배열을 선언합니다. 그리고 9번 줄부터 12번 줄까지가 반복문입니다. 10번 줄부터 12번 줄까지는 각 배열의 값을 기준값과 비교하여 알맞는 배열에 넣습니다.

모든 값의 비교가 끝나면 13번 줄에서 배열을 정렬한 상태로 돌려줍니다. 만약 내림차순 옵션이 True일 경우 기준값보다 큰 값들의 배열을 먼저 놓고 그 다음은 기준값과 같은 값들의 배열을 놓은 다음 마지막으로 기준값보다 작은 값들의 배열을 놓습니다. 물론 내림차순 옵션이 False일 경우(생략 포함) 반대로 작은 값부터 먼저 배열을 결합합니다. 두 옵션 모두 작은 값과 큰 값의 배열에 대해서는 quicksort 함수를 재귀호출하면서 계속 정렬해 나갑니다.

이제 이 함수를 실험해 봅시다.

unsorted = [4, 6, 1, 8, 7, 5, 2, 3]
print("  Unsorted: %s" % unsorted)
print(" Ascending: %s" % quicksort(unsorted) )
print("Descending: %s" % quicksort(unsorted, True) )

정렬되지 않은 배열을 세팅한 다음 정렬 함수를 오름차순과 내림차순으로 실행해 보면,

  Unsorted: [4, 6, 1, 8, 7, 5, 2, 3]
 Ascending: [1, 2, 3, 4, 5, 6, 7, 8]
Descending: [8, 7, 6, 5, 4, 3, 2, 1]

정렬된 배열이 출력됩니다.

이와 같이 파이썬에서 퀵 정렬 알고리즘을 구현해 볼 수 있습니다.