[자료구조론] 정렬

 

정렬의 수행시간

	수행시간	최악의 경우 수행시간
선택 정렬	O(n^2)	''
거품 정렬	O(n^2)	''
삽입 정렬	O(n^2)	''
셀 정렬	O(n^2)	''
퀵 정렬	O(nlogn)	O(n^2)
합병 정렬	O(nlogn)	''
힙 정렬	O(nlogn)	''
기수 정렬	O(k(n+q)	''

※ 퀵정렬의 경우 이미 정렬되어 있을 때 최악의 수행시간을 가진다.

※ 선택정렬에서 최악의 자료이동횟수는 n회

안정 배열

- 같은 값을 가지는 배열 정렬시, 그 순서가 같은거

- 거품정렬, 삽입정렬, 합병정렬, 기수정렬

 

제자리정렬

- 추가 메모리를 거의 사용하지 않는 것

- 제자리정렬이 아닌 것 : 합병정렬 , 기수정렬

 

정렬의 특징

	특징
선택 정렬	최댓값 또는 최솟값을 선택한 후 맨 앞 또는 맨 뒤로 자리 변경
거품 정렬	인접한 두 키 크기 비교 (회전 당 배열 다 검사)
삽입 정렬	이미 정렬된 부분에 새로 삽입
셀 정렬	간격을 정하여 정렬
퀵 정렬	제어키, 피봇키 사용, 분할정복법 사용
합병 정렬	외부정렬에서 주로 사용
힙 정렬	최대힙을 사용하여 정렬
기수 정렬	다중키에 의한 정렬, 큐와 스택 사용