C言語で配列の重複を削除し、ソート済みの一意な要素を出力する方法

整数型の要素を持つ配列が与えられたとき、重複する値を取り除き、一意な（distinct）要素だけをソートして出力するのが本記事の目的です。

例として、次のような整数値を格納した配列を考えてみましょう。

4, 6, 5, 3, 4, 5, 2, 8, 7, 0

この配列を単純にソートすると「0, 2, 3, 4, 4, 5, 5, 6, 7, 8」となりますが、この結果にはまだ重複値である 4 と 5 が含まれています。これらを削除し、最終的な出力結果は次のようになります。

0, 2, 3, 4, 5, 6, 7, 8

入力と出力の例

Input: array[] = {4, 6, 5, 3, 4, 5, 2, 8, 7, 0}
Output: 0 2 3 4 5 6 7 8

処理の流れ

期待する結果を得るために、以下の手順で処理を行います。

• 配列内の一意な要素だけを抽出し、別の配列 array1 に格納します。
• array1 を昇順にソートします。
• array1 の値を順に出力します。

アルゴリズム

START
    STEP 1: 変数 i, j, array1[size], temp, count = 0 を宣言
    STEP 2: i = 0 から i < size の間ループ
        j = i+1 から j < size の間ループ
            IF array[i] == array[j] ならば
                break（重複が見つかったので抜ける）
            END IF
        END FOR
        IF j == size ならば（重複が存在しなかった場合）
            array1[count++] に array[i] を代入
        END IF
    END FOR
    STEP 3: i = 0 から i < count-1 の間ループ（選択ソート）
        j = i+1 から j < count の間ループ
            IF array1[i] > array1[j] ならば
                array1[i] と array1[j] を交換
            END IF
        END FOR
    END FOR
    STEP 4: array1 を出力
STOP

C言語による実装例

#include <stdio.h>
/* 配列の一意な要素を出力する関数 */
void printDistinctElements(int array[], int size) {
    int i, j, array1[size], temp, count = 0;
    for(i = 0; i < size; i++) {
        for(j = i+1; j < size; j++) {
            if(array[i] == array[j]) {
                /* 重複する要素が見つかった */
                break;
            }
        }
        /* j が size と等しい場合、配列全体を走査しても
           array[i] の重複が見つからなかったことを意味する */
        if(j == size) {
            array1[count++] = array[i];
        }
    }
    /* 一意な値のみが格納された array1 をソート */
    for ( i = 0; i < count-1; i++) {
        for ( j = i+1; j < count; j++) {
            if(array1[i]>array1[j]) {
                temp = array1[i];
                array1[i] = array1[j];
                array1[j] = temp;
            }
        }
    }
    for ( i = 0; i < count; ++i) {
        printf("%d ", array1[i]);
    }
}
int main() {
    int array[] = {4, 6, 5, 3, 4, 5, 2, 8, 7, 0};
    int n = sizeof(array)/sizeof(array[0]);
    printDistinctElements(array, n);
    return 0;
}

実行結果

上記のプログラムを実行すると、以下の出力が得られます。

0 2 3 4 5 6 7 8

補足：計算量について

この実装では、重複チェックに二重ループ（O(n²)）、ソートにも選択ソート（O(n²)）を使用しているため、全体の計算量は O(n²) となります。小規模な配列では問題ありませんが、大規模なデータを扱う場合は、qsort() 関数で先にソートしてから隣接する重複を除去する方法や、ハッシュテーブルを活用する方法の方が効率的です。