9 선형 시간 정렬

9 선형 시간 정렬
 
9.2 계수 정렬
의사 코드:

COUNTING-SORT(A, B, k)
 1  for i ← 0 to k
 2     do C[i] ← 0
 3  for j ← 1 to length[A]
 4     do C[A[j]] ← C[A[j]] + 1
 5  ▹ C[i] now contains the number of elements equal to i.
 6  for i ← 1 to k
 7     do C[i] ← C[i] + C[i - 1]
 8  ▹ C[i] now contains the number of elements less than or equal to i.
 9  for j ← length[A] downto 1
10     do B[C[A[j]]] ← A[j]
11        C[A[j]] ← C[A[j]] - 1

 

 
Java 코드:

public class CountingSort {

	public static int[] countingSort(int[] A, int k) {
		int[] B = new int[A.length];
		int[] C = new int[k];

		for (int i = 0; i < k; i++)
			C[i] = 0;
		for (int i = 0; i < A.length; i++)
			C[A[i]] += 1;
		for (int i = 1; i < k; i++)
			C[i] += C[i - 1];
		for (int i = A.length - 1; i >= 0; i--) {
			B[C[A[i]] - 1] = A[i];
			C[A[i]] -= 1;
		}
		return B;
	}

	public static void main(String[] args) {
		int[] A = { 2, 5, 3, 0, 2, 3, 0, 3 };
		int[] B = countingSort(A, 6);
		for (int b : B) {
			System.out.print(b + " ");
		}
		System.out.println();
	}

}

 

 
출력: 0 0 0 2 3 3 5
 
code 후 감 은 '비교 정렬' (정렬 삽입, 정렬, 빠 른 정렬, 모두 '비교' 배열 의 값 이 므 로 모두 '비교 정렬') 과 다 릅 니 다. 계산 정렬 의 속도 가 매우 빠 르 고 '안정 적 인 정렬' 입 니 다.프로그램 자체 가 매우 깨끗 해서 모두 4 개의 순환 에 불과 하 다.마지막 순환 은 조금 어렵 습 니 다. 자바 프로그램의 배열 아래 표 시 된 시작 값 과 위조 코드 의 시작 값 은 같 지 않 습 니 다.알고리즘 서론 1 판 과 2 판 은 이 위조 코드 에 있 는 배열 아래 표 시 된 시작 값 자체 가 다르다.다행히 코드 자체 가 어렵 지 않 아 큰 어려움 은 없 을 것 이다.자바 코드 를 한 단계 추적 하여 실행 하고 A, B, C 배열 의 값 변 화 를 관찰 하 는 것 을 권장 합 니 다. A, B, C 배열 의 값 과 의 그림 이 일치 하 는 것 을 알 수 있 습 니 다.이렇게 하면 더욱 쉽게 이 알고리즘 을 이해 할 수 있다.
 
 
9.3 기수 정렬
의사 코드:

RADIX-SORT(A, d)
1  for i ← 1 to d
2     do use a stable sort to sort array A on digit i

 

 
Java 코드:

public class RadixSort {

	private static int[] countingSort(int[] A, int d) {
		int[] B = new int[A.length];
		int[] C = new int[10];
		for (int i = 0; i < 10; i++)
			C[i] = 0;
		for (int i = 0; i < A.length; i++)
			C[A[i] % ((int) Math.pow(10, d + 1)) / ((int) Math.pow(10, d))] += 1;
		for (int i = 1; i < 10; i++)
			C[i] += C[i - 1];
		for (int i = A.length - 1; i >= 0; i--) {
			B[C[A[i] % ((int) Math.pow(10, d + 1)) / ((int) Math.pow(10, d))] - 1] = A[i];
			C[A[i] % ((int) Math.pow(10, d + 1)) / ((int) Math.pow(10, d))] -= 1;
		}
		return B;
	}

	public static int[] radixSort(int[] A, int d) {
		int[] B = new int[A.length];
		for (int i = 0; i < A.length; i++)
			B[i] = A[i];
		for (int i = 0; i < d; i++) {
			B = countingSort(B, i);
		}
		return B;
	}

	public static void main(String[] args) {
		int[] A = { 12, 25, 13, 30, 32, 43, 20, 3 };
		int[] B = radixSort(A, 2);
		for (int b : B) {
			System.out.print(b + " ");
		}
		System.out.println();

	}

}

 

 
출력: 3 12 13 20 25 30 32 43
 
code 후 감 위조 코드 가 짧 고 자바 코드 가 길 어 요.두 번 째 줄 의 위조 코드 는 수조 A 의 i 위 를 키 로 하고 안정 적 인 정렬 으로 배열 하기 때문이다.지금까지 에서 소개 한 안정 적 인 순 서 는 앞의 절의 계수 만 정렬 되 었 고 그 절의 계수 순 서 는 여기에 직접 사용 할 수 없 었 다.어 쩔 수 없 이 앞의 절의 계산 순 서 를 고 쳐 써 야 한다.주의해 야 할 것 은 이 절의 계수 정렬 Public static int [] contingSort (int [] A, int d) 와 이전 절의 인자 (int [] A, int d) 는 같 지만 의 미 는 완전히 다르다 는 것 이다.이전 절의 계수 정렬 에서 두 번 째 매개 변수 (int k) 는 배열 A 의 가능 한 값 을 나타 내 는 개수 입 니 다.지난 절 에서 의 예 는 배열 A 가 0 에서 5 사이 이기 때문에 k 는 6 이다.이 절 은 10 진수 로 배열 되 어 있 는 것 을 고려 하여 프로그램 에서 10 으로 정 하고 매개 변수 에 의 해 도입 되 지 않 으 며 (int d) 는 정렬 된 키 가 있 는 자릿수 입 니 다. 테스트 프로그램 에서 d 는 0 에서 1 까지 순환 합 니 다.
 
 
9.4 통 정렬
의사 코드:

BUCKET-SORT(A)
1  n ← length[A]
2  for i ← 1 to n
3     do insert A[i] into list B[⌊n A[i]⌋]
4  for i ← 0 to n - 1
5     do sort list B[i] with insertion sort
6  concatenate the lists B[0], B[1], . . ., B[n - 1] together in order

 

 
Java 코드:

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

public class BucketSort {
	public static <T> void insertionSort(T[] t, Comparator<? super T> comparator) {
		for (int j = 1; j < t.length; j++) {
			T key = t[j];
			int i = j - 1;
			while (i > -1 && comparator.compare(t[i], key) > 0) {
				t[i + 1] = t[i];
				i--;
			}
			t[i + 1] = key;
		}
	}

	public static Double[] bucketSort(Double[] A) {
		List<Double>[] B = new List[10];

		for (int i = 0; i < B.length; i++)
			B[i] = new LinkedList<Double>();
		for (Double d : A)
			B[(int) (d * 10)].add(d);

		Double[][] BB = new Double[10][];
		List<Double> BBB = new LinkedList<Double>();
		for (int i = 0; i < B.length; i++) {
			BB[i] = B[i].toArray(new Double[0]);
			insertionSort(BB[i], new Comparator<Double>() {
				public int compare(Double o1, Double o2) {
					return (int) (Math.signum(o1 - o2));
				}
			});
			for (Double d : BB[i])
				BBB.add(d);
		}
		return BBB.toArray(new Double[0]);
	}

	public static void main(String[] args) {
		Double[] doubles = new Double[] { 0.78, 0.17, 0.39, 0.26, 0.72, 0.94,
				0.21, 0.12, 0.23, 0.68 };
		doubles = bucketSort(doubles);
		for (Double d : doubles)
			System.out.print(d + " ");
		System.out.println();
	}

}

 

 
출력: 0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94
 
code 후 감 은 이전 절 과 마찬가지 로 의사 코드 가 짧 고 자바 코드 가 길 습 니 다.그 이 유 는 통 정렬 의 첫 번 째 단 계 는 각 대기 요 소 를 통 에 담 는 것 이 고 두 번 째 단 계 는 각 통 에 정렬 하 는 것 이다.정렬 insertionSort 를 삽입 합 니 다. 1.1.1 절 에 소 개 했 습 니 다. 여기 서 1.1.1 프로그램 을 그대로 복사 해서 사용 합 니 다.정렬 을 잊 어 버 린 사람 에 게 다시 복습 하 게 하 세 요.
제9 장 은 이렇게 끝나 고 프로그램 이 비교적 간단 하 다. 쌓 기 정렬 과 빠 른 정렬 에 비해 계수 정렬 이 든 기수 정렬 이 든 통 정렬 이 든 위조 코드 를 이해 하 는 것 은 어렵 지 않다.그러나 앞의 지식 을 사 용 했 기 때문에 온고지신 하 다. 앞의 삽입 순 서 를 복습 하 는 것 이 필요 하 다.
전체적으로 보면 삽입 정렬 등 이 가장 느 리 고 일반성 을 고려 하면 쌓 기 정렬 과 빠 른 정렬 이 모두 좋 은 선택 이다.정수 일 경우 계수 나 기수 로 정렬 하고 부동 소수점 일 경우 통 순 서 를 선택 할 수 있 습 니 다.