データ構造とアルゴリズム Vol.8

Vol.8: Counting Sort

Counting Sortの原理を理解し、これをC言語で実現することができます。

Counting Sortとは？

👌 Counting Sortは大きさを基準にデータ数を数える整列アルゴリズムです。 各データをすぐにサイズを基準に分類するため、O(N)の時間複雑度を持ちます。

Counting Sort実現

例）実行するコードの例

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX_VALUE 10001 //Counting Sortは、データサイズを基準として整列するため、配列のインデックスを超える元素が入力されると整列できません。

int n, m;
int a[MAX_VALUE] //メモリが非常に消耗しているため、大きさの制限が必ず必要です。

int main(){
    scanf("%d", &n);
    for (int i =0; i < n; i++) { scanf("%d", &m); a[m]++; }
    for (int i =0; i < MAX_VALUE; i++) {
        while (a[i] != 0) { printf("%d", i); a[i]--; }
    }
    system("pause");
}

🤔 結果は？
input1-> 5
input2-> 7 8 9 10 392
result-> 7 8 9 10 392

まとめ

📌Counting Sortは、時間複雑度がO(N)の整列アルゴリズムです。
📌Counting Sortは、データのサイズが限定的な時に使用することができます。

📚参考講義：コンピューター工学専攻必須オールインワンパッケージOnline
👆 上記の講義はCとC++を言語を前提に説明しています。