C++でソートされていない配列からk番目に小さい・大きい要素を求める方法

このチュートリアルでは、ソートされていない配列の中からk番目に小さい数値を見つけるプログラムをC++で作成します。基本的な考え方を理解すれば、k番目に大きい要素を求める場合にもすぐに応用できます。

解決のアプローチ

最もシンプルで分かりやすい方法は、配列を一度ソートしてしまい、目的の位置にある要素を取り出すことです。手順は以下の通りです。

• 配列とkの値を初期化する。
• sort関数を使って配列を昇順にソートする。
• インデックス k - 1 の位置にある値を返す(配列は0始まりのため)。

それでは、実際のコードを見てみましょう。

サンプルコード

#include <bits/stdc++.h>
using namespace std;

int findKthSmallestNumber(int arr[], int n, int k) {
    sort(arr, arr + n);
    return arr[k - 1];
}

int main() {
    int arr[] = { 3, 5, 23, 4, 15, 16, 87, 99 }, k = 5;
    cout << findKthSmallestNumber(arr, 7, k) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

16

配列を昇順に並べると { 3, 4, 5, 15, 16, 23, 87, 99 } となり、5番目に小さい要素は 16 であることが確認できます。

k番目に大きい要素を求めるには?

k番目に大きい要素が必要な場合も、同じくソート後の配列から取得できます。この場合は、末尾から数えて arr[n - k] を参照します。例えば、上記の配列で3番目に大きい要素を求めると arr[7 - 3] = arr[4] = 16 となります。

計算量について

この手法の時間計算量は、ソート処理が支配的となるため O(n log n) です。データサイズが小さい範囲であれば十分実用的ですが、より大きな配列や頻繁なクエリが想定される場合は、ヒープ(優先度付きキュー)やクイックセレクトを使った O(n) の手法も検討するとよいでしょう。

まとめ

本記事では、C++の sort 関数を活用して、ソートされていない配列からk番目に小さい・大きい要素を求める方法を解説しました。シンプルながら実務でも役立つ基本テクニックなので、ぜひマスターしておきましょう。チュートリアルについて質問がある場合は、コメント欄でお気軽にお尋ねください。