선형시간 정렬1 알고리즘 8장 - 선형시간 정렬 알고리즘 : 계수 정렬 - 알고리즘 8장- 선형시간 정렬 알고리즘 : 계수 정렬 - 앞 장에서 설명한 정렬 알고리즘은 비교 연산을 통해서 정렬을 하는 방식을 취했다. 비교 연산은 두 개의 원소의 관계를 크고 작음에 따라 비교하여 판단하는 연산이다. 비교연산으로 정렬하는 방법은 아무리 빨라도 nlgn보다는 빠를 수가 없다. 하지만 비교를 하지 않는 방법으로 하면 이 보다 따른 시간으로 수행이 가능하다. 이런 방법으로 계수 정렬이 있다. 계수 정렬은 실제 숫자를 세는 방법으로 숫자가 몇 개인지를 기록한다. x라는 입력은 x보다 작은 원소의 개수가 I-1개라면 정렬 후에 I번째에 위치해야 한다. x보다 작은 원소의 개수는 원소를 개수를 세어서 확인할 수 있다. 계수 정렬에 대한 예를 한 번 들어보자. A라는 배열이 입력으로 들어왔다고 .. 2017. 6. 8. 이전 1 다음
