アルゴリズム 体操24 Cyclic Sort

Cyclic Sort

n個のオブジェクトを含むリストが与えられます。各オブジェクトは、作成時に、作成順序に基づいて1からnまでの一意の番号が割り当てられました。

O（n）の連続な番号に基づいてオブジェクトをin-placeで並べ替える関数を作成します。余分なデータ構造は必要ありません。簡単にするために、連続する番号のみを含む整数のリストが渡されたとします。ただし、各番号は実際にはオブジェクトです。

例

Input: [3, 1, 5, 4, 2]
Output: [1, 2, 3, 4, 5]

Input: [2, 6, 4, 3, 1, 5]
Output: [1, 2, 3, 4, 5, 6]

Input: [1, 5, 6, 4, 3, 2]
Output: [1, 2, 3, 4, 5, 6]

Solution

ご存じのとおり、リストには1からnの範囲の数値が含まれています。 この事実を利用して、数値を並べ替える効率的な方法を考えます。すべての数値は一意であるため、各数値を正しい位置に配置することができます。つまり、1をインデックス0に配置し、2をインデックス1に配置する、などのようにできます。

数値（または一般にオブジェクト）を正しいインデックスに配置するには、まずその数値を見つける必要があります。 最初に数値を見つけて正しい場所に配置すると、O（N^2）、これは受け入れられません。

代わりに、リストを一度に1つの数値で繰り返し、現在の数値が正しいインデックスにない場合は、正しいインデックスの数値と入れ替えます。このようにして、すべての数値を調べ、それらを正しいインデックスに配置し、リスト全体を並べ替えます。

def cyclic_sort(nums):
  i = 0
  while i < len(nums):
    j = nums[i] - 1
    if nums[i] != nums[j]:
      nums[i], nums[j] = nums[j], nums[i]  # swap
    else:
      i += 1
  return nums


def main():
  print(cyclic_sort([3, 1, 5, 4, 2]))
  print(cyclic_sort([2, 6, 4, 3, 1, 5]))
  print(cyclic_sort([1, 5, 6, 4, 3, 2]))


main()