계수 정렬1

• 

  계수 정렬 (+Java 코드) 1. 카운팅 정렬이란 카운팅 정렬이란 단어 그대로 정렬 알고리즘 중 하나입니다. 그렇다면 앞에 붙은 카운팅은 무엇일까요? 무엇을 카운팅한다는 것일까요? 정답은 데이터의 값이 몇 번 등장했는지를 카운팅하는 것입니다. 대부분의 정렬은 데이터의 값을 직접 비교하여 정렬하는 경우가 많지만 데이터 값의 직접 비교는 시간 복잡도가 O(NlogN)보다 작아질 수 없다는 한계가 존재합니다. 그에 비해 카운팅 정렬은 O(N) 의 시간 복잡도를 자랑하는데요! 어떻게 가능한 것일까요? 2. 동작 방식 아래 그림과 같은 배열을 정렬하고 싶다고 가정하고 동작 방식을 설명하겠습니다. (1) 카운팅 배열 만들기 카운팅 정렬에는 기존 배열 외에도 카운팅 배열이 따로 필요합니다. 즉, 데이터가 얼마나 등장하는지를 배열 인덱스를 통해 .. Algorithm & Data Structure/이론 2021. 8. 9.