[자료구조] 퀵정렬

퀵정렬이란?

"빠른" 정렬 알고리즘. 피벗을 기준으로 큰 값과 작은값을 서로 비교하고 교체하는 정렬. 

 

1. 리스트 가운데서 피벗이라고 하는 하나의 원소를 고름
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 함. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않음
3. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복하며 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복됨

• 값을 서로 교체하는데 N번, (엇갈렸을때) 전체 원소 나누는데 평균 logN번이 소요되므로 평균적으로 O(NlogN)의 시간복잡도를 가짐
• 최악의 경우에는 O(N²)번의 비교를 수행함
• 퀵정렬은 완전 이진트리와 흡사하며 이것은 컴퓨터 공학에서 가장 선호하는 이상적인 형태임

 

이미지 출처 : Wikipedia

 

 

 

참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수