Pythonで回転操作により配列をソートできるか判定する方法

問題の概要

数値のリスト nums が与えられ、「回転」操作を使ってこのリストを昇順にソートできるかどうかを判定します。ここでいう回転とは、配列の末尾から連続するいくつかの要素を取り出し、そのまま配列の先頭へ移動させる操作のことです。

例えば、入力が nums = [4,5,6,1,2,3] の場合を考えてみましょう。末尾の3つの要素「1, 2, 3」を先頭に移動させると [1,2,3,4,5,6] となり、ソートが完了します。したがって、この場合の出力は True となります。

解法のアプローチ

この問題は、次の手順で解くことができます。

• n をリスト nums のサイズとします。
• もし nums がすでにソート済みであれば、True を返します。
• そうでない場合は、以下の処理を行います。
  • status を True で初期化します。
  • i を 0 から n-2 まで走査し、nums[i] > nums[i + 1] となる最初の位置（降順になっている箇所）でループを抜けます。
  • i に 1 を加算します。
  • k を i から n-2 まで走査し、再び nums[k] > nums[k + 1] となる箇所が見つかったら、status を False にしてループを抜けます。
  • status が False の場合は False を返します。
  • そうでなければ、nums[n - 1] <= nums[0] が成り立てば True を、成り立たなければ False を返します。

なぜこの方法で判定できるのか

回転によってソート可能な配列は、必ず「2つの昇順の区間」に分割できます。つまり、配列内で降順になっている箇所（nums[i] > nums[i+1]）は最大でも1箇所しか存在せず、その境界を境に前半部分・後半部分がそれぞれ昇順になっていなければなりません。

さらに、後半部分の最後の要素が前半部分の先頭の要素以下（nums[n-1] <= nums[0]）であれば、境界をまたいでも昇順が保たれるため、適切な位置で回転することで完全にソートされた配列を得ることができます。

実装例

理解を深めるために、以下の実装を見てみましょう。

def solve(nums):
    n = len(nums)
    if all(nums[i] <= nums[i + 1] for i in range(len(nums) - 1)):
        return True
    else:
        status = True
        for i in range(n - 1):
            if nums[i] > nums[i + 1]:
                break
        i += 1
        for k in range(i, n - 1):
            if nums[k] > nums[k + 1]:
                status = False
                break
        if not status:
            return False
        else:
            if nums[n - 1] <= nums[0]:
                return True
            return False

nums = [4,5,6,1,2,3]
print(solve(nums))

入力

[4,5,6,1,2,3]

出力

True

計算量について

このアルゴリズムの時間計算量は O(n)、空間計算量は O(1) です。配列を最大2回走査するだけで判定が完了するため、非常に効率的な手法と言えます。