1. 퀵 정렬 (Quick Sort)
ㅇ 가장 빠른 정렬 알고리즘 중의 하나로 널리 사용됨
- 1962년 영국의 컴퓨터 과학자 찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)가 발표
ㅇ 피벗 선정 및 분할 방식에 따라 여러가지의 변형과 개선 버전 있음
2. 퀵 정렬의 작동방식
ㅇ 대소 그룹으로 나누는 분할을 반복해가며 정렬
- 작은 값들을 왼쪽, 큰 값들을 오른쪽으로, 2개의 대소 그룹으로 나누고,
- 각 그룹 내 다시 동일 동작을 반복하면, 전체가 작은 값부터 큰값으로 정렬됨
ㅇ 구체적으로, 수열 내에서,
- 피봇(기준 원소)을 무작위로 1개 선택한 후,
. 피봇 선택 방식 : 맨앞, 가운데값, 무작위, 무작위 3개 중 중앙값 등
- 피봇 이외의 값들을,
. `피봇 보다 큰 값`, `피봇 보다 작거나 같은 값`의 2 그룹으로 나누며, 이동시킴
- 피봇 위치는 그대로 두고, 각 수를 피봇과 비교하면서 좌우로 교환 이동 시킴
. 왼쪽 처음 나오는 큰 값과 오른쪽 처음 나오는 작은 값 간에 교환시킴
. 교환 위치 이후부터 연이어 왼쪽,오른쪽으로 조사하며, 교환 이동시킴
. 조사 위치를 관리하기 위한 인수 둘(2) : 시작 위치, 종료 위치
.. 조사 종료는, 시작 위치와 종료 위치가 만날 때까지임
.. 피벗은, 통상 시작 위치와 종료 위치 한가운데 값을 취함
- 각 그룹별로 하나 만 남을 때까지, 재귀적으로 부분 이동 정렬하면,
. 분할한 그룹별로 재귀 함수 호출에 의해 같은 방법으로 수행
- 전체 정렬이 됨
3. 퀵 정렬의 특징
ㅇ 분할 정복 알고리즘
ㅇ 재귀 호출 활용
- 통상, 재귀 함수를 사용하여 수행하되, 함수 밖 배열을 정렬하게 됨
ㅇ 교환 횟수를 줄이기 위해, 교환할 필요가 있는 것끼리 만 교환함
ㅇ 주요 연산 : 비교(compare), 교환(swap)
ㅇ 계산 효율성 : O(n log(n))
- 피벗을 어떻게 선택하는가에 따라, 성능 차이가 큼
ㅇ (추가편집중)
3. 알고리즘 구현 例)
ㅇ 파이썬 코드
def quicksort(data) :
# 종료 조건
if len(data) <= 1 :
return data
# 피벗 선택
pivot = data[(len(data)-1)//2]
# 좌우 배열을 리스트 자료구조를 사용하여 생성
left = []
right = []
# 피벗 비교 후 교환을 현재 배열 갯수 만큼 반복
for i in range(0,len(data)) :
# 피벗 보다 작으면
if data[i] < pivot :
# left(왼쪽그룹)에 추가
left.append(data[i])
# 피벗 보다 크면
elif data[i] > pivot :
# right(오른쪽그룹)에 추가
right.append(data[i])
# 분할된 결과 배열을 같은 방법으로 정렬 (재귀)
left = quicksort(left)
right = quicksort(right)
# 최종 결과 리턴
return left + [pivot] + right
- 위 코드는, 함수 밖 배열을 사용하는 대신에,
. 새로운 배열을 만들어서 그 결과로써 돌려주는 형태임
ㅇ (추가편집중)