정렬 알고리즘

정렬알고리즘은 선택/평가할 때의 고려요소

- 정렬할 데이터의 양

- 데이터와 메모리

- 이미 정렬된 정도(값들의 분포 상태)

- 필요한 추가 메모리의 양

- 상대위치 보존여부

 

 

대부분 O(n^2)과 O(n logn) 사이이다.

정렬알고리즘의 분류_1

비교 기반 알고리즘

- 선택정렬

- 버블정렬

- 삽입정렬

- 병합정렬

- 퀵정렬

- 힙정렬

 

그외 알고리즘(분포기반 정렬)

- 기수정렬

- 계수정렬

 

정렬알고리즘의 분류_2

기본적인 정렬 알고리즘 O(n^2) / 단순하나 비효율적 알고리즘

- 선택정렬

- 버블정렬

- 삽입정렬

 

효율적인 정렬 알고리즘 O(n logn)

- 병합정렬

- 퀵정렬

 

특정조건에서의 고효율 정렬 알고리즘 O(n)

- 기수정렬

- 계수정렬

 

정렬알고리즘의 분류_stable/unstable

Stable Sort

- 삽입정렬

- 선택정렬

- 버블정렬

- 병합정렬

(비교 외 기반 -> 별도의 장치 필요)

- 계수정렬

- 기수정렬

 

Unstable Sort

- 힙정렬

- 퀵정렬

 

정렬알고리즘의 분류_in-place

in-place sorting 알고리즘

- 삽입정렬

- 선택정렬

- 버블정렬

- 쉘정렬

- 힙정렬

- 퀵정렬

 

not-in-place sorting 알고리즘

- 합병정렬

- 계수정렬

- 기수정렬