Pythonで配列が「ほぼソート済み」かどうかを判定する方法

ほぼソートされた配列とは？

すべての要素がユニーク（重複なし）である数値の配列 nums があるとします。この配列が「ほぼソートされている（almost sorted）」かどうかを判定する必要があります。

ここでいう「ほぼソートされている」とは、各要素がソート後の本来の位置から最大1つ分だけずれた位置に存在している状態を指します。言い換えれば、どの要素も正しい位置から1インデックス以内の距離にあれば、その配列はほぼソートされているとみなせます。

例

入力が nums = [10, 30, 20, 40] の場合、出力は True になります。なぜなら、10 は本来の位置にあり、その他の要素（30 と 20）もそれぞれ本来の位置から最大1つ分しかずれていないためです。

解決アプローチ

この問題は、以下の手順で解決できます。

1. インデックス i := 0 から開始する
2. i が配列の長さ - 1 未満である間、以下を繰り返す：
   • nums[i] > nums[i + 1] の場合、2つの要素を入れ替え、i を1つ余分に進める
   • i を1増やす
3. 再度配列全体を走査し、隣接する要素に降順のペア（nums[i] > nums[i + 1]）が残っていれば False を返す
4. 問題がなければ True を返す

このアルゴリズムのポイントは、順序が崩れている箇所を見つけたら一度だけスワップして修正し、その後もう一度全体をチェックすることです。すべての要素が本来の位置から最大1つずれている場合のみ、この単純な修正で完全にソートされた状態になります。

実装例

以下のコードで実際の動作を確認してみましょう。

def solve(nums):
    i = 0
    while i < len(nums) - 1:
        if nums[i] > nums[i + 1]:
            nums[i], nums[i + 1] = nums[i + 1], nums[i]
            i += 1
        i += 1
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            return False
    return True

nums = [10, 30, 20, 40]
print(solve(nums))

入力

[10, 30, 20, 40]

出力

True

まとめ

この方法では、まず隣接する逆順のペアを1回のスワップで修正し、その後に全体を再検証することで、配列がほぼソートされているかどうかを効率的に判定できます。時間計算量は O(n) 程度であり、要素数が多い配列でも高速に処理できるのが特徴です。