[서울대학교 논자시 준비] 알고리즘 : chapter 4 정렬 - 계수정렬

앞서 설명한 정렬 알고리즘들의 공통점은 원소끼리 비교하는 것으로만 정렬을 한다는 것이다. 이런 정렬을 '비교정렬'이라고 한다. 이러한 비교정렬은 최악의 경우 수행 시간이 절대 O(nlogn)을 밑돌 수 없다. 정렬하고자 하는 원소들이 특수한 성질을 만족하면 이 하한보다 더 빠른 정렬 알고리즘을 적용할 수 있다. 기수정렬 기수 정렬은 입력이 모두 k자릿수 이하의 자연수인 특수한 경우에 사용할 수 있는 방법으로 O(n)시간이 소요되는 정렬 알고리즘이다. 기수정렬은 우선 가장 낮은 자릿수만 가지고 모든 수를 정렬한다. 그런 다음 가장 낮은 자릿수는 잊어버린다. 그리고 앞과 같은 방법으로 더 이상 자릿수가 남지 않을 때까지 반복한다. 이렇게 하면 마지막에는 정렬된 배열을 갖게된다. 계수정렬 계수 정렬은 정렬하고..

2023.08.26