[알고리즘] 3. 퀵 정렬

 

퀵 정렬: 분할 정복(Divide and Conquer)에 기반한 알고리즘

1. 데이터 집합 내에서 임의의 기준 요소 선택. 기준요소보다 작은 요소는 왼쪽에, 큰 요소는 오른쪽에 위치시킨다.

2. 나누어진 각각의 집합에서 기준요소를 정한 후 1번을 반복한다. 

3. 더이상 데이터 집합을 나눌 수 없을 때까지 반복한다. 

 

*좋은 기준요소를 선택하는 것이 성능에 도움이 된다. 보통 중간값으로 기준요소로 선택함.

 

고려해야할 점

-배열을 데이터 집합의 자료구조로 사용할 때, 분할은 어떻게 수행해야 하는가?(배열은 삽입/삭제가 자유롭지 않다)

-반복되는 분할 과정을 어떻게 처리할 것인가?

 

-> '수색 섬멸' 작전 이용.  2명을 투입해서 한 명은 왼쪽->오른쪽으로 이동하면서 기준요소보다 큰 요소를 찾고 , 다른 한명은 오른쪽->왼쪽으로 이동하면서 기준요소보다 작은 요소를 찾는다. 

이후 두 정찰병이 찾아낸 두 요소를 교환한다. 

 

-Partition() 함수: 정렬 대상의 첫번째 요소를 기준요소(pivot)로 지정하고, while 루프를 통해 분할 수행. 

두 개의 루프는 두 정찰병의 위치를 옮긴다.

첫번째 루프는 DataSet의 왼쪽에서 출발해서 pivot보다 큰 요소를 찾을 때까지 탐색을 계속하면서 Left를 1씩 증가 시킨다. 그러다가 pivot보다 큰 요소를 찾으면 Left에 그 요소가 위치한 인덱스를 저장하고 종료한다. 

다른 루프는 DataSeet의 오른쪽에서 출발해서 pivot보다 작은 요소를 찾아 그 요소의 위치를 Right에 저장한다. 

Left와 Right를 비교한 후(22행), Left가 Right보다 작으면 바꾼다. 두 개가 같다면 두 정찰병이 서로 만났다는 뜻이니 루프 종료.

분할 작업 종료 후 기준 요소와 분할 왼쪽 데이터 집합의 오른쪽 끝에 있는 요소 교환하고 기준 요소의 새 위치 반환. 

 

 

-최선의 경우(분할이 이등분씩 되는 경우): 퀵 정렬의 재귀 호출 깊이는 log2n.

비교 횟수: n , 퀵 정렬의 비교 횟수: nlog2n

-최악의 경우(1,(n-1)씩 분할 되는 경우): 퀵 정렬의 재귀 호출 깊이는 n(n-1)/2

-평균의 경우: 1.39nlog2n