[ 알고리즘 ] 21. Comparison sort

지금껏 우리가 배운 Sort는 Comparison sort이다.

 

Comparison sort = @번째 Index와 비교해서 자리를 바꾸는 sort 

 

이런 Comparison sort의 Time complexity는 오메가(n lg n)  = 최소 n log n 이상은 시간이 걸린다.

 

 

이렇게 n개의 item이 있을 때 sort를 한다고 했을 때

 

1 : 2 번째 인덱스를 비교 = 1번이 크면 오른쪽, 2번이 크면 오른쪽으로 가는 플로우다.

 

- leaf의 수 = item의 permutation

- algorithm의 running time = Path의 length와 관련있다.

- Worst - case running time = height of tree

 

 

따라서, 비교를 통해서 sort를 하는 경우에는 Time complexity가 Ω ( n lg n ) 이 걸린다.

 

 

그럼 비교를 하지 않고, 더 빠르게 sort하는 방법인 Counting sort는 어떻게 할까?

다음 시간에 계속...

 

(출처)

한동대학교 용환기교수님 - 알고리즘