ソート【sort】整列 / 並べ替え

概要

ソート（sort）とは、複数のデータが並んだ列を、何らかの順序に基いて順番通りになるよう並べ替えること。数値を大きい順または小さい順に並べたり、文字をアルファベット順や五十音順に並べたり、日時を古い順または新しい順に並べ替えることが該当する。

複数の同じ種類の要素が一列に並んでいる場合に、すべての要素に一律に適用可能な順序の規則を用いて並べ替える操作を意味する。数値と日付のように異なる種類の要素が混在していたり、要素間にじゃんけんの出し手のような循環的な関係性がある場合には正しく整列することができない。

数を小さい方から大きい方へ並べる順序を「昇順」（ascending order）、その逆を「降順」（descending order）という。数以外の場合、アルファベットを「A」から「Z」へ、読み仮名を「あ」から「ん」へ、日付や時刻を古い方（過去）から新しい方（未来）へといったように、本来の並び順や自然な順序を昇順、逆を降順という。

ソートアルゴリズム

コンピュータによるデータ処理でもソートは頻繁に用いられる操作で、整列手順を定式化したものを「ソートアルゴリズム」（sorting algorithm）という。古くから活発に研究され様々な手法が考案されており、計算回数の少なさ（高速さ）や必要な記憶装置の容量、手順のシンプルさ（プログラムの短さ）などが異なる。

平均的に効率が良く、広く用いられるのは「クイックソート」（quick sort）と呼ばれる手法で、要素数がn倍になると平均の計算時間が n×log₂n 倍になる。プログラミング言語に標準で組み込まれた配列を整列する関数などによく採用されている。

データ列に同じ値が含まれる場合、その出現順がソート前後で変わらない手法を「安定ソート」（stable sorting）、保存されるとは限らない（順序が入れ替わることがある）手法を「不安定ソート」（unstable sorting）という。

また、元のデータ列の格納領域のみを用いて操作が完結する手法を「内部ソート」（in-place sorting）、外部に別の領域を確保する必要がある手法を「外部ソート」（external sorting）という。組み込みシステムなど利用できるメモリ領域が限られる場合には、高速性よりも内部ソートであることが重視されることもある。

(2022.9.20更新)