파이썬 퀵정렬(QuickSort) 구현 방법 완벽 가이드

파이썬 퀵정렬(QuickSort)은 피벗(pivot) 요소를 하나 선택하고, 배열의 요소들을 두 개의 새로운 배열로 분할하는 정렬 알고리즘입니다. 피벗보다 큰 숫자는 한쪽 배열로, 피벗보다 작은 숫자는 다른 쪽 배열로 이동합니다. 각 배열을 정렬한 후 모든 배열을 하나로 병합하여 최종 결과를 얻습니다.

파이썬 퀵정렬 구현하기

프로그래밍에서 리스트를 정렬할 때 사용할 수 있는 알고리즘은 매우 다양합니다. 삽입 정렬(insertion sort), 버블 정렬(bubble sort) 등 여러 종류가 있으며, 그중 퀵정렬(QuickSort)은 가장 널리 사용되는 정렬 알고리즘 중 하나입니다.

이 글에서는 퀵정렬이 무엇인지, 어떻게 동작하는지 살펴보고, 실제 예제를 통해 파이썬으로 퀵정렬을 구현하는 방법까지 단계별로 알아보겠습니다.

파이썬 퀵정렬이란?

파이썬 퀵정렬 알고리즘은 하나의 배열을 여러 개의 하위 배열(sub array)로 나눕니다. 그런 다음 각 하위 배열에 대해 재귀적으로 자기 자신을 호출하여 리스트의 모든 요소를 정렬합니다. 하위 배열의 내용은 새로운 하위 배열로 이동하지 않는 피벗 요소를 기준으로 결정됩니다.

퀵정렬은 '분할 정복(divide-and-conquer)' 방식을 사용합니다. 즉, 리스트를 정렬하는 하나의 큰 작업을 여러 개의 작은 하위 작업으로 나누어 처리하고, 정렬이 끝나면 이 하위 작업들의 결과가 합쳐져 정렬된 리스트를 반환합니다.

퀵정렬에서 하위 작업이란 각 하위 리스트마다 피벗을 설정하고, 피벗을 기준으로 요소들의 상대적인 값을 비교해 배치하는 것입니다.

퀵정렬은 언제 사용해야 할까?

퀵정렬은 시간 복잡도가 중요한 상황에서 유용합니다. 다른 알고리즘보다 적은 메모리 공간을 사용하기 때문에 효율성 면에서 유리하기 때문입니다.

다만 퀵정렬은 재귀 함수에 의존하므로, 파이썬의 재귀(recursion) 개념에 익숙할 때 사용하는 것이 좋습니다.

또한 퀵정렬은 작은 배열에서는 병합 정렬(merge sort)보다 효율적입니다. 하지만 데이터 세트가 커지면 삽입 정렬이나 병합 정렬이 더 빠를 수 있습니다.

퀵정렬은 어떻게 동작할까?

퀵정렬은 먼저 피벗 역할을 할 요소를 하나 선택합니다. 피벗은 리스트의 어떤 요소든 될 수 있으며, 이 튜토리얼에서는 리스트의 마지막 항목인 3을 피벗으로 선택하겠습니다.

리스트의 항목들을 순회하면서 피벗 값과 모든 숫자를 비교합니다. 항목이 피벗보다 크면 피벗 뒤로 이동시키고, 그렇지 않으면 피벗 앞으로 이동시킵니다.

값 3이 리스트에서 아래쪽으로 이동했습니다. 3보다 작은 항목들은 모두 왼쪽으로, 3보다 큰 값들은 모두 오른쪽으로 이동했습니다.

이제 파이썬 배열은 두 부분으로 나뉩니다. 피벗보다 큰 항목들과 피벗보다 작은 항목들입니다.

이 과정이 시작되면 두 부분 각각에서 새로운 피벗이 지정됩니다. 각 피벗은 독립적으로 시작되며 위와 동일한 알고리즘을 사용합니다. 먼저 각 리스트의 마지막 값을 피벗 값으로 설정합니다.

다음으로 피벗보다 큰 값들은 모두 피벗의 오른쪽으로, 피벗보다 작은 값들은 모두 왼쪽으로 이동시킵니다.

이 과정을 반복하면 리스트 전체가 정렬됩니다.

최종적으로 정렬된 배열은 다음과 같습니다.

파이썬 퀵정렬 예제 코드

퀵정렬을 구현하려면 두 가지 함수가 필요합니다. 바로 피벗(분할) 함수와 퀵정렬 함수입니다.

먼저 분할(partition) 함수부터 만들어 보겠습니다. 이 함수는 피벗 요소의 값을 기준으로 배열을 분할하거나 준비하는 역할을 합니다.

분할 함수는 다음 작업을 수행합니다.

1. 피벗 요소를 선택한다
2. 피벗보다 큰 항목들을 모두 피벗의 오른쪽으로 이동시킨다
3. 피벗보다 작은 항목들을 모두 피벗의 왼쪽으로 이동시킨다

퀵정렬 파이썬 프로그램

이제 이 알고리즘을 구현하는 프로그램을 작성해 보겠습니다.

def prepare(numbers, low, high):
	pivot = numbers[high]
	item = low - 1

	for i in range(low, high):
		if numbers[i] <= pivot:
			item = item + 1
			(numbers[item], numbers[i]) = (numbers[i], numbers[item])

	(numbers[item + 1], numbers[high]) = (numbers[high], numbers[item + 1])

	return item + 1

먼저 피벗 요소를 선택합니다. 피벗은 리스트에서 가장 마지막에 있는 숫자와 같습니다.

다음으로 파이썬 for 루프를 사용해 리스트의 모든 항목을 순회합니다. 숫자가 피벗보다 작거나 같으면 피벗의 왼쪽으로 이동하고, 그렇지 않으면 피벗의 오른쪽으로 이동합니다.

이 파이썬 함수는 새로운 high 값을 반환합니다. 새로운 high 값은 item + 1과 같습니다.

이제 실제로 알고리즘을 실행해야 합니다. 별도의 함수를 작성해서 실행할 수 있습니다.

def quick_sort(numbers, low, high):
	if low < high:
		pivot = prepare(numbers, low, high)

		quick_sort(numbers, low, pivot - 1)

		quick_sort(numbers, pivot + 1, high)

이 함수는 'low' 값이 'high' 값보다 작은지 확인합니다. 조건이 참이면 정렬을 계속 진행하고, 그렇지 않으면 정렬을 종료합니다. 정렬이 종료된다는 것은 리스트가 이미 정렬되었다는 의미입니다.

다음으로 함수는 prepare() 메서드를 호출합니다. 이 메서드는 피벗 포인터를 식별하고 항목들을 올바른 위치로 이동시킵니다.

그런 다음 함수는 quick_sort() 메서드를 두 번 호출합니다. 첫 번째 호출에서는 피벗 왼쪽의 요소들에 대해 퀵정렬을 실행하고, 두 번째 호출에서는 피벗 오른쪽의 요소들에 대해 퀵정렬을 실행합니다. 따라서 이 함수는 자기 자신을 호출하는 재귀 함수입니다.

이 과정은 리스트의 모든 항목이 정렬될 때까지 계속됩니다.

메인 메서드 작성하기

이제 정렬할 리스트를 정의하는 메인 프로그램을 작성해 보겠습니다.

values = [8, 4, 5, 2, 1, 3]
total_values = len(values)

quick_sort(values, 0, total_values - 1)

print(values)

먼저 정렬할 값들의 리스트를 지정합니다. 파이썬 len() 메서드를 사용해 값 리스트의 길이를 계산한 후, quick_sort() 메서드를 호출합니다.

'values'를 정렬하려는 숫자로 전달하고, low 값으로 0을 전달합니다. high 값으로는 'values'의 길이에서 1을 뺀 값을 지정합니다. 리스트의 첫 번째 항목 인덱스가 0이기 때문에 high 값은 길이에서 1을 뺀 값이 됩니다.

프로그램을 실행해 보겠습니다.

[1, 2, 3, 4, 5, 8]

코드가 정렬된 리스트를 반환했습니다! 성공입니다. 퀵정렬은 이해하고 구현하기 쉽지 않은 알고리즘이니 스스로를 칭찬해 주세요.

시간 복잡도 개요

평균적으로 이 알고리즘은 O(n log n)의 성능을 보입니다. 이는 피벗 요소가 최댓값이나 최솟값이 아니고, 중간 요소 근처에 있지 않을 때 발생합니다.

퀵정렬의 최악의 경우 시간 복잡도는 O(n²)입니다. 이는 피벗으로 선택된 요소가 최댓값 또는 최솟값일 때 발생합니다. 이 경우 피벗 요소는 항상 정렬된 배열의 끝에 위치하게 되어 불필요한 하위 배열이 많이 생성됩니다.

이 알고리즘의 최선의 경우 시간 복잡도는 O(n log n)입니다. 피벗 요소가 중간 요소와 같거나 중간 요소 근처에 있을 때 발생합니다.

알고리즘 복잡도에 대해 더 자세히 알아보려면 빅오 표기법(Big O Notation) 관련 가이드를 참고하세요.

마무리

파이썬 퀵정렬은 재귀를 활용해 리스트를 더 작은 리스트로 나눈 후 각각을 정렬합니다. 각 리스트는 피벗 요소를 기준으로 정렬되며, 피벗보다 큰 요소는 오른쪽으로, 작은 요소는 왼쪽으로 이동합니다.

추천 파이썬 학습 자료, 온라인 강의, 도서 등에 대한 안내가 필요하다면 종합적인 '파이썬 학습 방법' 가이드를 확인해 보세요.