C++で配列内のクロスライン（交差線）を数える方法

問題の概要

ソートされていない、重複のない要素からなる整数配列が与えられます。この課題のゴールは、配列をソートしたときに発生するクロスライン（交差線）の総数を求めることです。

クロスラインとは、配列の各要素を縦線として表現したとき、ソートの過程で線と線が交差する回数のことです。言い換えると、これは配列内の転倒（インバージョン）、すなわち「手前の要素が後ろの要素より大きい」というペアの個数を数える問題と同じものです。

• Arr[] = { 1,2,4,3,5 } の場合：下図のように3本のクロスラインが存在します。
• Arr[] = { 1,2,3,4,5 } の場合：すでにソート済みのため、クロスラインは0本です。

クロスラインのカウントには挿入ソート（insertion sort）を利用します。挿入ソートでは、右側の要素を1つずつ取り出し、左側のソート済み領域の正しい位置へ挿入していきます。要素が正しい位置に移動するまでの間に、自分より大きい要素をすべて「横切って」いくため、その通過回数を数え上げればクロスラインの総数が求まります。

具体例で理解する

入力： arr[] = { 4, 3, 1, 2 }
出力： 配列内のクロスラインの数 − 5
説明： 線4-4と線3-3は、それぞれ線1-1と線2-2と交差します。ここで4本のクロスラインが発生します。さらに線4-4と線3-3も互いに1回交差するため、合計は 4 + 1 = 5 本となります。

入力： arr[] = { 0, 1, 5, 3 }
出力： 配列内のクロスラインの数 − 1
説明： 線5-5と線3-3が互いに1回だけ交差します。よってクロスラインは合計1本です。

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

• 重複のない数値で初期化された整数配列 arr[] を用意します。
• 関数 insertionSort(int arr[], int n) は、配列とその長さを受け取り、ソートを行いながらクロスラインの数を数えて結果として返します。
• クロスライン数の初期値は 0 とし、count 変数で管理します。
• 先頭要素は最初からソート済みとみなせるため、2番目の要素から末尾まで（i = 1 〜 i < n）ループし、各要素を item = arr[i] として取り出します。比較位置は j = i - 1 から開始します。
• arr[j] > item かつ j >= 0 の間、左側の要素を1つ右へシフトします。シフトが起こるたびに count を1増やします。これは item がそれらの要素をすべて横切る（＝交差する）ことを意味します。
• while ループを抜けたら、item を正しい位置 arr[j + 1] に配置します。
• この処理を全要素に対して繰り返し、交差した回数の合計を count に蓄積します。
• 最終的な count の値が、配列に存在するクロスラインの総数になります。

C++ 実装例

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

int insertionSort(int arr[], int n){
    int count = 0;
    int item;
    int j;
    for (int i = 1; i < n; i++){
        item = arr[i];
        j = i - 1;
        // ソート済み部分の正しい位置へ要素を挿入する。
        // 正しい位置まで移動する間に通過する要素の数が、クロスラインの数になる。
        while (j >= 0 && arr[j] > item){
            arr[j + 1] = arr[j];
            j = j - 1;
            count++;
        }
        arr[j + 1] = item;
    }
    return count;
}

int main(){
    int arr[] = { 4, 5, 3, 1, 2 };
    int n = 5;
    cout << "Number of cross lines: " << insertionSort(arr, n);
    return 0;
}

出力結果

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

Number of cross lines: 8

計算量について

挿入ソートベースのこの手法は、時間計算量が O(n²)、空間計算量が O(1) です。配列サイズが大きくなる場合は、マージソートを応用した分割統治法（O(n log n)）による転倒数の計算を検討するとよいでしょう。

まとめ

クロスラインのカウントは、挿入ソートの各要素の移動過程で「いくつの要素を超えていくか」を数えるだけで実現できる、非常にシンプルなアプローチです。小規模な配列であれば十分実用的であり、この問題が配列の転倒数を求める問題と等価である点を押さえておくと、アルゴリズムの理解がさらに深まります。