Tip:
Highlight text to annotate it
X
>> [音楽再生]
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です。