読者です 読者をやめる 読者になる 読者になる

A little bit of everything

情報系大学院生の備忘録

安定ソート(stable sort)

ソートアルゴリズムにおいて「安定である」ということの意味

同順序のものの順序関係が、ソート前とソート後で保たれるもののこと。 (順序が保たれないものは、「安定ではない」という)

例) 本の値段と出版年によってソートする場合を考える。

f:id:yuukiyg:20160116185432p:plain


最初に出版年でソートし、次に値段でソートした場合、同じ値段の本は出版年順にソートされた順序が保たれたままになるようなものは、安定ソートに分類される。 f:id:yuukiyg:20160116185434p:plain


以下のソートは安定ソートの一例。