개발 공부 - [정렬] sorting in linear time

선형시간 정렬 알고리즘

- Counting sort

: n개의 정수를 정렬하라. 단 모든 정수는 0에서 k사이의 정수이다.

: 예 : n명의 학생들의 시험점수를 정렬하라.

    단 모든 점수는 100이하의 양의 정수이다.

- k=5인 경우의 예

: 길이 k인 배열에 각 정수의 개수를 count 한다.

ㄴ counter 용 배열을 만들어서 거기다가 count 하는 것임 

C[0] = 2

C[1] = 1

... C[5] = 1

이런 식으로!

수도 코드

int A[n];

int C[k] = {0, };

for(int i = 1; i<n; i++){

    C[A[i]]++;

}

for(int s = 1, i =0; i<=k; i++) {

    for(int j=0; j<C[i]; j++){

        A[s++] = j;

    }

}

: 이것은 대부분 경우 정렬 Key값이 레코드의 일부분이기 때문에...

Counting-Sort(A, B, k)

for i <- 0 to k

    do C[i] <- 0

for j <- 1 to length[A]

    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] now contains the number of elements less than equal to i

for j <- length[A] downto 1

    do B[C[A[j]]] <- A[j]

        C[A[j]] <- C[A[j]] -1

시간복잡도

- O(n+k) 또는 O(n) if k=0(n).

- k 가 클 경우에는 비실용적이다. (일반적으로 k가 작을 때 사용)

- stable 정렬 알고리즘

: 입력에 동일한 값이 있을 때 입력에 먼저 나오는 값이 출력에서도 먼저 나온다.

: counting 정렬은 stable 하다.