C++の組み込みsort関数を使って正負の数値を並べ替える方法

正の数と負の数が混在する整数型配列 arr[](任意のサイズ)が与えられます。この記事では、C++ STLの組み込みsort関数を使用する方法と、再帰的なコーディング技法を使用する方法の2通りで配列を並べ替え、その結果を出力する方法を解説します。

入出力シナリオの例

入力 − int arr[] = {4, 2, -1, -1, 6, -3, 0}

出力 − 組み込みsort関数を使用した正負の数値の並べ替え結果: -3 -1 -1 0 2 4 6

説明 − 正と負の要素を含むサイズ7の整数配列が与えられています。すべての負の要素が正の要素より前に来るように配列を並べ替えると、最終結果は「-3 -1 -1 0 2 4 6」となります。

入力 − int arr[] = {-9, -10, 2, 3, 10, 5, 8, 4}

出力 − 組み込みsort関数を使用した正負の数値の並べ替え結果: -10 -9 2 3 4 5 8 10

説明 − 正と負の要素を含むサイズ8の整数配列が与えられています。すべての負の要素が正の要素より前に来るように配列を並べ替えると、最終結果は「-10 -9 2 3 4 5 8 10」となります。

プログラムで使用するアプローチ

sort()関数を使用する方法

• 整数型要素の配列を入力として受け取り、配列のサイズを計算します。
• データを関数 Rearrangement(int arr[], int size) に渡します。
• 関数の内部では、配列とそのサイズを引数としてC++ STLのsort関数を呼び出し、ソート済みの配列を取得します。
• 結果を出力します。

再帰を使用する方法

• 整数型要素の配列を入力として受け取り、配列のサイズを計算します。
• 一時変数(ここでは temp とします)を宣言します。
• i が配列のサイズ未満である間、forループを回します。ループ内で arr[i] が 0 未満であれば、temp を 1 増やします。
• 配列、0、size - 1 を引数として Rearrangement(arr, 0, (size - 1)) を呼び出します。
• 配列、temp、size - 1 を引数として Rotate 関数を呼び出します。

関数 Rearrangement(int arr[], int first, int last) の内部処理は以下の通りです。

• first と last が等しい場合は処理を終了して戻ります。
• 関数 Rearrangement() を再帰的に呼び出し、配列、first + 1、last を引数として渡します。
• arr[first] が 0 以上であれば、Rotate(arr, (first + 1), last) と Rotate(arr, first, last) を呼び出します。

関数 Rotate(int arr[], int first, int last) の内部処理は以下の通りです。

• first が last より小さい間、whileループを継続します。ループ内では、整数変数 temp に arr[first] を格納し、arr[first] に arr[last] を、arr[last] に temp を代入します。その後、first を 1 増やし、last を 1 減らします。

最後に、並べ替え後の結果を出力します。

1. sort()関数を使用する方法

サンプルコード

#include <bits/stdc++.h>
using namespace std;
//sort()関数を使用
void Rearrangement(int arr[], int size){
    sort(arr, arr + size);
}
int main(){
    int arr[] = {4, 2, -1, -1, 6, -3, 0};
    int size = sizeof(arr)/sizeof(arr[0]);
    //配列を並べ替える関数を呼び出す
    Rearrangement(arr, size);
    //並べ替え後の配列を出力
    cout<<"組み込みsort関数を使用した正負の数値の並べ替え結果: ";
    for(int i = 0; i < size; i++){
        cout<< arr[i] << " ";
    }
    return 0;
}

出力

上記のコードを実行すると、以下の出力が生成されます。

組み込みsort関数を使用した正負の数値の並べ替え結果: -3 -1 -1 0 2 4 6

2. 関数の再帰呼び出しを使用する方法

サンプルコード

#include <bits/stdc++.h>
using namespace std;
void Rotate(int arr[], int first, int last){
    while(first < last){
        int temp = arr[first];
        arr[first] = arr[last];
        arr[last] = temp;
        first++;
        last--;
    }
}
void Rearrangement(int arr[], int first, int last){
    if(first == last){
        return;
    }
    Rearrangement(arr, (first + 1), last);
    if(arr[first] >= 0){
        Rotate(arr, (first + 1), last);
        Rotate(arr, first, last);
    }
}
int main(){
    int arr[] = {4, 2, -1, -1, 6, -3, 0};
    int size = sizeof(arr)/sizeof(arr[0]);
    int temp = 0;
    for(int i = 0; i < size; i++){
        if(arr[i] < 0){
            temp++;
        }
    }
    //配列を並べ替える関数を呼び出す
    Rearrangement(arr, 0, (size - 1));
    Rotate(arr, temp, (size - 1));
    //並べ替え後の配列を出力
    cout<<"再帰を使用した正負の数値の並べ替え結果: ";
    for(int i = 0; i < size; i++){
        cout<< arr[i] << " ";
    }
    return 0;
}

出力

上記のコードを実行すると、以下の出力が生成されます。

再帰を使用した正負の数値の並べ替え結果: -1 -1 -3 4 2 6 0

まとめ

sort()関数を使う方法は実装が非常にシンプルで、計算量はO(n log n)と効率的です。一方、再帰を使う方法は、再帰呼び出しとローテーション処理を組み合わせて負の数をすべて正の数より前に移動させるアプローチであり、完全なソートではなく負数を前方に集める処理である点に注意してください。目的や制約に応じて、適切な方法を選択しましょう。