카운팅 정렬하기

배열이나 리스트를 정렬하는 방법은 여러가지가 있는데

그 중에서도 리스트의 길이가 길지 않을 때 빠르고 유용한 카운팅 정렬에 대해 알아보자.

 

기본 원리는 이렇다.

정렬할 배열의 최대값보다 1이 더 큰 빈 배열이나 딕셔너리를 만든다.

 

그리고 정렬할 배열을 순회하면서

배열의 값에 해당하는 인덱스나 키의 값을 1씩 올려주면 된다.

 

이렇게하면 정렬할 배열의 원소에 해당하는 갯수만큼 카운팅되어있는 배열이나 딕셔너리를 얻은 셈이다.

 

이제 이 배열 혹은 딕셔너리를 순회하면서

배열이라면 인덱스를 해당하는 값만큼 출력하고

딕셔너리라면 값에 해당하는 만큼 키의 값을 출력하면 된다.

 

inputArr = [1,2,3,2,1]
maxnum = max(inputArr) #최대값 구하기
mylist = [0]*(maxnum + 1)#최대값보다 1더 큰 리스트 생성[0,0,0,0]

for i in inputArr : 
	mylist[i] +=1	#input의값에 해당하는 인덱스에 1씩 추가

print(mylist) #[0,2,2,1] 1이 2개, 2가 2개 3이 2개이다.

sortedlist=[]

for j in range(len(mylist)): #mylist 길이 만큼 순회
	for _ in range(mylist[j]) : #mylist[j]의 값이 inputArr에 j가 몇 개 있는지 의미하므로 range로 순회
         sortedlist.append(j)	# j의 값을 sortedlist에 넣어준다.

print(sortedlist) #[1,1,2,2,3]