🧚‍♂️알고리즘🧚‍♂️ - 정렬 - 기수 정렬 / 계수 정렬

기수 정렬

값을 바로 비교하지 않는 특이한 정렬

값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교함

시간복잡도 O(kN) 

K는 데이터의 자릿수

 

10개의 큐 사용 ( 0,1,2,3,4,5,6,7,8,9 담당)

일의 자릿수 -> 십의 자릿수 -> 백의 자릿수 ... 순으로 정렬돤 데이터들을 계속 재정렬

(이전 자릿수에서 정렬된 순서 기준으로 다음 자릿수에 저장!)

 

계수 정렬

데이터의 최댓값 크기의 배열에 각 요소의 배열 등장 횟수를 count해 저장한 후

작은 인덱스값 순서대로 출력

O(n + k)

(k는 Input 요소의 최댓값)( k가 작은 수라면 O(n),  k가 무한으로 커질 때는 O(무한))

 

---

실버 5

10989번 수 정렬하기3

10989번: 수 정렬하기 3

계수 정렬

import sys
N = int(sys.stdin.readline())
Nlist = [0] * 10001
for i in range(N):
    a = sys.stdin.readline()
    Nlist[int(a)] += 1

for j in range(1, 10001):
    if Nlist[j] >= 1:
        for k in range(Nlist[j]):
            print(j)

---

<정렬 정리>
버블 - 각 턴마다 두 대씩 비교해 swap하기
선택 - 맨 앞(뒤) 데이터와 범위 중의 최소(대)와  swap
삽입 - 2번째 데이터부터 시작-> 범위 내 알맞은 자리에 삽입
퀵 - 
병합 - 재귀함수이용/ 가장 작은 덩어리들부터 두개씩 한개로 병합하며 정렬(투포인터 이용)
기수 - 0-9를 각각 상징하는 10개의 큐를 이용해 1의자리->10의자리->100의자리...에 차례대로 통과시켜가며 정렬