빠른 정렬(Quicksort)

빠른 정렬(Quicksort)

분할 정복 알고리즘의 일종으로, 평균적으로 매우 빠른 수행 속도를 자랑한다.

- 평균 시간복잡도: θ(n log⁡n)

- 최악 시간복잡도: θ(n^2)

 

빠른 정렬의 진행 과정

 

아래의 배열이 있다.

 

여기서 pivot이라 불리는 기준 값을 하나 정한다. 보통 맨 앞이나 중앙을 선택한다. 나는 중앙을 pivot으로 두겠다.

그 다음, pivot을 제외한 나머지에서 가장 왼쪽은 left, 가장 오른쪽은 right로 둔다.

 

left와 right는 pivot과 비교한다. 

left는 pivot보다 큰 수를 만나면, right는 pivot보다 작은 수를 만나면 대기한 뒤 서로 교환한다.

 

이렇게 left와 right가 움직이다가 left가 right 오른쪽에 위치하면 그만둔다. 단, pivot넘어서 까지 가지 않는다.

 

교환을 하고 나서 한 칸씩 움직인다.

그러면 left가 right보다 커진다. 그럼 정렬을 그만한다.

 

결과적으로, 6을 기준으로 6보다 작은 값은 왼쪽, 큰 값은 오른쪽에 위치한다. 그 다음에 그림에서 보듯이 각 나누어진 배열에서 또 pivot을 정하고 위 설명 과정을 반복하면 전체적으로 오름차순 정렬이 된다.