반응형
1. Quick Sort
이는 merge sort와 다르게 추가 배열을 만들지 않아도 된다.
quick sort의 알고리즘은 아래와 같다.
1. 배열에서 어느 한 값을 pivot으로 설정한다.
2. pivot을 기준으로 왼쪽은 pivot보다 작게 오른쪽은 pivot보다 큰 숫자가 들어가도록한다.
3. pivot을 기준으로 왼쪽과 오른쪽을 나눠서 재귀를 실행시킨다.
증명 (proof by Invariant)
invariant :
조건1 . a 배열이 입력이라고 가정하고 b배열이 sorting된 후 배열이라고 하면, a와 b의 값이 같아야한다.
조건2. 배열 b는 b[0]<b[1]< ... < b[n] 이어야한다. (같은 값은 없다고 가정)
집합조건을 깨는 코드는 없으므로 조건1 성립
증명 (proof by Induction)
위 invariant의 조건2 를 수학적 귀납법으로 증명해볼 것이다.
Base : n=1 은 할일이 없다
Step : qsort(a, d-1)와 qsort(a,+b+1, n-d-1)이 성공시 a[0]<a[1] ... a[d-1] 과 a[d+1]< a[d+2] ... a[n-1] 라면
n일때, qsort() 성공 → a[0]<a[1] ... a[n-1]
2. The Complecxity
잘되면 O(nlogn)
안되면 O(n^2)
반응형
'학부 내용 정리 > [ 2-2 ] 알고리즘' 카테고리의 다른 글
| [ 알고리즘 ] MST(1) : Prim Algorithm (0) | 2022.10.11 |
|---|---|
| [ 알고리즘 ] 자료구조 내용 복습 (0) | 2022.10.09 |
| [ 알고리즘 ] 정렬(2) Merge, Recursive Merge Sort (0) | 2022.10.09 |
| [ 알고리즘 ] 정렬(1) : Selection Sort, Recursive Selection Sort (1) | 2022.10.09 |
| [ 알고리즘 ] Binary Search, Recursive Binary Search (2) | 2022.10.03 |