알고리즘

주어진 수들을 정렬해야 하는 경우, 수들이 모두 양수이고, 최대값이 정해져 있다면. 카운팅 정렬 (계수 정렬)로 더욱 빠르게 정렬해 볼 수 있다. ■ 계수 정렬? 계수 정렬 알고리즘은 비교를 하지 않는다. 배열의 인덱스를 사용하여 숫자의 개수를 카운팅, 순서대로 출력하는 것이다. 매우 간단하다. 계수 정렬의 시간복잡도는 O(n) 으로 실행 시간은 짧지만 사용하기 위해 조건이 있다. 먼저 주어진 숫자들이 자연수이고, 최대값이 너무 크지 않아야 한다. 배열의 인덱스를 사용 할 것이기 때문에 양수만 가능하고, 최대값이 너무 커져버리면 메모리에 부담이 커진다. 이러한 조건 때문에 다른 정렬 알고리즘만큼 많이 쓰이지는 않는다. 하지만 위 조건을 충족하는 경우 다른 정렬 알고리즘보다 효율적으로 정렬할 수 있다. ■..