6일차 정리(퀵 정렬, 병합 정렬)

1. 퀵 정렬(quick sort)

- 리처드 호어(C. A. R. Hoare)가 붙인 이름

- 분할 정복 알고리즘과 재귀 호출을 사용한 퀵 정렬

- 작업수행 절차

 A. 스캔

  1) a[pl] >= x가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔

  2) a[pr] <= x가 성립하는 요소를 찾을 때까지 pr을 왼쪽으로 스캔

 B. 분할시 나눠지는 그룹

  1) 피벗 이하의 그룹 : a[0], ... , a[pl-1]

  2) 피벗 이상의 그룹 : a[pr+1], ... , a[n-1]

  또는

  피벗과 pl, pr이 모두 일치하는 값을 가지는 그룹인경우 : a[pr+1], ... , a[pl-1]

- 비재귀적인 퀵 정렬 코드

- 스택코드

A. lstack : 나눌 범위의 왼쪽 끝 요소의 인덱스를 저장하는 스택

B. rstack : 나눌 범위의 오른쪽 끝 요소의 인덱스를 저장하는 스택

-> 스택의 용량 : 분할시 요소의 개수가 적은 배열일수록 적은 획수로 분할을 종료할 수 있다.  그리고 스택에 쌓여 있는 데이터의 최대 개수를 줄일수 있따. 만약 배열의 요소 개수가 $n$개라면 스택에 쌓이는 데이터의 최대 개수는 $log{n}$보다 적다.

-> 피벗 선택 : 만약 데이터가 a[0] ~ a[8]개 있다면 a[0] = left, a[8] = right, a[4] 는 마지막 요소인 a[8]보다 1개 적은 a[7]과 데이터를 교환하고 pl 은 a[1] 부터 pr은 a[6]부터해서 a[0], a[7], a[8]를 제외한 범위인 a[1] ~ a[6]까지의 범위를 지정하는 방식을 하는게 조금 더 빠른 속도로 정렬

-> 시간 복잡도는 $O(nlog{n})$ 입니다. 다만 정렬할 배열의 초기값이나 피벗의 선택방법에 따랄 시간 복잡도가 증가하므로 최악의 시간복잡도는 $O(n^{2})$입니다.

2. 병합 정렬

- 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘

- 단순 병합정렬

- 배열 병합의 시간 복잡도는 $O(n)$이고 데이터의 요소가 n개 일때, 병합 정렬의 단계는 $log {n}$만큼 필요하므로 전체 시간 복잡도는 O(n log{n})이다.

- 병렬 정렬은 서로 떨어져 있는 요소를 교환하는 것이 아니므로 안정적인 정렬 방법이다.