I. 퀵 정렬 (Quick Sort)의 개요
가. 퀵 정렬의 정의
Pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 위치시키는 분할과 정복에 기반한 알고리즘
나. 퀵 정렬의 특징
- 분할과 정복 기반
- 재귀호출 구조
- 정렬을 위한 별도의 스택이 필요
- 수행시간 복잡도: O(n·log2n)
Ⅱ. 퀵 정렬의 단계 및 사례
가. 퀵 정렬의 단계
나. 퀵 정렬의 사례
void quicksort(element list[], int left, int right) { int pivot, i, j; element temp; if(left < right) { i = left; j = right + 1; pivot = list[left].key; do { do i++; while(list[i].key < pivot && i<=right); do j--; while(list[j].key > pivot); if(i < j) SWAP(list[i], list[j], temp); } while(i < j); SWAP(list[left], list[j], temp); quicksort(list, left, j - 1); quicksort(list, j + 1, right); }} |
'IT 용어 및 개념 > Algorithm' 카테고리의 다른 글
[Algorithm] 최소신장트리 알고리즘 (0) | 2024.09.15 |
---|---|
[Algorithm] 기수 정렬 (Radix Sort) (0) | 2024.09.14 |
[Algorithm] 버블 정렬 (Bubble Sort) (0) | 2024.09.14 |
[Algorithm] 해시 탐색 (Hash Search) (0) | 2024.09.14 |
[Algorithm] 합병 정렬 (Merge Sort) (0) | 2024.09.14 |