IN-PLACEアルゴリズム

in-placeアルゴリズムとは、計算機科学においてデータ構造の変換を行うにあたって、追加の記憶領域をほとんど使わずに行うアルゴリズムを意味する。アルゴリズムの実行によって、入力データ構造が出力データ構造で上書きされることが多い。\"in-place\" とは「その場で」といった意味であり、in-place でないアルゴリズムは not-in-place あるいは out-of-place などと呼ばれることもある。入力データを出力データで上書きするアルゴリズムを非公式的に in-place であると呼ぶこともある。実際には（クイックソートのように）それだけでは不十分であるか、必要条件ではない。出力がストリームの場合など出力領域が不定であっても in-placeアルゴリズムと呼ばれることがある。一方、より実用的に出力領域の大きさを測定して in-place アルゴリズムかどうかを決定する立場もある（後述の例にある reverse など）が、この考え方では in-placeアルゴリズムかどうかを厳密に定義するのが困難である。対数領域帰着のような問題では、出力空間を無視するのが一般的である（その場合、出力はライトオンリーとするのが基本である）。