指定された配列からn個の最小要素を元の順序で出力するアルゴリズム

k個の要素からなる配列が与えられたとき、プログラムはその中からn個（ここではk個）の最小要素を見つけ出し、配列に現れた元の順序のまま出力する必要があります。

例えば、入力が arr[] = {1, 2, 4, 3, 6, 7, 8} で k=3 の場合、配列の中から3つの最小要素を元の順序で、すなわち 1、次に 2、そして 3 の順に表示します。

入力 : arr[] = {1, 2, 4, 3, 6, 7, 8}, k=3
出力 : 1, 2, 3

アルゴリズム

この問題は、挿入ソートの考え方を応用することで効率よく解くことができます。基本的な発想は次のとおりです。

• 配列の先頭k個を「暫定の最小k要素」として保持します。
• k番目以降の要素を順に走査し、暫定のk要素の中の最大値より小さい要素が見つかったら、最大値を取り除いて新しい要素を末尾に追加します。
• この操作を配列の最後まで繰り返すことで、先頭k個が常に「それまでに見た要素の中で最小のk個」に保たれます。

手順を擬似コードで表すと以下のようになります。

START
ステップ1 → 変数を宣言する：int i, max, pos, j, k=4、および配列サイズ size
ステップ2 → i=k から i<size まで i++ でループ
    max = arr[k-1] とする
    pos = k-1 とする
    j=k-2 から j>=0 まで j-- でループ
        もし arr[j] > max ならば
            max = arr[j] とする
            pos = j とする
        終了
    終了
    もし max > arr[i] ならば
        j = pos とする
        j < k-1 の間ループ
            arr[j] = arr[j+1] とする
            j++ とする
        終了
        arr[k-1] = arr[i] とする
    終了
終了
ステップ3 → i=0 から i<k まで i++ でループ
    arr[i] を出力する
STOP

サンプルコード（C言語）

上記のアルゴリズムをC言語で実装した例が次のコードです。

#include <stdio.h>
int main() {
    int arr[] = {5,8,3,1,2,9};
    int i, max, pos, j, k=4;
    int size = sizeof(arr)/sizeof(arr[0]);
    // 挿入ソートの考え方を使い、k番目以降の要素を処理する
    for(i=k;i<size;i++){
        max = arr[k-1];
        pos = k-1;
        for(j=k-2;j>=0;j--) {
            if(arr[j]>max) {
                max = arr[j];
                pos = j;
            }
        }
        if ( max> arr[i] ) {
            j = pos;
            while( j < k-1 ) {
                arr[j] = arr[j+1];
                j++;
            }
            arr[k-1] = arr[i];
        }
    }
    // 最初のk個の要素を出力する
    for (i = 0; i < k; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、以下の出力が得られます。

5 3 1 2

この出力は、配列 {5, 8, 3, 1, 2, 9} の中から最小の4つの要素である 5, 3, 1, 2 が、元の配列での出現順序を保ったまま正しく出力されたことを示しています。

計算量について

外側のループは配列の残りの要素（size - k 個）を走査し、内側のループはk個の暫定要素の中から最大値を探すため、全体の時間計算量は O((size - k) × k) となります。配列の並び順を大きく変更せずに元の順序を維持できる点が、この手法の特徴です。