[Algorithm] 정렬 Sort - Counting sort, Radix sort

Comparison sort

• 데이터들간의 상대적 크기 관계만을 이용해 정렬하는 알고리즘
• 데이터들간의 크기 관계만 정의되어 있으면 어떤 데이터에든 적용 가능 (문자열, 알파벳, 사용자 정의 객체 등)
• bubble sort, insertion sort, merge sort, quick sort, heap sort 등

Non-Comparision sort

• 정렬할 데이터에 대한 사전지식을 이용해 정렬하는 알고리즘
• Bucket sort, Radix sort 등

---

Non-Comparision sort

Counting sort

• n개의 정수를 정렬하라. 단, 모든 정수는 0에서 k사이의 정수이다. (n=8이고, k=5인 경우)
  • 크기가 8인 배열 A에 0부터 5까지의 숫자가 랜덤으로 배열되어있음
  • 배열 C는 각 숫자의 갯수를 요소로 가지는 카운터 배열
  • 하지만 이 예시는 다수의 칼럼을 포함하는 레코드를 표현하기에 적절하지 않음

int A[n]; //정렬할 데이터(0..k)
int C[k] = {0, }; //k개의 카운터, 0으로 초기화
for (int i = 1; i <= n; i++)
	C[A[i]]++; //A[i]값의 카운터를 1 증가
for (int s = 1, i = 0; i <= k; i++) {
	for (int j = 0; j < C[i]; j++) {
		A[s++] = i;
	}
}

 

• (a) : 배열 A의 데이터를 카운트하여 배열 C에 저장
• (b) : 배열 C를 스캔하면서 누적합을 구함 (인덱스 2 : 2보다 작거나 같은 값들의 갯수)
• (c) : 누적합으로 값이 변경된 배열 C를 이용하여, 배열 B를 채움
  • 3보다 작거나 같은 값이 7개 있으므로 3은 7번 자리에 들어갈 수 있음, 만약 또 3이 나오면 6번 자리에 들어가야함
• (d) : 0보다 작거나 같은 수가 2개이므로 0을 2번 자리에 넣고 0번 인덱스의 값을 1 감소시킴
• (e) : 위와 같은 방법으로 배열 A의 값을 뒤에서부터 꺼내가면서 배열 C를 이용해서 배열 B를 채움

Counting-Sort(A, B, k)
	for i <- 0 to k //배열 C를 0으로 초기화하는 반복문
		do C[i] <- 0
	for j <- 1 to length[A] //배열 A의 데이터를 카운팅하여 배열 C에 저장
		do C[A[j]] <- C[A[j]] + 1
	=> C[i] now contains the number of elements equal to i.
	for i <- 1 to k //누적합을 구하는 반복문 
		do C[i] <- C[i] + C[i-1] //C[i-1]은 이전까지의 누적합
	=> C[i] now contains the number of elements less than or equal to i.
	for j <- length[A] downto 1 //배열 A를 역으로 탐색하는 반복문
		do B[C[A[j]]] <- A[j] //배열 A의 데이터를 배열 B에 저장
			C[A[j]] <- C[A[j]] - 1 //카운터 값 1 감소

Radix sort

• 길이가 d인 데이터 n개를 정렬하는 알고리즘
• 3자리 정수 7개를 정렬하시오 (d=3, n=7인 경우)
  • 가장 낮은 자리수부터 정렬 (1의 자리 -> 10의 자리 -> 100의 자리)
  • Stable sort : 동일한 값의 경우 입력에서 들어온 순서가 출력될 때도 유지되야하는 알고리즘
  • 매 단계에서 사용하는 알고리즘은 반드시 stable sort여야 함 (두번째에서 세번째 단계로 넘어갈 때 같은 2여도 329가 720보다 먼저 나오면 안됨)

Radix-Sort(A, d) //A는 n개의 데이터가 저장된 배열, d는 각 데이터의 길이
	for i <- 1 to d //d번동안 반복문 실행
		do use a stable sort to sort array A on digit i //stable sort를 적용하여 정렬