알고리즘 강의 - 4 [정렬]

서론

정렬은 데이터의 열을 특정 순서에 따라 줄을 세우는 과정이다.
정렬은 분할정복,힙 등의 다양한 알고리즘 기법을 배울 수 있는 주제이다.

다양한 정렬 알고리즘

	평균 시간복잡도	최악 시간복잡도	공간복잡도	안정정렬	비고
삽입정렬	$O(N^2)$	$O(N^2)$	$O(1)$	O	간단한 정렬법
병합정렬	$O(n \log_2 n)$	$O(n \log_2 n)$	$O(N)$	O	최악의 경우에도 빠름
퀵정렬	$O(n \log_2 n)$	$O(1)$	$O(n \log_2 n)$	O	최악인 경우는 O($N^2$)이지만 일반적으로 가장 빠름
힙정렬	$O(n \log_2 n)$	$O(n \log_2 n)$	$O(1)$	O	힙을 활용
버킷정렬	$O(N+A)$	$O(N+A)$	$O(N+A)$	O	정렬하고 싶은 값이 작을 때 유용

참고자료

문제 해결력을 높이는 알고리즘과 자료구조(오츠키 켄스케)