ソートの基本きほん

導入どうにゅう

この講義こうぎで最重要さいじゅうようなのは、ソートを「小ちいさい順じゅんに並ならべる作業さぎょう」でなく、順序じゅんじょの情報じょうほうを作つくる操作そうさとして見みることです。

探索たんさくや二分探索にぶんたんさくが効率的こうりつてきに働はたらくのは、ソートで順序じゅんじょが作つくられているからです。この講義こうぎでは、ソート自体じたいの細こまかい実装じっそうより、何なにを比較ひかくし、どう並ならべ替かえているかを整理せいりします。

用語ようごと定義ていぎ

ソートSort とは、要素列ようそれつをある規則きそくにしたがって整列せいれつすることです。

方針ほうしん

まず比較ひかくを何回なんかいするかを見みます。そのあと、要素ようそを入いれ替かえるのか、分わけてから戻もどすのかという動うごかし方かたを見みます。

直感的ちょっかんてきな説明せつめい

ソートは、散ちらばった本ほんを本棚ほんだなの順番じゅんばんに並ならべ直なおすようなものです。近ちかくの 2 冊さつを少すこしずつ入いれ替かえる方法ほうほうもあれば、大おおきく 2 組くみに分わけてから整ととのえる方法ほうほうもあります。

厳密げんみつな説明せつめい

見分みわけ方かた

• 順序じゅんじょがあると後続こうぞくの処理しょりが楽らくになるなら、まずソートを疑うたがいます。
• 入力にゅうりょくが大おおきいなら $$O\left(n^2\right)$$O(n^2) か $$O\left(n\log n\right)$$O(n\log n) かを意識いしきします。

最終形さいしゅうけい

一言ひとことでいうと

• ソートは並ならべ替かえ作業さぎょうそのものより、その後あとの処理しょりを簡単かんたんにするための基盤きばんです。