In-placeアルゴリズム
n個の要素からなる配列の要素を逆順に入れ替える場合を考える。単純な方法として以下の方式が考えられる:
この方法では配列 b の領域に O(n) の空間を必要とする。記憶領域の確保は時間がかかることが多い。もし a を今後必要としないなら、以下のような in-placeアルゴリズムで a に逆順の出力結果を書き込むことができる:
他の例として、以下のような整列アルゴリズムは入力配列そのものを操作して整列を施す in-placeアルゴリズムである:
バブルソート
コムソート
選択ソート
挿入ソート
ヒープソート
シェルソート
クイックソートは in-place アルゴリズムと言われることが多いが、素朴な実装ではそうではない。最悪の場合再帰の深さが O(n) に達し O(n log n) の領域を消費するからである。イントロソートに改めれば、再帰の深さをO(logn)に抑えられるため、広い意味では in-place になる。
選択アルゴリズムは多くの場合 in-place だが、結果を得るために入力配列の要素の配置を大幅に変えてしまう。
文字列操作アルゴリズム(トリムや文字列の逆転など)は in-place で行われることが多い。