카운팅 정렬이란
카운팅 정렬(Counting sort)은 특정 범위 내의 값을 기반으로 하는 정렬 기법입니다. 배열의 빈도수를 저장한 다음 저장된 빈도수를 활용하여서 정렬하는 방식입니다. (일종의 해싱).
카운팅 정렬 작동 방식
- 배열에 존재하는 값의 각 원소의 개수를 세어줄 새로운 배열 count를 만들어줍니다.
- count 배열의 원소를 누적합 값으로 갱신해준다. 이 작업은 arr에 담긴 원소를 바로 정렬된 위치로 삽입하기 위한 사전작업입니다.
- arr의 길이와 같은 result 배열을 만들어준다. 해당 배열에는 arr의 원소를 정렬된 위치에 삽입할 것 입니다.
- arr의 각 원소값을 count의 인덱스로 사용해 값을 가져온 후, 해당 값을 다시 result의 인덱스로 사용해 arr의 원소로 저장해줍니다.
- 해당 작업을 마친 후 count[arr[i]]의 값을 1 줄여줍니다.
예를 들어, arr 배열이 [3, 1, 2, 3] 이라면 count 배열은 [0, 1, 1, 2] 가 되고, 누적합으로 갱신된 count 배열은 [0, 1, 2, 4] 가 됩니다. 그리고 result 배열은 arr와 같은 크기로 만들어져서 정렬된 값을 담을 준비를 합니다.
다음으로 arr 배열의 값을 하나씩 가져와 count의 인덱스로 사용합니다. 예를 들어 arr[0]은 3이므로 count[3]을 가져와서 4를 얻게 됩니다. 이 값을 다시 result[4]의 인덱스로 사용하여 arr[0]을 result[4]에 저장합니다. 그리고 count[3]의 값을 1 줄여줍니다.
이런 식으로 arr의 모든 원소를 처리하면 result 배열에는 정렬된 값들이 들어가게 됩니다. count 배열을 누적합으로 갱신하고 값을 가져오면서 해당 값들을 result에 삽입하고, count 배열을 갱신하는 과정을 거치게 됩니다.
arr = [5,7,8,2,4,6,9,1,3]
cntDict = {}
for n in arr:
cntDict[n] = 1
result = []
for n in range(len(arr) + 1):
while n in cntDict and cntDict[n] > 0:
result.append(n)
cntDict[n] -= 1
print("카운트 정렬 전 : ", arr)
print("카운트 정렬 후 : ", result)
print(result)조사를 하면서 key값에 정렬을 한다고 해서 딕셔너리로 만들어 보았는데 그냥 리스트로 만드는 게 더 좋았을 거라는 생각이 들면서도 재미삼아 만들어 보았습니다.
카운트 정렬이 이뤄지는 과정인데 이해하시기에 좋을 것 같습니다. 이미지 가져온 사이트 : https://medium.com/@manishsundriyal/counting-sort-in-javascript-abf976e66b8c
부족한 글 읽어주셔서 감사합니다.
