[Powered by Google Translate] トミー：のは、選択ソートを見て、アルゴリズムを見てみましょう 番号のリストを取得し、それらを並べ替えるため。 アルゴリズムは、覚えているが、単純にステップ·バイ·ステップである タスクを実行するための手順。 選択ソートの基本的な考え方は、分割することである 2つの部分に私たちのリスト -  ソートされた部分と、ソートされていない部分。 アルゴリズムの各ステップで、番号がから移動されている 結局までソート部分にソートされていない部分 リスト全体がソートされます。 そこでここでは6つの番号のリストです -  23、42、4、16、8、15。 今のところ全体のリストはソートされていないと見なされます。 16のような数はすでに正しい順序であるかもしれませんが 場所、我々のアルゴリズムはこれを続けて知る方法がありません リスト全体がソートされます。 だから我々は我々の並べ替えまで未ソートするすべての数を考慮します それは自分自身。 我々はリストが昇順になりたいことを知っています。 だから我々は我々のリストのソートされた部分を構築したいと思う 左から右へ、小さい方から大きい方へ。 そのためには、最低限のソートされていない要素を見つける必要があります およびソート部分の終わりにそれを置く。 このリストがソートされていないので、実行する唯一の方法は、 思い出して、ソートされていない部分の各要素を見 最低と比較どの要素である と各要素。 だから我々は最初の23を見てみましょう。 これは、我々が見てきた最初の要素であるので、私たちは覚えているだろう 最低でもそれ。 次に、我々は42を見てみましょう。 42は23より大きいので、23は最小です。 次は23未満で4なので、4を覚えているだろう 新しい最小値として。 次は4より大きい16であるので、4 まだ最小値です。 8は4よりも大きく、15が4よりも大きいので、4でなければなりません 最小のソートされていない要素。 だから、たとえ人間として我々はすぐに4があることがわかります 最小の要素は、我々のアルゴリズムは見てする必要があります  - 私たちは4を見つけた後でも、すべてのソートされていない要素、 最小要素。 だから今我々は最小の要素、4を見つけたので、今度はお勧めします リストのソートされた部分にそれを移動します。 これが最初のステップですので、これは我々が4を配置することを意味 リストの先頭。 今のところ23は、リストの先頭にある 4と23を交換してみましょう。 だから今、私たちのリストは次のようになります。 それがあるので、私たちは、4を最終的な位置になければならないことを知っている 冒頭最小の要素と要素の両方 リストの。 我々は二度とそれを移動する必要がないことを意味し、これはそう。 だから、別の要素を追加するには、このプロセスを繰り返してみましょう リストのソートされた部分。 それだから我々は、我々は4を見てする必要がないことを知っている 既にソートされています。 だから我々は、我々はどのように覚えているだろう、42で起動することができます 最小要素。 そこで、次の我々は、42未満である23を見たので、よ 23が新しい最小値であることを覚えている。 次に我々はそう、23未満である16を参照 16新しい最小値です。 今、私たちはそう、16未満である8を見れ 8新しい最小値です。 そして最後に8が15未満であるため、我々は8が最小であることを知っている ソートされていない要素。 だから我々はソートに8を付加するべきであることを意味している リストの一部。 たった今4のみソート要素なので、配置したい 4から8の隣。 42以来のソートされていない部分の最初の要素である リストには、我々は42と8を交換したいと思う。 だから今、私たちのリストは次のようになります。 4および8は、リストのソートされた部分を表しており、 残りの番号がソートされていないを表す リストの一部。 それでは、別の反復を続けましょう。 我々が見ている必要はありませんので、私たちは、23で、この時間を開始 彼らがきたので、もう4と8 既にソートされて。 16は23よりも小さいので、私たちは覚えているだろう 新しい最小値として16。 16は42未満であるが、15は16よりも小さいので、15でなければなりません 最小ソートされていない要素。 だから今我々は15〜23を入れ替えたい 私たちは、このリストを与える。 リストのソートされた部分は、4,8及び15で構成されており、 これらの要素はまだソートされていない。 しかし、それだけでソートされていないので、次の要素、16、ことが起こる 既にソートされています。 しかし、知っている我々のアルゴリズムのための方法はありませんその16 すでに正しい場所にあるので、我々はまだする必要が 全く同じプロセスを繰り返します。 だからそう、我々は16が42未満であることを確認し、16は23未満です 16は最小要素である必要があります。 それは、それ自体には、この要素をスワップすることは不可能ですので、我々はできる 単にこの場所にしておきます。 だから我々は我々のアルゴリズムの1以上のパスが必要です。 42は23よりも大きいので、23でなければなりません 最小ソートされていない要素。 かつて我々は我々の最終的に終わる、23と42を入れ替える ソートされたリスト -  4、8、15、16、23、42。 我々は、それがだから42が正しい場所にある必要があります知っている 唯一の要素が残って、それが選択ソートだ。 現在、いくつかで我々のアルゴリズムを定式化してみましょう 擬似コード。 1行目では、我々は我々が上に統合する必要があることがわかります リストのすべての要素。 1つの要素から最後の要素を除いて リストがすでにソートされています。 2行目では、私たちは、ソートされていないの最初の要素を考慮する 私達が私達の場合と同じように、最低でもするリストの一部 たとえば、私たちはと比較する何​​かを持っている。 3行目は、我々は繰り返し処理する第2のループを開始 各ソートされていない要素。 我々は知っている私に繰り返された後、ソートされた部分 私たちのリストの各ステップからそれで私は要素持っている必要があります ソートつの要素。 だから最初にソートされていない要素は、位置iに1を加えたでなければなりません。 4行目の、私たちは最小に現在の要素を比較する 我々はこれまで見てきた要素。 現在の要素が最小値より小さい場合 要素は、次に我々は、新規としての現在の要素を覚えている 行5で最小。 最後に、ライン6と7で、私たちは最小値を入れ替える これにより第1ソートされていない要素を持つ要素、 リストのソートされた部分に追加します。 かつて我々はアルゴリズム、尋ねるべき重要な質問があります プログラマとしての自分自身はそれがどのくらいかかりましたか？ 私たちは最初にどのくらいの時間がかかりますかこの質問を聞いてみよう アルゴリズムは、最悪の場合に実行するには？ 我々はこのランニングを表すリコール ビッグO記法と時間。 ソートされていない最小の要素を決定するために、我々 本質的には、リスト内の各要素の比較をしました リスト内の他のすべての要素。 直感的に、これはnの二乗演算のOのように聞こえる。 私たちの擬似コードを見てみると、我々はまた、中にネストされたループを持っている 確かにOのように聞こえる別のループ、 nの二乗の動作。 しかし、我々は目を通す必要はありませんでしたことを覚えておいてください リスト全体をソートされていない最小の要素を決定する？ かつて我々は4は、例えば、ソートされたことを知っていた、私たちはしませんでした 再びそれを見て必要があります。 だから、これは実行時間を下げるのでしょうか？ 長さ6の私達のリストのために、私たちは5を作るために必要な 最初の要素のための比較のための4つの比較 第二の要素、というように。 すなわち、ステップの総数はの和であることを意味します 1からのリストの長さから1を引いたの整数。 我々は合計でこれを表すことができます。 我々はここで和に入ることはありません。 しかし、それはこの総和がn倍に等しいことが判明 nはマイナス2以上1。 または同等に、nは2以上2以上マイナスn乗。 漸近的な実行時の話を、このn乗項 このn任期を支配しようとしている。 だから、選択ソートは、n乗のOである。 私たちの例では、選択ソートは、まだするのに必要なことを思い出してください すでにソートされた番号かどうかをチェック 移動する必要がありました。 だから我々はすでに上に選択ソートを実行した場合ことを意味します リストソート、それはそれとして同じステップ数を必要とするであろう 完全にソートされていないリストをひくときだろう。 だから、選択ソートは、乗nの最高のケースの性能を持っている その我々はオメガNの2乗で表す。 そして、それは選択ソートのためのそれだ。 私たちができる多くのアルゴリズムの一つに過ぎ リストをソートするために使用します。 私の名前はトミーであり、これはCS50です。