정렬

특정 값을 기준으로 데이터를 순서대로 배치하는 방법

구현 쉬움, 느림

버블 정렬, 삽입 정렬, 선택 정렬

구현 조금 더 어려움, 빠름

합병 정렬, 힙 정렬, 퀵 정렬, 트리 정렬

하이브리드 정렬

팀정렬, 블록 병합 정렬, 인트로 정렬

기타정렬 알고리즘

기수정렬, 카운팅정렬, 셸정렬, 보고 정렬

정렬 알고리즘 복잡도 Summary

정렬방법	$\Omega(n)$	$\Theta(n)$	$O(n)$	보조메모리	안정성
버블 정렬	$n$	$n^2$	$n^2$	$1$	O
삽입 정렬	$n$	$n^2$	$n^2$	$1$	O
선택 정렬	$n^2$	$n^2$	$n^2$	$n$	X
합병 정렬	$nlogn$	$nlogn$	$nlogn$	$n$	O
힙 정렬	$nlogn$	$nlogn$	$nlogn$	$1$	X
퀵 정렬	$nlogn$	$nlogn$	$n^2$	$logn$	X
트리 정렬	$nlogn$	$nlogn$	$n^2$	$n$	X
기수 정렬	$dn$	$dn$	$dn$	$n + k$	O
계수 정렬	$n + k$	$n + k$	$n + k$	$n + k$	O
셸 정렬	$nlogn$	gap에따라	$n^2$	$1$	X