퀵 정렬(Quick Sort)
전개
- pivot(중심점)과 left 리스트, right 리스트를 활용하여 퀵 정렬을 구현할 수 있다.
- pivot을 설정한다.
- 여기에서는 마지막 인덱스에 해당하는 원소를 pivot으로 설정하였다.
- pivot보다 작은 데이터는 left 리스트에 담고, 큰 데이터는 right 리스트에 담는다.
- left 리스트와 right 리스트 각각을 재귀적으로 정렬한 후, left 리스트, pivot, right 리스트 순으로 이어붙인다.
- 주의할 점: 재귀함수를 사용하므로 기저 조건이 필요하다.
- 기저 조건: 리스트의 길이가 1일 때 리스트를 반환한다.
시간 복잡도
- 평균적으로는 O(NlogN)
- 최악의 경우 O(N2)
- 이유는 추후에 서술할 예정이다.
구현 코드
방법 1: 정렬 후 새 리스트 리턴
def quick_sorted(numbers):
"""오름차순 퀵 정렬을 실행합니다."""
if len(numbers) <= 1:
return numbers
pivot = numbers[-1]
left = [n for n in numbers[1:] if n < pivot]
right = [n for n in numbers[1:] if n >= pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
if __name__ == '__main__':
numbers = [6, 5, 6, 4, 3, 2, 1]
sorted_numbers = quick_sort(numbers)
print(sorted_numbers)
방법 2: 정렬 후 리턴 값 없음
def quick_sort_sub(numbers, start, end):
""" 오름차순 퀵 정렬을 실행합니다. """
if end - start <= 0:
return
pivot = numbers[end]
i = start
for j in range(start, end):
if numbers[j] <= pivot:
numbers[i], numbers[j] = numbers[j], numbers[i]
i += 1
numbers[i], numbers[end] = numbers[end], numbers[i]
quick_sort_sub(numbers, start, i - 1)
quick_sort_sub(numbers, i + 1, end)
def quick_sort(numbers):
""" 오름차순 퀵 정렬을 호출합니다. """
quick_sort_sub(numbers, 0, len(numbers) - 1)
if __name__ == '__main__':
numbers = [6, 5, 6, 4, 3, 2, 1]
quick_sort(numbers)
print(numbers)
'''
출력 결과
[1, 2, 3, 4, 5, 6, 6]
'''
Ref