[Algorithm] 퀵 정렬 (Quick Sort)

개념

Pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 위치시키는 분할과 정복에 기반한 알고리즘

 

I. 퀵 정렬 (Quick Sort)의 개요

 

가. 퀵 정렬의 정의

- Pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 위치시키는 분할과 정복에 기반한 알고리즘

 

 

나. 퀵 정렬의 특징

 

- 분할과 정복 기반

- 재귀호출 구조

- 정렬을 위한 별도의 스택이 필요

- 수행시간 복잡도: O(n·log2n)

 

 

Ⅱ. 퀵 정렬의 단계 및 사례

 

가. 퀵 정렬의 단계

 

- 정렬할 원소들의 집합에서 Pivot 값을 설정 - Pivot보다 큰 값은 오른쪽, 작은 값은 왼쪽 - 분할된 집합의 크기가 1이 될 때까지 반복

 

 

나. 퀵 정렬의 사례

 

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); }}

 

 

[Algorithm] 해시 탐색 (Hash Search)

[Algorithm] 해시 탐색 (Hash Search)

 

[용어/개념] 멧칼프의 법칙(Metcalfe's Law)/암달의 법칙(Amdal's Law)/무어의 법칙(Moore's Law) 비교

[용어/개념] 멧칼프의 법칙(Metcalfe's Law)/암달의 법칙(Amdal's Law)/무어의 법칙(Moore's Law) 비교