퀵 정렬
배열에서 기준값(Pivot)을 설정해 작은 값은 왼쪽에, 큰 값은 오른쪽에 배치한다. 재귀적으로 분할해 정렬을 수행한다.
- pivot, left 인덱스와 right 인덱스를 설정한다.
- left값이 피봇보다 작으면 오른쪽으로 이동하고 크면 stop, right값도 똑같이 피봇보다 크면 왼쪽으로 이동하고 작으면 stop한다.
- 둘 다 stop인 경우 두 값을 swap한다.
- left 인덱스와 right 인덱스가 만날 때까지 수행하고, 그 인덱스를 기준으로 파티션을 분할해 정렬을 수행한다.
평균 시간복잡도는 O(nlogn)이지만 최악의 경우(오름차순 되어 있는데 내림차순으로 변경할 때) O(n^2)이다.
병합 정렬
병합 정렬의 기본 원리는 정렬되어 있는 두 배열의 첫 번째 값을 비교해 하나의 배열로 병합하는 원리이다.
따라서 우리가 정렬하고 싶은 무작위 배열을 둘로 나눴을 때 정렬되어 있음을 보장할 수 없으므로 원소의 개수가 1이 될 때까지 분할한다. 그런 다음 하나의 배열로 merge한다.
시간 복잡도는 O(nlogn)을 보장한다. (배열 값을 N번 비교, logN번 분할) 하지만 병합하는 배열을 따로 저장하기 때문에 공간을 사용할 수 없는 경우 퀵 소트를 사용한다.
ref
이 분 짱짱
퀵정렬
병합정렬
'컴퓨터공학 > 알고리즘 ˙ 자료구조' 카테고리의 다른 글
| [알고리즘] 배낭 알고리즘 (fractional 배낭, 0-1 배낭) (0) | 2023.04.29 |
|---|---|
| [자료구조] AVL 트리, Red-Black 트리 (0) | 2023.04.28 |
| [자료구조] B-tree와 B+tree (0) | 2023.04.24 |
| [알고리즘] 2차원 배열 시계 방향 회전, 180도 회전, 전치 행렬 구하기 (0) | 2023.04.10 |
| [C++] 달팽이 알고리즘 (0) | 2023.03.22 |
