Counting sort 구현해보기!

들어가기 전에,,,

코딩에 익숙해지기 위해 한줄 한줄 이해하기위해 노력중입니다!

부족한 부분은 댓글에 피드백해주세요! 언제나 환영입니다!

when?

중복되는 값이 있고 숫자범위가 좁은 경우에 count sort를 사용하면 수행시간이 짧아진다!

 

Hint:

• 1~7사이의 무작위 값 20개가 저장되어있는 listA를 생성
• listA의 최대값과 최소값을 찾아 C리스트를 생성 (0으로 채워져 있는 리스트)
• listA의 각 index를 확인하면서 listC 값을 업데이트
• listC의 업데이트를 끝내면, listB를 생성하고 채우기 

check

• 최대값과 최소값을 뽑는 이유는 listA = [3,4,3,5,2,6,6,8] 일때,                                                                      없는 숫자를 세지않음으로  시간과 공간의 낭비를 줄이기 위함이다
• " for j in range(i): " 에서 j는 메타몽과 같다. range(i)에서 넣는 값에따라 j가 바뀌기 때문.  또한 j에 들어있는 값도 중요하지만, j 의 개수에 집중해보도록 하자
• 파이썬은 리스트를 0부터 센다! 따라서 아래 리스트 a 의 첫번째 요소는  a[ 0 ] = 5 이다. 

index값	0	1	2	3	4
item	5	4	3	7	8

 

• listA : 랜덤값이 length만큼 들어있는 리스트
• listC : listA에 있는 값의 숫자를 0부터 최대값까지 찾아 세주는 리스트
• listB : listC에서 0이 아닌 값들을 갯수만큼 출력하는 리스트

code:

결과값:

 

count sort를 완벽하고 간결하게 구현하지는 못했으나, 이해해보고 반복문과 리스트의 성질을 활용하는 실습이었다!