カウントソート

16403 ワード

データ構造アルゴリズム(C) テキストリンク

度数ソートフィーチャー

キー値を比較する必要がない

を選択、挿入、高速、マージ、hipでソートする.

サイズ、数個で、位置を変える必要はありません

すべてのデータに1回アクセスするだけで効率的な

を得ることができます.

範囲条件がある場合、速度は非常に速い

である.
度数ソート手順
1.度数分布表の作成

説明:
配列aは値を入力する必要があり、配列fは導関数分布テーブルを作成する必要があり、fはカウントする必要があり、すべての遷移値を0に初期化する.aをスキャンして値を検索すると、fのインデックスの値1にインクリメントされます.

コード#コード#

/* 개수 0으로 초기화 */
for (i = 0; i <= max; i++) f[i] = 0;
    
/* 도수 분포표 */
for (i = 0; i < n; i++) f[a[i]]++;

図

2.累計導関数分布テーブルの作成

説明:
配列aの値の範囲が0以下である場合(図ではmaxを10と仮定する)、配列fはいくつかの累積値を生成する.これにより、配列aの値が何番目にあるかがわかる.

コード#コード#

/* 누적 도수 분포표 */
for (i = 1; i <= max; i++) f[i] += f[i - 1];

図

3.目標シナリオの作成

説明:
配列aの値が何番目にあるかは既に分かっているので,並べ替えはほぼ完了していると考えられる.
配列aの各ステップ値は積算導関数分布テーブルfと照合し,並べ替え作業を行う.aと同じサイズの作業用途配列bが必要である.また、下図の例とa配列の3は重複する値がある可能性があるため、末尾から最初の要素にスキャンして順序が逆転しないようにします.(最初から累積導関数分布をスキャンしていたので)

コード#コード#
a[i]はf[a[i]の2番目の数字であることを示すため、f[a[i]の2番目の値であるb配列のインデックスを減らす必要がある.(f配列の値も1減少したため削除される)
n−1からスキャンを開始して順序の逆転を防止する(最初から累積導関数分布をスキャンするため)

/* 목적 배열 만들기 */
for (i = n - 1; i >= 0; i--) b[--f[a[i]]] = a[i];

図

4.アレイのコピー

説明:
ターゲット配列bをaにコピーして並べ替えを完了する

コード#コード#

 /* 배열 복사 */
 for (i = 0; i < n; i++) a[i] = b[i];

完全なコード

#pragma warning (disable:4996)
#include <stdio.h>
#include <stdlib.h>

/* 도수 정렬 함수(배열의 요소값 0 이상 max 이하)*/
void fsort(int a[], int n, int max) {
    int i;
    int* f = (int*)calloc(max + 1, sizeof(int)); // 누적 도수
    int* b = (int*)calloc(n, sizeof(int)); // 목적 배열 만들기
     
     /* 개수 0으로 초기화 */
    for (i = 0; i <= max; i++) f[i] = 0;

    /* 도수 분포표 */
    for (i = 0; i < n; i++) f[a[i]]++; 

    /* 누적 도수 분포표 */
    for (i = 1; i <= max; i++) f[i] += f[i - 1]; 

    /* 목적 배열 만들기 */
    /* a[i]가 f[a[i]]번째 숫자임을 뜻함, 따라서 b배열의 인덱스 하나 줄여야 f[a[i]]번째 값임 */
    /* 끝에서 부터 스캔하여 순서 반대로 바뀌는 것을 방지(누적 도수 분포포를 처음부터 스캔했기 때문에)*/
    for (i = n - 1; i >= 0; i--) b[--f[a[i]]] = a[i]; 

    /* 배열 복사 */
    for (i = 0; i < n; i++) a[i] = b[i];

    free(f);
    free(b);
}

int main() {
    int nx;
    int* x = NULL;
    int max = 100;

    scanf("%d", &nx);
    if ((x = (int*)calloc(nx, sizeof(int))) == NULL)
        return -1;

    for (int i = 0; i < nx; i++)
        scanf("%d", &x[i]);

    fsort(x, nx, max); // 도수 정렬 함수 호출

    for (int i = 0; i < nx; i++)
        printf("%d ", x[i]);

    free(x);
    return 0;
}