C++で最大値・最小値を交互に並べるソートを実装する方法

問題の概要

整数のリスト nums が与えられたとき、以下のルールに従ってリストを並べ替えることを考えます。

• 1番目の要素は最大値
• 2番目の要素は最小値
• 3番目の要素は2番目に大きい値
• 4番目の要素は2番目に小さい値

以降も同様に、大きい値と小さい値を交互に配置していきます。

たとえば、入力が [6, 3, 10, 4] の場合、出力は [10, 3, 6, 4] となります。

解法のアプローチ

この問題は、配列をあらかじめ昇順にソートしておき、両端から交互に要素を取り出すことで解決できます。具体的な手順は以下の通りです。

1. 結果を格納するための配列 ret を定義します。
2. 配列 nums を昇順にソートします。
3. j を「nums のサイズ − 1」で初期化します(末尾=最大値側)。
4. i を 0 で初期化します(先頭=最小値側)。
5. i <= j の間、以下を繰り返します。
   • ret の末尾に nums[j](大きい側)を追加し、j を1減らします。
   • その後も i <= j が成り立つ場合は、ret の末尾に nums[i](小さい側)を追加し、i を1増やします。
6. 最後に ret を返します。

この方法では、ソート済みの配列の後ろから最大値を、前から最小値を交互に拾っていくため、要素数が奇数の場合でも中央の要素が正しく一度だけ処理されます。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    vector<int> solve(vector<int> & nums) {
        vector<int> ret;
        sort(nums.begin(), nums.end());
        int j = nums.size() - 1;
        int i = 0;
        while (i <= j) {
            ret.push_back(nums[j]);
            j--;
            if (i <= j) {
                ret.push_back(nums[i]);
                i++;
            }
        }
        return ret;
    }
};
main() {
    Solution ob;
    vector<int> v = {6,3,10,4};
    print_vector(ob.solve(v));
}

入力

{6,3,10,4}

出力

10, 3, 6, 4

計算量について

このアルゴリズムの時間計算量は、ソート処理が支配的となるため O(n log n) です。ソート後の交互配置は配列を一度走査するだけなので O(n) で済みます。また、結果用の配列 ret が必要なため、空間計算量は O(n) となります。元の配列を破壊してもよい場合は、インプレースで両端の要素を入れ替えながら処理することで、追加メモリを削減することも可能です。