퀵정렬1 [정렬] 퀵정렬 (Quick Sort) 앞에서 살펴본 선택 정렬, 삽입 정렬, 버블 정렬은 모두 구현은 간단하지만 느린 정렬 알고리즘이었다. 이번 글에서 살펴볼 퀵 정렬은 가장 많이 쓰이는 정렬 알고리즘이며 분할과 정복을 기반으로 하는 알고리즘이다. 평균적인 시간 복잡도는 O(NlogN)이다. 기본 아이디어 우선 배열 안에서 임의의 요소를 고른다. 이 요소를 피벗(pivot)이라고 부른다. 설명을 위해 중간에 위치한 원소를 피벗으로 잡았지만, 아무 원소나 잡아도 상관없다. 이 피벗을 선택하는 방법에도 여러 알고리즘이 있다. 가장 왼쪽의 요소를 피벗으로 삼는 방법도 있고, 랜덤으로 선택하는 방법도 있고, 또 가장 오른쪽의 요소를 피벗으로 삼는 방법도 있는데, 최종적인 성능은 모두 비슷하다. 피벗을 잡았으면, 배열을 순회하면서 피벗보다 작은 쪽과.. 2021. 7. 27. 이전 1 다음