알고리즘 이론 9강. 정렬들의 분류

 

[In place sorting과 Not in place sorting]

- In Place Sorting : 데이터를 정렬하는데 입력사이즈 n정도 크기이상의 추가 공간이 필요하지 않은 정렬

- Not in place Sorting : 위와 반대(정렬하는데 많은 추가 공간 필요한 정렬)

 

 

 

[Stable sort과 Unstable sort]

- Stable sort : 요소들이 정렬된 후에 같은 key값 가진 요소들끼리는 원래의 순서 유지하는 정렬

- Unstable sort : 요소들이 정렬된 후에 같은 ket값 요소들까리 원래의 순서 유지하지 않는 정렬

 

 

 

[정렬 알고리즘의 종류]

- O(n^2) 정렬 알고리즘 : 삽입정렬, 선택정렬, 버블정렬

- O(nlogn) 정렬 알고리즘 : 힙정렬, 병합정렬, 퀵정렬

 

- 배열의 크기가 클때 : 병합정렬, 퀵정렬

- 배열의 크기가 작을떄 : 삽입정렬, 선택정렬 (5~20일때 권장, 15% 실행시간감소)

 

 

 

[병합정렬 vs 퀵정렬]

: 둘다 분할과 정복 기법 알고리즘 (재귀)

: 둘다 평균 케이스 O(nlogn)

: 병합정렬은 최악케이스일때 O(nlogn), 퀵정렬은 최악케이스일때 O(n^2)

: 병합정렬은 2n의 공간 필요, 퀵정렬은 추가 공간 필요 X

 

=> 데이터 이동/복사 많고, 비교횟수 적을때 : 병합정렬

=> 적은 데이터 이동/복사, 비교횟수 많을때 : 퀵정렬

 

 

 

[비교 기반 정렬과 non비교 기반 정렬]

: 생략

 

 

[Internal Sorting vs External Sorting]

- Internal Sort : 정렬된 데이터가 전부 컴퓨터의 메인 메모리에 저장

- External Sort : 정렬된 데이터 일부가 외부, 느린 장치에 저장

 

 

 

[정렬알고리즘의 수행시간]

Name	Average	Worst	Memory	Stable	Method
Bubble sort	O(n^2)	O(n^2)	O(1)	Yes	교환
Selection Sort	O(n^2)	O(n^2)	O(1)	No	선택
lnsertion Sort	O(n^2)	O(n^2)	O(1)	Yes	삽입
Merge Sort	O(nlogn)	O(nlogn)	O(n)	Yes	병합
Quick Sort	O(nlogn)	O(n^2)	O(1)	No	부분화(partition)
Heap Sort	O(nlogn)	O(logn)	O(1)	No	선택

 

: 쉬운 구현(Simplicity)과 효율성(efficiency)간의 균형이 중요하다.