Counting Sort

http://bowbowbow.tistory.com/8#counting-sort

계수 정렬

  • 각각의 원소가 몇 개 존재하는지 counting 한 후 개수를 센 배열을 통해서 정렬된 배열을 뽑아내는 방법
  • 배열에 index에 해당하는 값 counting하는거라 데이터는 무조건 양의 정수, O~K 범위 일때, K가 너무 크면 안되기 때문에 데이터 제한이 존재. 가령 0, 2, 0, 200 만 해도 index 200까지 있어야하니까 메모리낭비.
  • counting sort 는 아래 예시처럼 정렬 숫자가 작은 범위 안에 있을때 주로 사용. O(n+k)으로 범위가 작을 경우, 퀵소트보다도 유리
  • ori array : 5, 5, 3, 4, 5, 1, 0, 4, 1 ,3 0, 2, 4, 2, 3, 0 이면
  • counting array의 0~5 index 값은 3, 2, 2, 3, 3, 3 이다
counting array
num 0 1 2 3 4 5
cnt 3 2 2 3 3 3
  • sorted array : 0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5 로 만드는 방법은
counting array
num 0 1 2 3 4 5
cnt 3 2 2 3 3 3
accumulated 3 5(3+2) 7(5+2) 10(7+3) 13(10+3) 16(13+3)
  • 등장 횟수를 위처럼 누적 시킨다.
  • 정렬할 배열을 뒤에서 앞으로 순회하면서 sorted array에 넣어줌. 위 과정에서 구한 누적 합이 ori array의 숫자가 sorted array의 어디에 위치해야 할지 정확하게 알려줌
  • accumulated가 가리키는 sorted array의 index에 해당 숫자를 위치시키고, 해당 수 accumulated 값을 하나씩 빼준다
  •  http://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html
  • 위 애니메이션 처럼 반복하면 정렬 완료
  • 위처럼 뒤에서부터 순환하며 누적합 하나씩 빼주면서 배열하는건,이 순서로 해주어야 stable sort가 되기 때문.
  • stable sort란 , 굳이 소팅 될 필요가 없는 값들(같은 값)은 이전의 순서를 유지해 주는 것. radix sort에서 stable sort가 보장 되어야 하기 때문에 중요한 개념
#include <iostream>
using namespace std;
#define MAX_SIZE 1000
#define MAX_NUM 10000

int ori_arr[MAX_SIZE + 1];
int sorted_arr[MAX_SIZE + 1];
int cnt_arr[MAX_NUM + 1];
int cnt_sum[MAX_NUM + 1];//누적합 저장

int main(){
    int N;//수열 길이   
    cin >> N;

    int mymax = 0;

    for (int i = 1; i <= N; ++i){
        cin >> ori_arr[i]; //값은 MAX_NUM이하로 들어와야 성립
        cnt_arr[ori_arr[i]]++; //등장 횟수 세기
        if (ori_arr[i] > mymax) mymax = ori_arr[i];
    }

    //누적합
    cnt_sum[0] = cnt_arr[0];
    /*인풋 받을때 mymax로 재설정 해도 좋을듯. 실제 들어오는 젤 큰거로*/
    for (int i = 1; i <= mymax; ++i)
        cnt_sum[i] = cnt_sum[i - 1] + cnt_arr[i];

    //뒤에서부터 ori_arr 순회
    for (int i = N; i >= 1; --i){
        sorted_arr[cnt_sum[ori_arr[i]]] = ori_arr[i];
        cnt_sum[ori_arr[i]]--;
    }

    for (int i = 1; i <= N; ++i)
        cout << sorted_arr[i];


    return 0;
}

 

Musicals, Travel, Photo, Coding