카운팅 정렬
원소 간 비교없이 정렬
모든 원소가 양의 정수이고, 최댓값을 알고 있을 때 사용
시간복잡도가 적은 것이 장점
자, 위의 설명은 머릿속에서 지워버리고 아래 설명만 보자.
예를 들어, 다음과 같이 순서가 엉망인 original 리스트가 있다.
orginal = [5, 0, 1, 1, 4, 3, 1, 4, 5, 2, 1]우리는 지금부터 original 리스트를 카운팅 정렬 할 것이다.
(단, 카운팅 정렬을 할 때에는 반드시 최댓값을 알 수 있어야한다!!)
위 original 리스트를 카운팅 정렬을 한다면 최종결과는 다음과 같다.
result = [0, 1, 1, 1, 1, 2, 3, 4, 4, 5, 5]이 과정에서 3가지만 기억하자!
첫번째, original 리스트 원소들의 빈도 값을 세어 counting 리스트를 만들어준다.
counting = [1, 4, 1, 1, 2, 2]두번째, counting의 요솟값에 직전 요솟값을 더해준다.
counting = [1, 5, 6, 7, 9, 11]세번째, 이제 우리는 original 리스트와 counting 리스트를 사용하여 최종결과물(result)을 만들어낼 것이다.
result = [0, 1, 1, 1, 1, 2, 3, 4, 4, 5, 5]🌈첫번째를 코딩으로!
# 첫번째!
original = [5, 0, 1, 1, 4, 3, 1, 4, 5, 2, 1]
# original 리스트 원소들의 빈도 값 리스트 만들기!
counting = [0] * 6
for i in range(len(original):
counting[original[i]] += 1
# counting = [1, 4, 1, 1, 2, 2]여기서 우리는 새로운 리스트 counting을 만들어 주고, 여기에 빈도 값을 넣을 것이다.
(참고)
근데 여기서 의문점이 생길 수 있다.
왜 [0] * 6 이라는 데이터를 미리 넣어주지? 그리고 왜 [0]을 6번 넣어주지??
그 이유는 미리 데이터를 넣어주지 않으면 오류가 발생하기 때문이다.
만약 빈리스트로 설정하고 for 문을 입력한다면... (
counting = [])for i in range(len(original): counting[original[i]] += 1for 문의 첫번째 i 값 = 0
original[0] = 5
counting[5]
빈리스트에 5번째 값이라는 것이 존재할까? 아니다..
그래서 우리는 오류 방지를 위해 임의로 [0] * 6이라는 임의의 데이터를 넣어주는 것이다.
그리고 원소의 갯수가 0~5, 즉 6개이니까 [0]을 6개 입력해주는 것이다~
🌈두번째를 코딩으로!!
# 첫번째!
original = [5, 0, 1, 1, 4, 3, 1, 4, 5, 2, 1]
# original 리스트 원소들의 빈도 값 리스트 만들기!
counting = [0] * 6
for i in range(len(original):
counting[original[i]] += 1
# counting = [1, 4, 1, 1, 2, 2]
############################################
# 두번째!!
# counting 요솟값에 직전 요솟값을 더해주기!
for i in range(len(counting)-1):
counting[i+1] += counting[i]
# counting = [1, 5, 6, 7, 9, 11]여기서 range를 설정할 때, 반드시 len(counting)에 -1을 해줘야 한다.
만약 그냥 len(counting)으로 설정하게 되면 아래 counting[i+1]에서 range 범위를 벗어나게 되어 오류가 발생한다.
그리고 counting[i+1]로 설정하여 마지막 값까지 도달하게 한다.
🌈세번째를 코딩으로!!!
# 첫번째!
original = [5, 0, 1, 1, 4, 3, 1, 4, 5, 2, 1]
# original 리스트 원소들의 빈도 값 리스트 만들기!
counting = [0] * 6
for i in range(len(original):
counting[original[i]] += 1
# counting = [1, 4, 1, 1, 2, 2]
############################################
# 두번째!!
# counting 요솟값에 직전 요솟값을 더해주기!
for i in range(len(counting)-1):
counting[i+1] += counting[i]
# counting = [1, 5, 6, 7, 9, 11]
############################################
# 세번째!!!
# original과 counting 리스트를 사용해서 최종결과물을 만들기!
result = [0] * len(original)
for i in original:
result[counting[i]-1] = i
counting[i] -= 1
# result = [0, 1, 1, 1, 1, 2, 3, 4, 4, 5, 5]~~세번째부터 아마 머릿속에서 대환장파티가 벌어질 것이다..
이제 우리는 original 리스트와 counting 리스트를 사용하여 최종결과물(result 리스트)을 만들어낼 것이다.
그러니 반드시 첫번째와 두번째 for 문을 완벽하게 이해하고 세번째를 바라보자!
-
오류 방지를 위해
result리스트에 임의 데이터 [0] * len(original)을 넣어준다. -
그리고
original과counting리스트를 이렇게 바라보자.for i in original: result[counting[i]-1] = i🙆♀️
original의 값(i) 5 => counting[5]은 11이니까 5은 열한번째로 가야해!!🙆♀️
original의 값(i) 0 => counting[0]은 1이니까 0은 첫번째로 가야해!!🙆♀️
original의 값(i) 1 => counting[1]은 5이니까 1은 다섯번째로 가야해!!🙅♀️===>>> 하지만,
original의 값(i) 1 => counting[1] 엥? 또 나왔네 어떡하지??
-
자, 2번의 마지막처럼 같은 값이 다시 나올 것을 대비하여 counting(i) 값을 1씩 줄여준다.
result[counting[i]-1] = i다음에
original의 같은 원소(값)가 나온다면 이전 동일 원소의 앞(전)에 위치하게 된다.
이 모든 과정을 완료하면
result리스트는 다음과 같게 된다.result = [0, 1, 1, 1, 1, 2, 3, 4, 4, 5, 5]
🧷 정리
카운팅 정렬을 하기 전에..
원본 리스트가 모두 양의 정수로 이루어져있는지
(max 함수를 쓰지 않는 전제하에) 최댓값을 한번에 알아볼 수 있는지
카운팅 정렬 중에..
🔍 3가지 순서만 잘 이해하자!
원본 리스트 요소 갯수 세서 카운팅 리스트로 만들기
카운팅 리스트 요소들을 인덱스 순서대로 누적으로 합하기
원본 리스트와 카운팅 요소를 사용하여 최종 리스트 만들기
✒️ 즉, for 문 3개를 써야한다는 것!!
카운팅 정렬 후에..
소리 벗고 팬티를 질러보자!
