[자료구조] 정렬 알고리즘

https://en.wikipedia.org/wiki/Sorting_algorithm

 

정렬 알고리즘이란

원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘

대표적 정렬

- 선택 정렬
- 삽입 정렬
- 거품 정렬
- 힙 정렬
- 퀵 정렬
- 합병 정렬

정렬 방법

안전 정렬 - 정렬 후 중복값 순서가 유지
제자리 정렬 - 추가적인 메모리를 거의 사용 하지 않음
비교 정렬 - 상대적 크기관계를 통해 정렬

 

정렬 알고리즘

	선택 정렬	삽입 정렬	거품 정렬	힙 정렬	퀵 정렬	합병 정렬
최선	n^2	n	n	nlogn	nlogn	nlogn
평균	n^2	n^2	n^2	nlogn	nlogn	nlogn
최악	n^2	n^2	n^2	nlogn	n^2	nlogn
메모리	1	1	1	1	logn ~ n	n
안정	X	O	O	X	X	O
제자리	O	O	O	O	O	X
비교	O	O	O	O	O	O