정렬 알고리즘 정리

§ n log n 은 어떻게 나오는 것일까

정렬은 하는 과정은 완전 이진트리 형태의 결정트리(Decision Tree) 형태로 표현할 수 있습니다.

--> 비교를 수행 후, 결과에 따라 좌우 부트리 중 한쪽 부트리로만 순회하는 형태

n개의 잎이 존재하는 포화이진트리의 높이는 최소 log (n+1) 인 것은 다들 아시겠죠

그렇다면 

n! 개의 잎이라면?   log n!

==> 어떠한 비교 알고리즘도 최소 log(n!) 시간을 소요 한다는 것을 알 수 있습니다.

이를 수학적으로 유도하면

log(n!)    = log( n * (n-1) * (n-2) *....* 3 * 2 * 1 )

>= log(n * (n-1) * .... * (n/2) )

>= log( (n/2) * (n/2) * (n/2) *...* (n/2) ) = log (n/2)^(n/2) = (n/2) log (n/2)

==> Ω (n log n)  ( 하한 )

그렇습니다 ㅎㅎ

§ 정렬의 안정성

(키, 원소) 쌍으로 구성된 데이터 생각

키가 같은 경우,

--> (key_i, element_i ) (key_j, element_j )

--> key_i = key_j 라면

정렬 전에 i가 j보다 앞서 있었는데, 정렬 후에도 마찬 가지라면

==> 이 정렬 알고리즘은 안정적이라고 합니다.

안정적인 정렬 알고리즘 --> 선택 정렬, 삽입 정렬, 합병 정렬

비안정적인 정렬 알고리즘 --> 힙 정렬, 퀵 정렬