<Algorithm> Counting, Bucket, Radix, Merge Sort

1. Counting Sort(계수 정렬)

• 선형 정렬 알고리즘(키에 대한 추가적인 조건 및 정보를 가정)
• 키 값이 0~K-1 사이의 정수일 경우 적용가능
• 빈도수를 이용해서 정렬하는 알고리즘
• K의 크기와 N의 크기, 즉 키값의 크기와 배열의 길이가 비슷하면 최고 : O(N+K)
• K=N^3처럼 터무니 없이 차이가 나면 최악 : O(N^3)

Java Code

public class Counting {
	//A는 정수배열, 자릿수는 K개
	public static int[] sort(int[] A, int K) {
		int i , N = A.length;
		int[] C = new int[K], B = new int[N];
		
		for(i = 0; i < N; i++) C[A[i]]++; // 원소의 빈도수 합산
		for(i = 1; i < K; i++)	C[i] += C[i-1]; // i값이 저장될 위치 계산
		for(i = N-1; i >=0; i--) {
			B[--C[A[i]]] = A[i];
		}
		return B;
	}
	
	public static void main(String[] args) {
		 int[] A = {10,4,5,8,1,8,3,6}, B;
		 B = Counting.sort(A, 11);
		 for(int i = 0; i < B.length; i++) {
			 System.out.println(B[i] + "");
		 }
		 System.out.println();
	}
}
 

2. Bucket Sort(버킷 정렬)

• 계수 정렬에서 여러 개의 구간을 하나의 버킷으로 통합
  • 버킷의 크기가 1인경우가 계수정렬이다.
• 초기에 비어 있는 버킷을 준비
• 아래의 사진은 버킷의 크기를 10으로 하여, 10단위를 기준으로 배열을 나눴음
• 버킷 수가 2인 정렬 => Quick Sort

3.Radix Sort(기수 정렬)

• 자릿수를 기준으로 하는 정렬 ex) 세자리수면 3개의 기준이 존재
• MSD sort -> 높은 자리 우선 정렬
• LSD sort -> 낮은 자리 우선 정렬
• MSD는 큰 자리 기준으로 정렬하고, 다시 작은 자리 기준으로 정렬
• LSD는 작은자리부터 먼저 정렬하므로 효율적이지만 사용시 Stable Sorting 사용

4.Merge Sort(병합 정렬)

• 사전에 전제 배열을 절반 나눔
• 정렬된 두 개의 SubList를 병합
• 별도의 새로운 배열이 필요
• Top-down / Bottom-up의 두 가지 방식이 존재