[音楽再生] DOUG LLOYD：選択ソートです ご想像のとおり、アルゴリズム、 要素の集合をソートします。 また、アルゴリズムのリコール ステップバイステップのセットです タスクを完了するための手順の。 

選択で並べ替え 基本的な考え方は、これであります 最小のソートされていない要素を検索し、 ソートされたリストの最後に追加します。 事実上、これは何をするかビルドがあります ソートされたリスト、一度に一つの要素。 擬似コードにそれを破壊 我々は、このアルゴリズムを述べることができ 次のように、なるまでこれを繰り返します 何のソートされていない要素が残っていません。 ソートされていないを検索し データは、最小値を見つけるために、 次いで、最小値を交換します ソートされていない部分の最初の要素。 

それは、これを視覚化するのを助けることができます それでは、これを見てみましょう。 これは、私が争う、あります ソートされていない配列と私はしました すべてのことを示すことによってそれを示しました 要素で、赤色に着色されています 彼らはまだソートされていません。 これは、全体で 配列のソートされていない部分。 

それでは、以下のステップを介して行ってみよう この配列をソートするために選択ソート。 そこで再び、我々はつもり繰り返しです まではソートされていない要素が残っていません。 我々は、全体を検索つもりです データは、最小値を見つけるために、 し、次いでその値を入れ替えます ソートされていない部分の最初の要素。 

今、再び、全体 配列がソートされていない部分です。 赤の要素のすべてがソートされていません。 だから我々はを検索し、 私たちは、最小値を見つけます。 私たちは、先頭から開始 我々は、最後に移動 私たちは、最小値は、1です見つけます。 だから、一部一つです。 そして、第二部では、とその値を入れ替えます ソートされていない部分の最初の要素、 または、最初の赤の要素。 

この場合であろうと 5、私たちは1と5を交換します。 我々はこれを行うと、我々はできます 視覚的に私たちがしたことを参照してください。 最小の値を持つ要素を移動 配列の、非常に先頭に。 効果的にその要素をソートします。 

そして、私たちは実際に確認することができます そして、状態1ということは、ソートされます。 そして、私たちはソートされた部分を示すだろう 私たちの配列の青、それを着色することもできます。 

今、私たちは再びプロセスを繰り返します。 我々は、ソートされていない部分を検索 最小の要素を見つけるための配列。 この場合には、2の。 

私たちは最初にすることを入れ替えます ソートされていない一部の要素。 この場合、2つもあることを起こります ソートされていない部分の最初の要素。 だから我々は、それ自体で2を交換し、 これは実際には2つだけを残し それは、それがソートのWHERE。 引き続き、全体を検索 最小の要素を検索します。 これは3つです。 私たちは最初にそれを交換 5である素子。 そして今、3つがソートされます。 

私たちは再びを検索し、我々 最小要素が4である見つけます。 我々は、最初の要素とそれを交換します ソートされていない部分、今4がソートされます。 

私たちは5であることを見つけます 最小要素。 私たちは最初にそれを交換 ソートされていない一部の要素。 そして今5がソートされます。 

そして最後に、私たちの ソートされていない部分が構成されてい 単に1つの要素の、 私たちは全体を検索 私たちは6であることを見つけます 最小の、そして実際には、唯一の要素。 そして、我々はそれがソートされていることを述べることができます。 そして今、我々は我々の配列を切り替えました 完全にソートされていないされてから 赤で、完全にソートします 青色で、選択ソートを使用。 

そこでここでは最悪のシナリオは何ですか？ まあ最悪で 場合、我々は以上のを見ています 配列の要素のすべて 最小のソートされていない要素を見つけます、 我々は繰り返す必要が このプロセスをn回。 配列の各要素のために一度 私たちだけのため、このアルゴリズムでは、 一度にソートつの要素。 

最良のシナリオは何ですか？ まあそれは右、全く同じですか？ 私たちは実際にはまだをステップ実行する必要があります 配列のすべての単一の要素 それがあることを確認するために、 実際には、最小の要素。 

だから、最悪の場合の実行時間は、我々 プロセスをn回繰り返す必要があり、 n個の要素のそれぞれについて一度。 そして最良の場合のシナリオにおいて、 私たちは同じことを行う必要があります。 

だから、戻って私たちの考え 計算の複雑さのツールボックス、 最悪です、あなたは何を思いますか 選択ソートのためのケースランタイム？ 最高です、あなたは何を思いますか 選択ソートのためのケースランタイム？ 

あなたは、nのビッグOの二乗と思いました、 nのビッグオメガ二乗しましたか？ あなたは正しいだろう。 ものであり、実際には、 最悪の場合と最良の場合の実行 選択ソートのための時間、。 

私はダグロイドです。 これはCS50です。