[알고리즘] 계수 정렬(Counting Sort)

 

 

 

과정

 

1. 배열을 돌면서 해당 숫자가 몇 개인지 count
2. temp 배열을 누적으로 순차적으로 sum
3. 끝에서부터 정해진 위치에 넣을 수 있도록 한다.

https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html

Counting Sort

→ 이 애니메이션을 보면 쉽게 이해된다!! 굿굿

 

 

코드(c++)

#include <iostream>
using namespace std;

void counting_sort(int arr[])
{
    int temp[1000];
    int count[1000];
    int sorted[1000];

    memset(temp, 0, sizeof(temp));

    //더해주기
    for (int i = 0; i < 10; i++) temp[arr[i]]++;
    count[0] = temp[0];

    //누적으로 더해주기
    for (int i = 1; i <= 23; i++) count[i] = count[i - 1] + temp[i];

    //제일 끝에서 부터 삽입
    for (int i = 9; i >= 0; i--){
        sorted[count[arr[i]]-1] = arr[i];
        count[arr[i]]--;
    }
    
    //정렬된 행렬
    for (int i = 0; i < 10; i++) cout << sorted[i] << " ";
    cout << endl;
}

int main()
{
    int arr[1000] = { 10,23,1,1,23,23,4,5,6,7 };
    counting_sort(arr);
    return 0;
}

 

장점

 

O(n)

 

단점

 

메모리 낭비가 너무 심함

• 임시 배열
• count 배열
• count 누적합 배열
• 정렬된 배열

➿ 배열에 포함된 숫자 중 큰 수가 존재하면 메모리 낭비가 더 심함

 

언제 사용하면 좋을까..?

 

정렬하는 숫자가 특정 범위 내에 있을 때

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!

 

 

 

 

 

 

참고: https://hsho.tistory.com/28