Quick Sort (퀵 정렬)

개념

- 분할해서 정렬

- 주어진 값에서 기준이 될 값을 정하고 기준이 되는 값보다 작은 값은 왼쪽, 높은 값은 오른쪽으로 우선 정렬한다.

이후 왼쪽은 왼쪽대로 정렬하고, 오른쪽은 오른쪽대로 정렬한다.

- 랜덤 배열에서 빠름

- 순열이나 역순의 경우 매우 느림

(기준값을 선정하는 방법에 따라 속도가 다름)

1. 최소 값이나 최대 값으로 할 경우

2. 이미 정렬된 배열을 정렬할 경우

- 재귀함수 기반으로 구현할 경우 복잡해질 수 있다.

​

기준값이 3라고 정했을 경우

(5,4,'3',2,1) -> (2,1,'3',5,4)

왼쪽 값 정렬 : (2,1) -> (1,2)

오른쪽 값 정렬 (5,4) -> (4,5)

​

최종적으로 (1,2,3,4,5)로 정렬 된다.

​

퀵정렬의 단점을 보안하기 위해 여러 기법들이 개발 되었는데, 그 중에 대표적인 것이 기준값을 랜덤으로 잡는 RandomQuickSort이다.

그리고 무조건 배열의 위치상 중간에 있는 것을 기준 값으로 잡거나, 배열 중에 3개나 9개의 원소를 골라 이들의 중앙값을 피벗으로 고르는 방법이 있다. 이러한 방법에도 최악의 속도가 나올 수도 있는데 그 경우가 극히 드물어진다.

배열이 단순하게 비교 가능한 숫자가 아니라면 중앙값 피벗 방법이 비효율적일 수도 있다.

참고자료에서 이러한 나쁜 케이스들을 없애고 싶다면 하이브리드 퀵 정렬을 사용하라고 한다.

 

다람쥐와 포동포동이

RememberCook 9월 28일 정식 출시!