Sort - counting sort (계수정렬)

오늘은 Counting sort 에 대해서 공부해보려고 한다!

 

이론상으로는 신박하고, 이해하기 쉽지만

 

코드로 단계씩 이해하려다보니 쬐끔씩 머리가 복잡해진다 껄껄

 

할 수 이따..☆

 

 

정렬알고리즘 중 하나인 카운팅 알고리즘은

집합에 각 항목이 몇 개씩 있는지 세는 작업을 한 뒤 정렬하는 알고리즘이다!

 

시간복잡도는 O(n + k): n 은 리스트 길이, k는 정수의 최대값이다.

퀵소트가 가장 빠르다고 알고 있었는데,

정수의 최대값이 무한대로 크지 않는 이상

카운팅소트도 어마무시하게 빠른 정렬알고리즘이었다,,!!!

(무지했던 나 반성해,,,,,)

 

 

여튼! 예시로 카운팅 정렬을 이해해봅시다~!~!

 

예를 들어

for_sorting_list = [6, 6, 6, 5, 4, 3, 2, 1, 1, 0] 이라고 해보자.

 

먼저 가장 큰 원소가 무엇인지 알아야한다!

for_sorting_list 배열에선 6이 가장 큰 것임을 알 수 있다.

따라서 크기가 6인 배열을 만들어서 각 원소의 개수를 넣어준다!

 

각 원소별 개수

 

다음으로 이 배열을 누적시켜줄 것이다.

 

왜냐? 그건 이따가~~~

 

 

 짜잔-

이제 이 배열의 의미를 살펴보자!

 

이 배열의 이름을 A라고 해보자.

지금은 인덱스가 0번부터 시작했기 때문에 -1를 하고 바라볼 것이다!

(누적배열의 인덱스가 1부터 시작이라면 -1를 하지 않아도 된다!!)

A[0]==1 --> 원소 0은 1-1 == 0번인덱스까지 있다!

A[1]==3 --> 원소 1은 3-1 == 2 번 인덱스까지 있다!

A[2]==4 --> 원소 2은 4-1 == 3 번 인덱스까지 있다!

A[3]==5 --> 원소 3은 5-1 == 4 번 인덱스까지 있다!

A[4]==6 --> 원소 4은 6-1 == 5 번 인덱스까지 있다!

A[5]==7 --> 원소 5은 7-1 == 8 번 인덱스까지 있다!

A[6]==10 --> 원소 6은 10-1 == 9 번 인덱스까지 있다!

 

요런 느낌이다.

그러면 한 단계 한 단계 정렬을 해보쟈

 

A배열의 끝 원소가 10 이라는 것은 정렬할 원소의 개수가 10개란 의미이다!

따라서 길이가 10인 Result 배열을 먼저 만들자!

 

짜잔.

이런 느낌이다.

기존 배열인 for_sorting_list의 마지막 요소부터 탐색한다.

요소 0은 누적배열 0번인덱스로 가고, 값이 1이므로 Result에서  1-1 == 0번 인덱스에 0이 저장된다.

(요소 0은 0번 인덱스에 있다!)

 

아마.. 아직 헷갈릴 것이다.

(이걸 쓰고 있는 나도 계속 헷갈린다 하하)

 

두 번째 단계를 봐보자!

아니다 뭔가 잘못됐다.

위에 사진에서 for_sorting_list를 잘못 적었다..ㅎㅎ

*for_sorting_list = [6, 6, 6, 5, 4, 3, 2, 1, 1, 0]

(위에 단계에는 문제 없다!)

 

 

뒤에서 두번째 요소인 1을 보자.

idx == 1의 값은 3이다.

따라서 Result배열의 3-1==2 이덱스에 1을 넣어준다.

 

마지막으로 한 단계만 더 해보자!

1) 뒤에서 3번째 요소가 1이다

2) idx==1인 부분의 값은 2이다.

3) 2에서 1을 빼준다(인덱스 차이 때문. -> 1부터 시작하게 된다면 안빼도 됨!)

4) Result[1]에 1을 넣어준다.

5) 끗!

 

 

이러한 방법으로 counting sort를 진행하다 보면

 

이렇게 마무리가 된다!

즉 Result 배열에 sort가 되어서 저장된 것을 확인할 수 있다 ㅎㅎ

 

 

 

counting sort..

쉬우면서도 헷갈린...*

계속 반복적으로 봐야겠다 끠끠

다음엔 counting sort 관련 문제를 풀어볼 예정이다-!

그때도 화이팅이다.☆(아마 오늘)