이 3가지 정렬을 안다고해서 그냥 지나가듯 마무리 짓기엔 너무 아깝다는 생각이든다.
우리가 언제 어느상황에서 더 효율적으로 이 3가지의 정렬들을 사용할 수 있을까?
그러면 먼저 이 세 가지의 수행시간 분석도를 짚고 넘어가보자.
위의 세가지 수행시간인 최악, 평균, 최선으로 분류할 수 있다.
이러한 경우의 조건은 우리가 정렬하고자 하는 값들이 이미 정렬이 되어있을때로 가정을 해보면 이해하기 쉬울것이다.
이미 정렬이 되어있는 상태에서 선택과 버블정렬은 의미없는 수행을 반복하지않겠는가?
버블정렬 같은경우에 특정 코드를 삽입해서 이미정렬되어있다는 것을 알려줄 수 잇으나
그러려면 메모리가 하나 더 추가가 되어있어야 하므로 효율적이지 못한 결과가 나온다.
그러려면 메모리가 하나 더 추가가 되어있어야 하므로 효율적이지 못한 결과가 나온다.
반면에 삽입정렬은 처음 과정부터 n까지 앞뒤의 크기비교를 바탕으로 시작이되므로,
Theta(n)의 시간이 걸리게 된다.
우리가 정렬을 배웠으면 단순한 원리를 알기보다는 어떠한 상황에서 더 효율적인 방법을 찾을 수 있을지 잘 기억해두자!
댓글 없음:
댓글 쓰기