bubble-sort - ソートアルゴリズムを適用せずに、コレクションがほぼソートされているかどうかを知ることができますか?

Question

ソート アルゴリズムに関するウィキペディアの記事の http://en.wikipedia.org/wiki/Sorting_algorithm#Summaries_of_popular_sorting_algorithms のバブル ソートの下には次のように書かれています。要素は大幅にずれていません)

だから私の質問は次のとおりです。最初にソートアルゴリズムを使用してリストをソートせずに、それがほぼソートされているかどうかをどうやって知ることができますか?

Answer 1

配列がどの程度ソートされているか、またはランダムであるかについての標準化された尺度が存在するとは思いません。

独自の尺度を考え出すことができます-順序が狂っている隣接するペアの数を数えたり(コメントで提案されています)、配列内の小さな数字の前に発生する大きな数字の数を数えたり(これは単純な単一のペアよりもトリッキーです)合格）。