왠지 모르겠지만, 계수정렬이란 개념이 도저히 기억이 안났다.
2년전엔 다뤘던 개념이라고 강의자료엔 똑똑히 나와있지만, 내 머릿속엔 이미 사라진지 오래여서 이를 다뤄보려한다.
가장 빠른 정렬 알고리즘(특수한 상황)
계수 정렬이란, A라는 정수 배열을 정렬할때, A에 등장하는 숫자들이 몇번 등장하는지 세어(Counting) 정렬하는 방식이다.
A=[2,5,4,3,3,4,5,1,1,0,0] 인 경우에
0:2번,1:2번,2:1번,3:2번,4:2번,5:2번
이런식으로 몇번 등장했는지 파악만 하더라도 가장 작은 수부터 쭉 몇번 등장했는지 출력,혹은 저장만 해줘도 정렬이 끝이난다.
정렬된 배열을 B라고 가정하면,
B=[0,0,1,1,2,3,3,4,4,5,5]
사실, 이런식의 상황이 많이 주어지는것은 아니다.
일반적인 상황에서 가장 빠르다고 알려진 QuickSort() 알고리즘의 평균 시간 복잡도는 O(nlogn)이지만,
지금 다루는 계수정렬 같은 경우, O(n)의 평균 시간 복잡도를 갖는다.
근데 왜 난 기억을 못했을까?
솔직히 내가 기억 못한건 그냥 군대갔다와서,,,
비효율적인 상황이 너무나도 많고, 일반적으로 사용하기 어렵기 때문이다.
단적인 예로 A=[0,200,3,100] 이란 배열을 정렬한다고 가정해보자,
계수 정렬을 사용하게 된다면, 존재하지도 않는 1,2,4,........ 등의 원소들을 가지고 있는지, 최대값인 200까지의 의미없는 반복을 해야하기 때문에, 숫자 크기에 큰 영향을 받아, 비효율적인 상황이 나온다.(메모리 측면에서도 마찬가지)
하지만, 적절한 상황이 나온다면 확실히 정렬 속도가 빠르다.
unsorted = [0] * T #배열 내 숫자의 최대값 크기 만큼의 배열 생성
for i in range(N): #N개의 숫자를 받았다고 가정하였을때.
n = int(sys.stdin.readline())
unsorted[n] = unsorted[n]+1 #T만큼의 배열 공간중,
#입력받은 숫자 ex)127 라면
#unsorted[127](기존값 0)
#+1해서 unsorted[127]=1
for i in range(T):
if unsorted[i] != 0: #등장한 숫자는 1 이상일테니.
for j in range(unsorted[i]):
print(i) #문제푼 코드 그대로라서 바로 출력하지만,
#새로운 배열에 저장해서 사용해도 되고.파이썬 환경에서 짠 코드이고, 다음장에서 다룰 문제에 대한 나의 답이기도 하다.
첫 포스팅
꽤 오래 공부도 했고, 이해도 완전히 했다고 생각했는데, 글을 쓰면서 보니 놓친 부분도 많아보이고, 개념적인 부분에서도 설명을 완전히 못하였다는 생각이 든다...
그래도 글을 올리는 이유는 하나씩 하나씩 올려가다보면 성장하는게 보이지 않을까 하는 기대,, 그리고 워낙 게으른지라 뭘 실행조차도 하지 않는 내가 꼴보기 싫을거같아서 많이 모자라고 부끄럽지만 올려본다..
이제 시작이니까,초라해도 점차 나아지길🤞
