퀵소트 는 Pivot 값을 이용하여 점차적으로 정렬 범위를 좁혀나가는 식의 정렬 알고리즘이다.
여기서 Pivot이란 정렬 고려 범위를 좁혀나가기 위해 작은수의 데이터와 큰수의 데이터 Block을 나누는 기준 값인데,
퀵소트의 연산 속도는 입력 데이터 양이 방대할 수록,
- Pivot 값의 선정과
- 입력된 데이터의 배열이
굉장히 중요하다.
일반적으로 잘 알려진 퀵 소트의 정렬방식을 적용할 경우에 비효율적으로 동작하는 입력의 경우는 아래와 같다.
- 오름차순 정렬을 하고자 하는데, 입력 배열이 내림차순으로 정렬되어있는 경우. (혹은 그 반대의 경우)
- 배열 내 중복 값이 많은 경우.
정렬이라는 것은 어짜피 다양한 input을 가질 수 있고, 그중에서도 발생 가능한
최악의 case를 회피하거나 다른 경우와 별 차이없이 원만하게 해결가능 하도록 하는것이 큰 최적화 포인트가 된다.
위 내용을 바탕으로, 퀵소트가 최악의 사태를 모면하기 위해 아래와 같은 최적화 테크닉이 추가 될 수 있다.
====================================
Ideal Pivot Selection Algorithm
Pivot 은 전체 정렬을 위한 element 중 가장 중간에 가까운 값이 선정될 수록 정렬에 효율적이다.
- random pick : 모든 정렬범위의 개체중 랜덤하게 1개를 추출
- start, middle, end compare : 시작, 중간, 끝 개체중 중간 값을 pivot으로 사용
Element Shuffling
- linear random swapping : 배열 가장 앞의 index를 기준으로 하여 N개의 모든 index를 한번씩 random swap 하는 셔플링 기법
Block Partitioning
- 3 way partitioning : 선택된 pivot을 기준으로 중복값을 가운데, 작은값을 왼쪽, 큰값을 오른쪽으로 하여 3개의 block으로 파티셔닝 하는 기법
====================================
그 외 퀵소트에 대한 자세한 개념과 구현 방법은 여기를 참조하시길 바랍니다.
끝 !
