Counting Sort 계수 정렬 10989 백준 수정렬하기 3

Counting Sort 계수 정렬 !

시간 복잡도 O(n + k) 만큼 걸리고 공간 복잡도 O(k) 만큼 걸리는 정렬 알고리즘

Radix Sort 기수 정렬보다 공간 복잡도가 적게 드는 장점이 있는 정렬 알고리즘이다.

Radix Sort 에서는 Linked list 와 Dynamic Array가 필요하기 때문에 계수 정렬에 비해 

공간이 절약된다. 기수 정렬에서 정렬될 Index를 계산 하는데 앞서 Counting number 를 누적해 나간다. 

누적하기 때문에 다른 배열을 사용하지 않아도 되는 장점이 있다. 

Unsorted Array : 7, 2, 3, 5

Stored Array : 0, 0, 1, 1, 0, 1, 0, 1

1. 정렬되지 않은 배열의 숫자 범위만큼 Stored Array 를 할당하고 숫자의 갯수를 저장한다.

2. 저장된 숫자의 갯수들을 배열의 시작부터 더해나간다 

Stored Array : 0, 0, 1, 2, 2, 3, 3, 4

누적된 숫자는 인덱스가 숫자로 기록될 배열의 인덱스이다.

3번째의 값이 1이니까 배열의 1번째 자리에 0, 1, 2 숫자에서 3번째인 2를 집어 넣는다.

그 다음 4번째의 값이 전의 값보다 증가했으니 2의 인덱스 자리에 4번째인 3을 집어넣는다. 

즉 누적시키는 숫자로인해 저장될 숫자의 위치를 이전에 정렬될 작은 숫자위치 다음에 넣는 방식이다.

출처 : 위키피디아 

수 정렬하기 3 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
5 초	8 MB	7155	1600	1183	24.518%

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 

10
5
2
3
1
4
2
3
5
1
7

예제 출력 

1
1
2
2
3
3
4
5
5
7

시간 제한이 5초이며 메모리가 8mb이므로 

10,000,000 갯수의 입력 값을 정렬해야 하기 때문에 

입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초 당 반복문 수행 횟수가 1억(108${10}^8$)을 넘어가면 시간 제한을 초과할 가능성이 있다.1

위의 알고리즘 문제해결전략에서 참고한 수행속도 예측에 따르면,

1천만의 입력 갯수를 정렬할때 O(nlogn) 는 5초 약 5억의 반복횟수를 넘을 것이다. 

또한 그나마 빠른 radix sort를 사용한다면 O(nk) 1천만 X 1만이기 때문에 1000억의 반복횟수를 넘는다.

Array Sorting Algorithms

Algorithm	Time Complexity			Space Complexity
	Best	Average	Worst	Worst
Quicksort	Ω(n log(n))	Θ(n log(n))	O(n^2)	O(log(n))
Mergesort	Ω(n log(n))	Θ(n log(n))	O(n log(n))	O(n)
Timsort	Ω(n)	Θ(n log(n))	O(n log(n))	O(n)
Heapsort	Ω(n log(n))	Θ(n log(n))	O(n log(n))	O(1)
Bubble Sort	Ω(n)	Θ(n^2)	O(n^2)	O(1)
Insertion Sort	Ω(n)	Θ(n^2)	O(n^2)	O(1)
Selection Sort	Ω(n^2)	Θ(n^2)	O(n^2)	O(1)
Tree Sort	Ω(n log(n))	Θ(n log(n))	O(n^2)	O(n)
Shell Sort	Ω(n log(n))	Θ(n(log(n))^2)	O(n(log(n))^2)	O(1)
Bucket Sort	Ω(n+k)	Θ(n+k)	O(n^2)	O(n)
Radix Sort	Ω(nk)	Θ(nk)	O(nk)	O(n+k)
Counting Sort	Ω(n+k)	Θ(n+k)	O(n+k)	O(k)
Cubesort	Ω(n)	Θ(n log(n))	O(n log(n))	O(n)

Radix와 Counting Sort의 최악의 경우의 시간과 공간의 복잡도가 입력 값의 개수와 

숫자의 범위가 늘어나면 배로 커질 수 밖에 없다.

 

소스 코드

#include <stdio.h>

int main(){

    int n=0,counts[10001]={0,},input=0;

    //1 부터 10000 까지의 숫자 종류를 저장하기 위해 배열을 할당

    scanf("%d",&n);

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

        scanf("%d",&input);

        counts[input]++;

        //숫자에 인덱스를 위해 숫자의 갯수를 세어 저장

    }

    for(int i=1; i<=10000; i++)

        counts[i] = counts[i] + counts[i-1];

        //정렬될 숫자의 인덱스를 위해 누적을 시킴

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

        int index = counts[i]-counts[i-1];

        if(i==1){

            index = counts[i];

            //첫 숫자는 전의 숫자와 비교할 필요가 없음

        }

        while(index--){

            printf("%d\n",i);

            //전 숫자와 차이만큼 숫자 출력

        }

    }

    return 0;

}