[音楽再生] ANDI PENG：セクションの週3へようこそ。 すべての来てくれてありがとう、あなたたち、 今日この早い開始時間に。 私たちは少し、素敵なを持っています 親密なグループ今日。 だから、うまくいけば、我々はに取得します 仕上げ、おそらく、初期の、 少し早い今日。 だからすぐに、単にいくつかの 議題今日発表。 私たちは始める前に、私たちはしています わずかに行くつもり いくつかの簡単な物流の問題、PSET 質問、デブリーフィング、そのようなこと。 そして、我々は右ダイビングます。 我々は、GDBへと呼ばれるデバッガを使用します 我々のコード、ダビデを暴く開始 先日講義で説明しました。 私たちは、ある種の4種類の上に行きますよ。 我々は非常にすぐにそれらの上に行きますよ 彼らはかなりの集中しているからです。 しかし、知っているすべてのスライドと ソースコードは常にオンラインです。 そうするためには、あなたの閲覧で、お気軽に 戻って、その見てみましょう。 我々は通過します 漸近記法、これ ただ派手な方法であります のが「ランタイム」を 私たちは大きなOを持っている場合は、これ ダビデは講義で説明しました。 そして、我々はまた、オメガを持っています 下界ランタイムがあります。 そして、私たちは少し詳しく説明します 綿密な方法これらの作業について。 そして最後に、我々は、二分探索の上に行きますよ なぜなら、すでに持っているあなた方の多く おそらくことを知っているあなたのpsetをちらっと見ました それはあなたのpsetでの質問です。 だから、すべてにご満足いただけることでしょう 私たちは今日、これをカバーします。 そして最後に、あなたのあたり セクションのフィードバック、実際に私 で約15分間放置 わずか行くに終了 pset3の物流、ご質問、 多分指導のビット、あなたがする場合は、 我々はプログラミングを開始する前に。 それでは、を介して取得してみましょう かなり迅速に材料。 そして、我々はいくつかの時間を過ごすことができます PSETのためのより多くの質問を取ります。 OK。 すぐに、これだけの数 発表我々が今日開始する前に。 まず、作ることに歓迎 それあなたのpsetの2つの貫通。 私はええ、レッツyour--で見ていました そのいずれかの拍手のラ​​ウンドを取得します。 実際に、私は、本当にでした 本当に感動。 私はあなたたちのために、最初のpsetを段階的 先週とあなたたちは信じられないほどでした。 スタイルのポイントにありました いくつかのコメントのほかに。 あなたはいつもしていることを確認してください あなたのコードをコメント。 しかし、あなたのpsetは点にありました。 そして、それを維持します。 そして、それはへ年生のために良いことです あなたたちは入れていることを確認 あなたのスタイルのように多くの努力で あなたのコード内で、デザイン あなたが見ることのために私たちは希望のこと。 だから、私は感謝の気持ちに沿って渡しています TAの残りのため。 しかし、そこにあります いくつかの結果を聞く質問 私はちょうどそれの上に行きたいです 両方の私の人生になるだろう および他の多くの TAが「少し簡単に住んでいます。 まず、私はこれを気づきました 過去はあなたの何をweek-- 上check50を実行されています あなたの前にあなたのコードを提出しますか？ OK。 だから、誰もがcheck50にやるべきこと、 secret--実際に我々because-- 私たちの正しさの一部としてcheck50を実行 あなたのコードをテストするためのスクリプト。 だからあなたのコードが失敗した場合 check50、すべての可能性で、 それはおそらくに起こっています 同様に私たちのチェックに失敗。 時々、あなたたち 正しい答えを持っています。 のように、貪欲で、いくつかの あなたは正しい番号を持って、 あなただけのいくつかの余分なものをプリントアウト。 そして、その余分なもの 実際にチェックに失敗しました、 コンピュータはしていませんので、 実際にそれが探しているものを知っています。 そしてそれはちょうど、通じ実行されます あなたの出力がないことを確認 私たちは答えを期待するものと一致 よく、それは間違ってマークします。 そして、私はで起こったことを知っています あなたの例いくつかの今週。 だから私は戻って、手動で行ってきました みんなのコードをregraded。 しかし将来的には、 、確認してくださいしてください。 あなたが実行していること あなたのコードに50を​​ご確認ください。 そのためには、TAのための痛みのようなものです 戻って手動で勾配をつけ直すために持っています すべてのためのすべての単一のpset シングル、少しインスタンスを逃しました。 だから私は、任意のポイントを離陸しませんでした。 私は多分、離陸したと思います 1または設計のための2つ。 しかし将来的には、もし あなたはcheck50に失敗しています、 ポイントが取得されます 正しさのためにオフにします。 さらに、のpsetがあります 正午金曜日による。 私は7分があると思います 私たちはあなたを与える後半猶予期間。 ハーバード時間当たり、それらが許可されているに 後半すべてに7分です。 だからここにエールで、我々はよ 同様にそのに準拠しています。 しかし、かなり多く、12：07で、 あなたのpsetがでない場合は、 それは、後半にマークされるだろう。 そしてそれがマークされている間 私はのように遅く、TA-- まだあなたのpsetをグレーディングすることになるだろう。 だから、あなたはまだグレードが表示されます表示されます。 しかし、であることを知っています 学期の終わり、 すべての後半のpsetだけになります コンピュータによって自動的にゼロに。 我々は2つ​​の理由でこれを行います。 一つは、時には我々が得ます 学部長の言い訳のように、免除、 後でその上で、私はまだ知りません。 だから我々は我々がグレーディングしていることを確認したいです 念のため、私は、同じようにすべて 学部長の言い訳が欠落。 そして第二に、中に保ちます 心、あなたはまだすることができます その1 PSETをドロップ 全範囲のポイントを持っています。 そして、私たちはグレードしたいです あなたのpsetのすべてだけ 必ずあなたの範囲のことを確認します そこに、あなたはそれをしようとしています。 だから、それは遅場合でも、あなたはまだよ スコープポイントのクレジットを取得し、私は​​思います。 物語の道徳的だから、作るさ 必ずあなたのpsetはオンタイムです。 そして、彼らはオン時間内にない場合、 それは素晴らしいではないことを知っています。 ええ、私は上に移動する前に、誰もが持っているん PSETフィードバックに関する質問？ うん。 聴衆：あなたは私たちが言いました psetのいずれかをドロップすることができますか？ ANDI PENG：うん。 だから、全体の9のpsetがあります 学期の経過。 そして、あなたはスコープを持っている場合 points--のでスコープは、単にあります かなり、あなたがしようとしています 問題は、あなたが時間内に入れています、 あなたがしたことを示しています あなたが仕様を読んだ実証しました。 それはかなりの範囲です。 そして、あなたが果たしている場合 スコープポイント、我々 最低をドロップすることができます 完全な範囲のうち1。 だから、にあなたの利点にです 完了し、すべてのPSETを試してみてください。 いずれの場合であってもupload-- 彼らは動作し、それらをすべてアップロードします。 そして、我々は、うまくいけばのことができるようになります あなたはこれらの点のいくつかを返します。 クール。 その他の質問は？ グレート。 第二に、オフィスはいくつかのhours-- 営業時間についての簡単なメモ。 そこでまず、初期の週に来ます。 誰もが今までではありません 月曜日の営業時間。 クリスタベルはに来ました 営業時間昨夜。 クリスタベル、うん。 そして、我々はオフィスで何を持っていました 時間昨夜、クリスタベル？ 観客：我々は、アイスクリームを持っていました。 ANDI PENG：だからそうです、私たちは持っていました 営業時間の最後の夜にアイスクリーム。 私はあなたを約束することはできませんが 私たちは、営業時間にアイスクリームを持っています 毎週、私はあなたを約束することができるもの かなりあるだろうということです TA比に優れた学生。 合法的なように、それは一から三のようなものです。 、とそのコントラストのに対し 木曜日には、約150を持っています 本当に子供なしアイスクリームを強調しました。 そして、それは誰ものための生産的ではありません。 物語の道徳的なだから、早期に来ています 営業時間と良いものへ 起こります。 また、質問をする準備してきます。 ええと？ 関係なく、どのようなTAの、私 、言っていると思いますが、 我々は、カップルの学生を取得してきました 10：50、のような、で木曜日に来る人 仕様を読んではありません 私を助けるようなもの、私を助けて。 残念ながら、その時点で、あります 多くの私たちはあなたを助けるために行うことができません。 だから、初期の週に来てください。 営業時間に早期に来ます。 質問をする準備してきます。 必ずことを確認してください 学生、どこにあります あなたはそのようにする必要があります TAが、に沿ってあなたを導くことができます どのような営業時間であります 割り当てられなければなりません。 第二に、私は教授を知っています テストで私たちを驚かせたいです。 私は教授のものを持っていました ところで、ヨーヨーのような、 その中間を覚えています あなたは来週の月曜日です。 ええ、私はその中間については知りませんでした。 だから私はそのTAになるだろうよ それはあなたにすべてのことを連想させるクイズ 0--あなたが知っている、ので、我々は、CSです。 今、私たちは、配列をやったことを、あなたが取得します それはクイズ0だからこそ、えっ、1をクイズではありませんか？ OK。 ああ、私はその1にいくつかの笑うを得ました。 OK。 だから、クイズ0があれば10月14日になります あなたは月曜日〜水曜日のセクションにいます そして10月15日あなたがしている場合 火曜日・木曜日のセクション。 これは適用されません ハーバード大学のあなたのそれら 私はあなたがすべてのだろうと思いwho-- 14日にあなたのクイズを取ります。 そうそう、来週、場合 ダビデは、講義で、行きます、 ええ、そんなに クイズ来週、あなたのすべて ので、ショックを受けることはありません あなたはセクションに来ました あなたはあなたのことを知っています クイズ0は2週間です。 そして、我々は審査があるでしょう セッションおよびすべて。 そんなに心配しません そのために怖がっています。 ご質問before--ご質問 全てにおいて物流の問題で、 グレーディング、営業時間、セクション？ うん。 観客：クイズがありそう 講義中になるだろうか？ ANDI PENG：うん。 クイズだから、私が思うに、60です そのタイムスロットに割り当てられた分 あなただけ取るだろうと 講堂インチ だから、来る必要はありません ランダム午後7時、のような、上。 大丈夫だよー。 うん。 クール。 大丈夫。 だから我々はするつもりです あなたに概念を導入します ダビデは一種すでに持っているこの週 この一週間の講義で触れました。 これは、GDBと呼ばれています。 そして、どのように多くの、にある間 あなたのpsetを書くもちろん、 言う大きなボタンに気づきました あなたのIDEの上部に「デバッグ」？ OK。 だから今、私たちは実際に発掘するために取得します 実際にどのようなそのボタンの謎 い。 そして、私はそれは、あなたを保証します 美しい、美しいもの。 だから今まで、私は思います 二つのことがあったです 学生は一般的になっています psetをデバッグするときにやって。 一方、彼らはいずれかで追加します printf（） - ので、すべての数行、 彼らはprintfの（）に追加します - ああ、この変数は何ですか？ ああ、この変数は何ですかnow-- あなたは親切なの進行状況を確認 それは実行時にコードの。 や子供たちが行う第二の方法は、 彼らは全体のことを書くこと して、最後に次のように行きます。 うまくいけば、それは動作します。 私はあなたを保証する、GDBは良いです これらのメソッドの両方より。 うん。 だから、これはあなたの新しい親友になります。 それは美しいものだからです その視覚的に表示され、両方の あなたのコードが何をしていますか 特定の時点で だけでなく、どのようなあなたのすべて 変数は運んでいます、 それらの値が何であるかのように、 その特定の時点で。 このようにし、あなたが本当にすることができます あなたのコードにブレークポイントを設定します。 あなたは、行ごとを介して実行することができます。 そして、GDBだけのために持っています あなたは、あなたのために表示され、 何すべての変数の 、彼らは何をしているしています、 何がコード内で起こっています。 そして、このように、それはです そんなに簡単に参照するために 何がprintfの-INGの代わりに起こっています または、あなたの文を書き留めます。 だから我々は、この後の例をやります。 だから、これはビット抽象的です。 心配しないで、我々は例もしないでしょう。 だから、本質的に、三大、 あなたはGDBに必要があります最も使う機能 次は、ステップオーバー、 およびボタンへのステップ。 私は頭の上に行きますよ そこに、実際に、今。 だから人はすべてのことを見ることができます または私は少しズームインする必要がありますか？ バックでは、あなたはそれを見ることができますか？ 私は、ズームインする必要がありますか？ 少しだけ？ うんいいね。 そうしよう。 OK。 だから、私は、ここでは、持っています 貪欲のための実装です。 そして、あなたたちの多くが書いている間 そのform-- whileループで貪欲 行うには完全に受け入れられる方法です それを行うにはit--別の方法は、単純であること モジュロに分けます。 あなたが持つことができるので、あなたの 値と、あなたの残りを持っています。 そして、あなただけのことができます 一緒にそれをすべて追加します。 私がやっている何のロジックを行い 誰もがここに意味をなさない、 私たちは始める前に？ やや？ クール。 グレート。 それはかなりセクシーな作品です コー​​ドの、私は言うでしょう。 私はに、ダビデを言ったように しばらくして、講義、 あなたはすべてのコードを見てから始めましょう 美しいものとして。 そして、時にはあなたは美しい見たとき コー​​ドは、このような素晴らしい感覚です。 だからしかし、このコードは非常にある間 美しい、それが正しく動作しません。 それでは、この上check50を実行してみましょう。 50 20-- OOPを確認してください。 2？ そのpset2はありますか？ うん。 ああ、PSET1。 OK。 だから我々はcheck50を実行します。 そして、あなたたちはここで見ることができるように、 それは例のカップルを失敗しています。 そして、あなたのいくつかのために、中 問題のセットをしているもちろん、 ああ、なぜそれが機能していない、のようにあなたがしています。 なぜそれがいくつかのために働いています 値ではなく、他人のために？ さて、GDBはあなたの図を助けるために起こっています これらの入力が機能していなかった理由を。 OK。 それでは、、のいずれかを見てみましょう 私はcheck50に失敗したチェック 0.41の入力値でした。 正解だから あなたは4で取得する必要があります。 しかし、その代わりに、私はプリントアウトしていますどのような 間違っている3-nは、あります。 だから、ちょうどこれを手動で実行してみましょう check50が動作していることを確認してください。 それでは、./greedyやってみましょう。 おっと、私は欲張りようにする必要があります。 そうしよう。 今./greedy。 どのくらいを負っているのですか？ それでは、0.41を実行してみましょう。 そして、うん、私たちはここを参照してください それは3を出力するということ ときに正しい答えは、 実際には、4でなければなりません。 それでは、GDBを入力して、どのように我々を見てみましょう この問題を修正するに取り掛かることができます。 の最初のステップそう 常にあなたのコードのデバッグ ブレークポイントを設定することで、 で、あなたやポイント コンピュータまたはたい デバッガが見て開始します。 だから、あなたが本当にない場合は あなたの問題が何であるかを知っています、 通常、典型的なものは、私たちがしたいです 行うには、主に私たちのブレークポイントを設定することです。 だから、あなたたちはこれを見ることができれば 右が赤いボタン、 うん、それは私が設定しました 主な機能のためのブレークポイントを設定します。 私はそれをクリックします。 そして私は私のデバッグボタンまで行くことができます。 私は、そのボタンを押してください。 私ができるなら、私はズームアウトしてみましょう。 そうしよう。 だから我々は、ここでは、右側のパネルを持っています。 私は、後ろにみんなごめんなさい、あなた 本当に本当によく見ることができません。 しかし、本質的に、すべての この右側のパネルにはやっています 両方の強調表示を追跡しています コー​​ドの行である行、 コンピュータは、現在実行されていること、 だけでなく、あなたのすべての変数 ここでダウン。 だから、セント、コイン、n個を持って、 すべての異なるものに申告 この時点で。 私たちが実際に持っていないので心配ありません、 まだ変数に初期化。 お使いのコンピュータでだから、あなたの コンピュータはただ見ています、 ああ、32767は、最後に使用された機能 私のコンピュータにそのメモリ空間の。 セントが現在ある場所となるようです。 しかし、誰それ一度あなたは、コードを実行しません それは、初期化になるはずです。 それでは、通過させ、線で ラインは、ここで何が起こっています。 OK。 だからここまでの3つがあります 私は説明したボタン。 あなたがプレイ、またはファイル名を指定して実行機能を持っています、 ボタンを押すと、ボタンの上にステップを持っています、 そして、あなたはまた、ボタンにステップを持っています。 そして、基本的に、すべての3つの 彼らは自分のコードを行きます そして、異なることを行います。 だから一般的に、あなたがデバッグしているとき、 私たちは、ただプレイをヒットする必要はありません プレイはちょうど実行されますので、 それの最後にあなたのコード。 それから、あなたは実際にはしません 知っているあなたの問題 あなたが複数のブレークポイントを設定しない限りです。 あなたは複数のブレークポイントを設定した場合、 それだけで自動的になります 1ブレークポイントから実行し、 次へ、次へ。 しかし、このケースでは、我々はしました 私たちのためだけでは1、 私たちのように動作するようにしたいです ダウン上から下へ。 だから我々はそのボタンを無視するつもりです 今、このプログラムの目的のために。 関数オーバーステップだから すべての単一の行をステップオーバー とを示していますどのような コンピュータがやっています。 関数へのステップは行きます 実際の関数に それがコードのあなたのライン上にあります。 ですから、例えば、printfのような（）、 それは右、機能ですか？ 私は物理的にステップしたい場合 printf（）関数に、 私は実際の片に行くだろう printf（）が書かれたコードとを参照してください 何が起こっています。 しかし、一般的に、我々はことを前提としてい 私たちはあなたを与えるコードが動作します。 我々は、printfの（）が機能していると仮定します。 私たちは、GetIntでは（）が動作していることを前提としています。 そうする必要はありません これらの関数にステップイン。 しかし、機能があるかどう あなたは自分自身を書くこと 確認したいこと で何が起こっていますか、 あなたがステップしたいです その関数に。 だから今、私たちはちょうどつもりです コー​​ドのこの部分の上に進みます。 それでは見てみましょう。 ああ、プリント、 "ああ海、どのように 多くの変更が負っているのですか？」 私たちは気にしないでください。 私たちは、それが働いている知っています、 私たちはそれをステップオーバー。 だからnは、私たちのフロートであること 我々initialized--またはdeclared--ました 上部にまで、私たちは今です GetFloatをすることに等しいです（）。 それでは、そのステップオーバーしましょう​​。 そして、我々はでご覧ください 底のここに、プログラム 値の入力に私を促しています。 それでは入力私たちが望む価値を聞かせて 0.41である、ここでテストします。 グレート。 だから今N--君たちが見るん ここで、それはだbottom--で 我々のでstored-- まだ丸められていない、それはです このような巨大に保存されています 0.4099999996フロート、 私たちに十分近いです 目的、今、0.41に。 そして、我々は、我々のように、後に表示されます プログラムをステップオーバー続け、 ここでは後に、n個となっています 丸みを帯びたとセントは41となっています。 グレート。 だから我々は我々の丸めの作業ということを知っています。 私たちは持っていることを知っています セントの正確な数、 私たちはそれがだことを知っています 本当に問題。 だから我々は、ステッピング続け​​ます このプログラムでの。 私たちはここに行きます。 だから、このコード行の後、我々 我々が持っているどのように多くの方面知っている必要があります。 私たちは、ステップオーバー。 そして、あなたは私たちが、実際には、いずれかを持っているかを参照してください。 四半期我々は25を差し引いたから 41の私達の初期値から。 そして、私たちは私たちのセントのための16の左を持っています。 誰もがどのように理解しています プログラムがステップ実行され そしてなぜセントは現在16となっています そしてなぜ、今、硬貨は1となっていますか？ 誰もがそのロジックを次のされていますか？ クール。 、この点のように、 プログラムの作業は、右？ 我々は、それが正確にやっている知っています 我々はそれをしたいのか。 そして、我々は実際にはしませんでした プリントアウトする必要があり、ああ、どのような この時点でセントです、 この時点でコインものです。 私たちは、プログラムを通過続けます。 ステップオーバー。 クール。 私たちは、ダイムの上に行きます。 グレート。 我々は、それがかかったことがわかり ダイムのための$ 0.10オフ。 そして今、我々は2枚のコインを持っています。 その通りです。 私たちは、ペニーの上に行くと、私たちは見ます 我々はセントの上に残ってしまったこと。 うーん、それは奇妙です。 ここでプログラムでまで、私はなっていました 私のペニーを差し引いています。 おそらく、私はありませんでした その行を右にやって。 そして残念ながら、あなたが見ることができます ここで、私たちが知っているので 我々は、強化していること 線32及び33を介して、 それはどこに私たちのプログラムです 不適切な変数は、実行していました。 だから、私たちは見て、ああ、見ることができ、 私はここセントを引いています、 しかし、私は実際にはありませんよ 私のコインの価値を加えること。 私はセントに追加しています。 そして、私はに追加する必要はありません セントは、私がコインに追加します。 だから我々は、コインのことを変更した場合、 我々は、作業プログラムを持っています。 私はcheck50を実行することができます。 あなたは、GDBの権利を終了することができます ここにして、再度check50を実行します。 私はこれを行うことができます。 私は欲張りようにする必要があります。 0.41。 そしてここで、印刷です 正解アウト。 あなたたちが見ることができるように、GDB 本当に強力なツールです 私たちは多くのコードを持っている場合の 行くと非常に多くの変数 それが私たちのために難しいこと、など を追跡するために人間。 GDBでコンピュータ、 デバッガは、能力を持っています すべてのトラックを維持します。 私はおそらくあなたたち、ヴィジョネアで、知っています いくつかのセグメンテーションフォールトを打った可能性があります あなたが実行していたので、 あなたの配列の範囲外。 シーザーの例では、それはです まさに私がここで何実装しました。 だから私はのためにチェックするのを忘れました 私ならば何が起こりますか 2つのコマンドライン引数を持っていませんでした。 私はちょうどそのチェックを入れませんでした。 私はDebug--を実行した場合ので、私は設定します そこに右に私のブレークポイントを設定します。 私は、デバッグを実行します。 OK。 うん。 だから実際には、GDBを想定しました そこに私に言っているように そこにセグメンテーションフォールトました。 私は何が起こっていたか分かりません 右が、私は、それを実行したとき それが働いていました。 あなたを介してコードの行を実行するとし、 GDBはちょうど突然、あなたに終了する可能性があります 上がると赤のエラーが何であるかを見てください。 それは、ちょっと、あなたにあなたを教えてあげましょう セグメンテーションフォールトを持っていました、 これは、あなたがアクセスしようとしたことを意味し 存在しなかった、アレイ内のスペース。 うん。 次の問題でそう 今週設定、君たち おそらく多くのを持っています 変数が漂っ。 あなたは何を確認するするつもりはありません それらはすべて、ある時点で意味します。 だから、GDBは本当に把握のお手伝いをします 彼らはすべて等しくされているかを そして、視覚的にそれを見ることができること。 誰がどのように混乱しています そのいずれかが働いていましたか？ クール。 大丈夫。 だから後に、我々は、 右のダイビングに行きます 異なる4つに 今週のためのある種のタイプ。 どのように多くのあなたの第一、第 すべての、私たちは始める前に、 pset3のための全体の仕様を読んでいますか？ OK。 私はあなたたちを誇りに思います。 それは、クラスの半分のようにするのです 前回よりはるかに多くのです。 だから、素晴らしいことだときのため 私たちは、コンテンツについての話 lecture--か残念で、 section--で私は好き その多くを関連付けるために バックPSETが何であるかに あなたがしたいですか あなたのpsetのそれを実装します。 だから、あなたが持って来れば 仕様を読んで、それはよ あなたが理解するためにはるかに簡単です 私が言うとき、私はについて何を話しています、 ちょっとああ、これは本当に可能性があります このソートを実装するのに適した場所。 読んでいるあなたの人々だから あなたのpsetの一部として、それを知っている仕様、 あなたがする必要があるとしています ソートの種類を記述します。 だから、これは非常に有用であろう あなた方の多く今日のために。 だから我々は、から始めましょう、 基本的に、最も単純なタイプ ソート、選択ソート。 以下のための典型的なアルゴリズム どのように我々はこのことについていいと思います ダビデはすべて、これらを経てis-- 講演ので、私はすぐに沿って移動します here--あなたは、本質的に 値の配列を持っています。 そして、あなたが見つけます 最小値はソートされていません あなたがして、その値を交換します 最初にソートされていない値。 そしてあなただけの繰り返し続けます あなたのリストの残りの部分と。 そして、ここで視覚的な説明です それがどのように動作するかの。 したがって、たとえば、私たちがあった場合に起動します 5要素の配列は、インデックス付き 3,5、2,6、および4の値を有する0〜4、 そう、今array--に配置され、 私達はちょうど仮定するつもりです 彼らはすべてのソートされていないしていること 我々はそれ以外の場合はテストしていませんので。 それでは、どの選択ソートだろう 仕事は、それが最初であろうことです 全体を通して実行 ソートされていない配列の。 これは、最小値を選ぶだろう。 この場合、図3に示すように、右 今、最小です。 それは5になります。 いや、5はthan--大きくありません または申し訳ありませんが、3 than--少なくありません。 だから、最小値はまだ3です。 そして、あなたは2を取得。 ああ、見ているコンピュータ、2は3未満です。 2は現在、最小値でなければなりません。 そして、その結果、最初の値と2スワップ。 だから、1パスの後、我々は確かに見ています 図2及び3が交換されます。 そして、私たちはただやって継続するつもりです 再びこの配列の残りの部分と。 だから我々はちょうどを介して実行するつもりです 配列の最後の4つのインデックス。 私たちは3であることがわかります 次の最小値。 だから我々は4でそれを交換しようとしています。 そして、我々はただ維持するつもりです あなたは、最終的には、までを通じて実行されています でソートされた配列を取得 2、3、4、5、及び6は全てソートされます。 誰もが論理を理解して 選択ソートがどのように動作するかの？ あなただけのいくつかの並べ替えを持っています 最小値。 あなたはそれが何であるかを追跡することです。 あなたはそれを見つけるたびに、あなたがそれをスワップ array--の最初の値を持ちます または、ない最初va​​lue-- 配列内の次の値。 クール。 だから君たちのような種類の 簡単な垣間見るから見て、 我々はこれを擬似コードするつもりです。 だから後ろに君たちがしたい場合は テーブルの皆さん、グループを形成 少し相手を形成することができる、私は行きますよ あなたの3分のような連中を与えるために ちょうどを通して話をします ロジック、英語で、 我々は、実施することができるかもしれないのか 選択ソートを書き込むための擬似コード。 そして、お菓子があります。 出てくるとお菓子をゲットしてください。 あなたが後ろにいる、あなたがしたい場合 キャンディは、私はあなたにお菓子を投げることができます。 実際、you--クールを行います。 あ、ごめんなさい。 OK。 だから私たちのように、したい場合 クラス、書き込み擬似コード 一つは近づくかもしれない方法について この問題は、単に自由に感じます。 私は周りに行くとよ、 ために、グループを尋ねます の次の行のための 私たちは何をする必要があります。 だからみんなが起動する場合 オフ、最初のものは何ですか あなたがしようとしているときに実行します このプログラムを解決する方法を実装 選択リストをソートするには？ ちょうど私達を仮定しましょう 配列、すべての権利を持っていますか？ 観客：あなたはいくつかを作成したいです 並べ替え[聞こえない]あなたがしていること あなたの全体の配列を介して実行しています。 ANDI PENG：右。 だから、反復処理したいとしています すべての空間を介して、右か？ だから、素晴らしいです。 あなたたちは私に与えたい場合 次の後ろに、ええline--。 聴衆：それらをチェック すべての最も小さいため。 ANDI PENG：そこに私達は行きます。 だから我々は通過し、にチェックしたいです 右、最小値が何であるかを参照してください？ 私はにそれを短縮するつもりだ "分" あなたたちは、後にはどのように過ごしたいです あなたが最小値を見つけましたか？ 聴衆：[聞こえません] ANDI PENG：だからあなたがしたいとしています その配列の最初でそれを切り替えて、 右？ それは私が言うつもりだ、始まりです。 大丈夫。 だから今、あなたが最初にスワップしたこと 1、あなたはそれの後に何をすべきかをしたいですか？ だから今、私たちはここで、このいずれかを知っています 右、最小値でなければなりませんか？ その後、追加の残りの部分を持っています ソートされていないのです配列の。 だから場合は、ここで何をしたいのか みんなは私に次の行を与えたいと思いますか？ 観客は：だから、あなたは反復したいです 配列の残りの部分を通って。 ANDI PENG：うん。 だから何が繰り返し処理ん 種類の我々は、おそらく必要があります意味するものでは？ どのようなタイプof-- 聴衆：ああ、追加の変数？ ANDI PENG：おそらく 別のループのために、右？ だから我々は、おそらくするつもりです through--偉大を反復します。 そして、あなたが戻って行くつもりです おそらく再び最小値をチェックし、 右？ そして、あなたは繰り返し続けるつもりです この、ループがちょうど行くので、 右、走り続けるには？ だから、あなたたちは、私たちを見ることができるように ただ、一般的な擬似コードを持っています 私たちはこのプログラムを見てみたいかの。 これはここで繰り返す、我々は何をすべきか 一般的に私たちのコードで記述する必要があります 私たちはを反復処理する場合 構造体の配列、どのタイプ？ 私はクリスタベルを考えます すでに、これは前にも言いました。 聴衆：forループ。 ANDI PENG：forループのA？ その通りです。 だから、これはおそらくです ループのためになるだろう。 暗示するつもりはここでチェックとは何ですか？ 通常、チェックしたい場合は 何かが何かある場合else-- 聴衆：もし。 ANDI PENG：アン場合、右？ ここスワップそして、我々はよ 後で越える、デビッドので、 同様に講義のそれを通り抜けました。 そして、第二の反復implies-- 聴衆：ループのための別。 ANDI PENG：正確には、forループ--another。 だから私たちは探しているなら 正しくこの時、我々 我々は、おそらくしていることがわかります ループのネストされたが必要になります そこには条件文と コー​​ドのと、実際の作品 値を交換する予定。 だから、僕は、一般的に書いています ここで擬似コードコード。 そして、我々は実際に行っています 物理的に、クラスとして、 今日はこれを実装してみてください。 それでは、このIDEに戻りましょう。 おっと。 なぜそこnot--それがあるということです。 OK。 申し訳ありませんが、私はもう少しでズームしてみましょう。 そうしよう。 私はここでやっているすべては私が作成したあ​​ります 呼び出されたプログラム「選択/ sort.c。」 私は9の配列を作成しました 値は、4、8、2、1、6、9、7、5、3。 現時点では、することができますように 彼らは順序付けられていない、参照してください。 nが、その数になるだろう あなたの値の量を指示します あなたの配列を持っています。 ここでは、9つの値を持っています。 そして、私はちょうどここにループのため持っています それは、ソートされていない配列を出力します。 そして最後に、私はまたのために持っています もう一度それをプリントアウトするループ。 だから理論的には、このプログラムの場合 最後に、正しく動作しています、 あなたはループのために印刷表示されるはずです これは1、2、3、4、5、6、7、8、 図9は、ために、すべて正常です。 だから我々はここで私たちの擬似コードを持っています。 私はちょうどよto--誰もが欲しいん volunteers--を求めるに行くつもり 場合入力する正確に何を教えて 我々は、まず、単に反復したいです この配列の先頭を介して？ 私はコードの行は何ですか おそらく、ここで必要になるだろうか？ 聴衆：[聞こえません] ANDI PENG：ええ、感じ あなたは、残念to--無料 up--感触を我慢する必要はありません あなたの声ビットを上げて自由。 聴衆：int型のために私が等しく0-- ANDI PENG：うん、良いです。 聴衆：私は、配列の長さよりも小さいです。 ANDI PENG：だからでおきます 我々ので、ここでは気に その機能を持っていません 私たちの配列の長さを指示し、 我々はすでに持っています それを格納した値。 右？ もう一つは、維持します 配列内のmind--で 9つの値のうち、インデックスは何ですか？ ちょうどこの配列は、0〜3であったとしましょう​​。 あなたは最後のことを見ます インデックスは、実際には3です。 それはそこだとしても、4ではありません 配列の4つの値。 そこでここでは、我々は非常に注意する必要があります 長さのためにどのような私たちの条件の なるだろう。 観客は：それは、nマイナス1になると思いませんか？ ANDI PENG：それが起こっています ちょうどnマイナス1、。 そのメイク感覚、なぜ それは、みんなのnはマイナス1？ 配列はゼロがインデックスされているからです。 彼らは、0から開始し、1からnマイナスまで実行します。 ええ、それは少しトリッキーです。 OK。 その後 - 聴衆：Isnt'1こと すでにかかわらの世話をし、 単に "より小さいかを言っていないことにより、 等しい」とだけ言って「より小さい？」 ANDI PENG：それは 本当に良い質問です。 だから、はい。 しかし、また、私たちがしている方法 チェック権利を実装し、 あなたは、2つの値を比較する必要があります。 だから、実際にしたいです 」を「空のままにしておきます。 あなたは比較する場合ので、 これは、あなたがつもりはありません それの後に何を持っています 右に比較するには？ うん。 だから私は++しました。 それでは、私たちの中にブラケットを追加してみましょう。 おっと。 グレート。 だから我々は始まりを持っています 私たちの外側のループの。 だから今、私たちはおそらくしたいです 維持するための変数を作成 最小値のトラック、右？ 誰も私に与えたいと思うん それを行うことになるコードの行？ 私たちが行っている場合は、私たちは何が必要です 何かを保存するには？ 右。 そのためたぶん良い名前 「TEMP」は全くworks-- be--う 多分より適切になるであろうという名前の、 私たちは最小value--が必要な場合 聴衆：ミン。 ANDI PENG：分、そこに私達は行きます。 minが良いでしょう。 だからここで、我々は何をすべきか それを初期化したいですか？ これは少しトリッキーです。 そのため、今で この配列の先頭、 あなたは正しい、何を見ていませんか？ それで自動的に何、あれば 我々は、ちょうど私が0に等しいにしています 我々は、初期化するために何をしたいです に私たちの最初の最小値はありますか？ 聴衆：私。 ANDI PENG：私、丁度。 クリスタベル、なぜ私たちがしたいです 私にそれを初期化するには？ 聴衆：よく、そのため、 我々は0で開始しています。 だから我々は、比較することは何もありませんので、 それは、最小値は0になってしまうでしょうします。 ANDI PENG：その通り。 そこで彼女は、まさにそうです。 私たちは実際には持っていないので まだ何も見て、 私たちは最小値が何であるかを知りません。 私達はちょうどそれを初期化します 私は、これは、現在、右ここにあります。 そして、私たちはし続けています この配列を下に移動、 私たちは、それぞれに、それを参照してくださいよ 追加のパス、私は増加します。 だからその時点で、 私はおそらく起こっています 最小になりたいために、 それはどのようなことになるだろうので、 ソートされていない配列の始まりです。 クール。 だから今、私たちは追加したいです それだ、ここでループのために 反復処理しようとして ソートされていない、またはこの配列の残りの部分。 誰も私に与えたいと思うん それを行うことになるコードの行？ Hint--我々はここで何を下に必要なのでしょうか？ 何ループのためにこれに行くために起こっているのですか？ うん。 聴衆：だから我々がしたいと思います 異なる整数値を有します 我々は残りを実行しているので、 配列の代わりに私、ので、多分 J。 ANDI PENG：うん、jは私にはいいですね。 等しいですか？ 聴衆：だからので、私プラス1になります あなたは、次の値で開始しています。 そして、そのように再びend--に、jがあります nはマイナス1、次にJ ++未満。 ANDI PENG：グレート。 そしてここで、我々はするつもりです 私たちの条件が満たされるかどうかを確認するために、 右？ あなたがしたいので、 最小値を変更します それは何よりも実際に小さいだ場合 あなたは正しい、それを比較していますか？ それでは、私たちはここで必要としていますか？ 確認してください。 文のどのような種類 我々は、おそらく行きます TIは、私たちならば利用したいです 何かを確認したいですか？ 聴衆：if文。 ANDI PENG：if文。 だからif--となるように何が起こっていますか 我々は内側する条件 私たちのif文の？ 者：jの値の場合 i--の値よりも小さいです ANDI PENG：その通り。 だからif--ので、この配列には、「アレイ」と呼ばれています。 グレート。 その場合はそれが何でしたかarray--？ もう一度言って。 対象：配列-jは未満である場合 配列-iは、我々は分を変更します。 だから分がjになります。 ANDI PENG：意味がありますか？ OK。 そして今ダウンここで、実際に我々 右、スワップを実現したいですか？ それでダビデは、ときに、講義では、リコール 彼が何であったかthe--を交換しようとしていました オレンジジュースit--とmilk-- 聴衆：グロスでした。 ANDI鵬：ええ、それはグロスのようなものでした。 しかし、それはかなり良かったです 概念は、時間を実証します。 だからここに自分の価値観を考えます。 あなたは配列を持っています 分の、私の配列、 または何でも私たちはここで交換しようとしていました。 そして、あなたはおそらくにそれらを注ぐことができません 同時に互いに、右？ だから我々は何を行っています ここで作成する必要がありますするには 正しく値を交換するためには？ 聴衆：一時変数。 ANDI PENG：一時変数。 それでは、int型の温度を行うことができます。 参照してください、これは良いだろう ちょっと待ってto--時間は、それは何でしたか？ OK。 だから、これはもっと良かったはずです 変数名には時間 "一時を。」 それでは、int型の温度を行うことができます。 私たちがしようとしています ここに等しく設定の一時？ 聴衆：ミン？ ANDI PENG：それは少しトリッキーです。 これは、実際に最終的には関係ありません。 これは、何が問題ではありません。 順序をスワップすることを選択します 限り、あなたはあなたがしている作っているよう あなたがスワッピングしているものを追跡します。 観客：それは配列-iの可能性があります。 ANDI PENG：うん、の配列-Iを行うことができます。 そして、次の行は何ですか コー​​ドの私たちはここに持っていたいですか？ 聴衆：配列-iは、アレイ-Jに等しいです。 ANDI PENG：そして最後に？ 聴衆：配列-jは、アレイ-Iに等しいです。 聴衆：または配列-Jイコール アレイtemp--または、一時。 ANDI PENG：[OK]をクリックします。 それでは、これを実行して見てみましょう それが動作するように起こっている場合。 ことはどこに起こっているのでしょうか？ ああ、それが問題です。 私たちがしている、ライン40上に、参照してください。 配列-Jを使用しようとしていますか？ しかし、ここでjはのみに存在していますか？ 聴衆：forループで。 ANDI PENG：右。 だから、私たちは何をする必要がありますするつもりですか？ 聴衆：the--外に定義します 聴衆：ええ、私はあなたが持っていると思います if文の右、別のものを使用するには？ だからのような、場合minimum-- すべての権利、私は考えてみましょう。 ANDI PENG：みんな、みてください 外観レッツを取ります 我々はここで行うことができるものです何を参照してください？ 聴衆：[OK]をクリックします。 だから、最小値が等しくない場合 最小である場合にj--のでまだi-- その後、我々は交換する必要がありません。 ANDI PENG：それ同等の私はいますか？ 何がここで言いたいのですか？ 聴衆：またはええ、もし 最小値はええ、私と同じではありません。 ANDI PENG：[OK]をクリックします。 まあそれは、この種の、私たちの問題を解決します。 しかし、それはまだ解決していません。 J以来j--場合に何が起こるかの問題 何、それの外に存在しません あなたは私たちがそれをどうしますか？ 外それを宣言？ それでは、このを実行してみましょう。 おっと。 私たちのソートが機能していません。 あなたは、私たちの最初のを見ることができるように 配列は、それらの値を持っていました。 そして、その後それが持っている必要があります 1、2、3、4、5、6、7、8、9であっ。 それは働いていません。 ああ。 私たちは何をしますか？ 聴衆：デバッグ。 ANDI PENG：すべての権利、私たちはそれを試すことができます。 私たちは、デバッグすることができます。 少しズームアウト。 私たちのブレークポイントを設定してみましょう。 のがOK like--行きましょう。 だから我々はすでにそれを知っているので、 これらの線、15〜22、 私がやっているすべてであるためworking--されています ちょうどを反復処理し、printing-- 私が先に行くとそれをスキップすることができます。 ライン25で開始してみましょう。 OOPは、私はそのを取り除くましょう。 聴衆：だからブレークポイントの デバッグが始まりますか？ ANDI PENG：または停止しました。 聴衆：または停止しました。 ANDI PENG：うん。 あなたは、複数のブレークポイントを設定することができますし、 それだけで一方から他方へジャンプすることができます。 しかし、このケースでは、我々は知りません どこでエラーが起こっています。 だから我々はちょうどしたいです トップダウンからのスタート。 うん。 OK。 そこでここでは、この行は、我々がでステップ実行することができます。 あなたは、ここでダウンして見ることができます 我々は配列を持っています。 それらは値であり、 アレイ内にあること。 あなたが、どのようにインデックス0、それ参照しています ああvalue--に対応し、 私はズームインしようとするつもりです。 申し訳ありませんが、それは本当に難しいです 配列のインデックス0でsee--します、 我々は、4の値を有し、そして その後、などのように。 私たちは、ローカル変数を持っています。 今、私はに等しいです。 我々はそれになりたい0、。 そしてそうのが通過ステッピング維持させます。 私たちの最小値は0に等しく、 これは私たちもそれになりたいです。 そして、私たちは私たちの第二を入力してください ループ配列-jは配列-Iよりも小さい場合、 これはそうではありませんでした。 だから、どのように見ました それはその上をスキップ？ 聴衆：だからべきか 最低限、すべてのthat--べきではないこと ループの最初の内側にありますか？ ANDI PENG：いいえ、なぜなら あなたはまだテストしたいです。 あなたは、すべての比較をしたいです 時間、あなたはそれを介して実行した後でも。 あなたはそれを行うにはしたくありません 最初のパス・スルーに。 あなたはでそれをやってみたいです 再び各追加パス。 だからかどうかを確認したいです 内部のあなたの状態。 だから我々はちょうどしようとしています ここを走り続けます。 私はあなたたちにヒントを与えるでしょう。 それは時という事実に関係しています あなたは、あなたの条件をチェックしています あなたがチェックしていません 正しいインデックスの。 だから、今あなたがチェックしています jの配列インデックスが配列よりも小さいです 私のインデックス。 しかし、あなたはで何をやっています forループの始まり？ あなたは私に等しいJを設定していませんか？ ええ、私たちは実際にすることができます ここで、デバッガを終了します。 それでは、私たちの擬似コードを見てみましょう。 我々はするつもりですFor-- 私は0に等しいから始まります。 私たちは、1からnマイナスまで行くつもりです。 それでは、確認してみましょう、我々は正しいことをしていたのですか？ うん、それは正しかったです。 それでは、ここで内側に、私たちはしています 最小値を作成するつもり 私にそれが等しくなるように設定。 我々はそれをしましたか？ うん、それをしました。 現在、私たちの内側のためのループでは、我々はしています Jをするつもりは、iがnはマイナス1に等しいです。 我々はそれをしましたか？ 確かに、我々はそれをしました。 だからしかし、我々はここで何を比較していますか？ 聴衆：Jプラス1。 ANDI PENG：その通り。 そして、あなたが設定したいとしています Jプラス1と同様に等しいあなたの最小値。 だから私は本当にすぐにそれを経​​験しました。 あなたたちは理解しています なぜそれがjプラス1ですか？ OK。 だからあなたのアレイでは、中 あなたの最初のパス、 あなたのループのために、int型のため 私は0に等しい、ちょうどしてみましょう これはまだ変更されていないと仮定します。 我々は、完全に、の配列を有します わずか4ソートされていない要素は、右？ だから私たちは私が0に等しい初期化したいです。 そして、私はちょうどしようとしています このループを実行します。 だから最初のパスでは、我々が行っています "分"と呼ばれる変数を初期化します そのためにも、私に等しいです 私たちは、最小値を持っていません。 だから、同様に0に現在と同じです。 そして、我々が通過しようとしています。 そして、私たちは再び反復したいと思います。 今、私たちは見つけたことをどのような私たちの最小 我々は反復処理したいです それは右、比較だ場合には、再度参照してくださいするには？ だからjは、ここでは、起こっています 同じ私に、0です。 そして、アレイJプラス私の場合、これは 以下のように、次の終わったものです 何あなたの現在の最小値よりも 値はあなたが交換したいです。 それでは、ちょうど私達がしたとします。 2、5、1、8、のようになりました。 今、私はに等しいです。 0およびjは0に等しいです。 そして、それは私たちの最小値です。 配列-Jの場合プラスi-- 1もしそうであれば それは、私たちが見ているものの後です それ以前に1よりも大きいです、 それが最小となるだろう。 そこでここでは、5ていることがわかり それ以上です。 だから、5にならないだろう。 我々は右、1が2未満であることを確認？ だから今、私たちは私たちの最小であることを知っています 0、1、2のインデックス値になるだろう。 うん？ そして、あなたはここに降りたときに、 あなたは正しい値を入れ替えることができます。 だから、あなたたちはただJを持ったとき、 前に、1つを見ていませんでした それの後。 あなたが見ていました 同じ値が、その それだけで何もしていなかった理由です。 それは誰にでも意味がありますか、 なぜ我々がそのプラス1が必要？ OK。 それでは、ただ作るためにそれを介して実行してみましょう 必ず残りのコードは正しいです。 それはなぜ起こっているのでしょうか？ ああ、それはここ分です。 我々は間違った値を比較しました。 ああ、いや。 そうそう、ダウンここではなかったです 同様に誤った値を交換します。 我々は、iとjを見ていたので。 これらは、私たちがチェックされたものです。 私たちは、実際に交換したいです 最小、現在の最小値、 何で1外です。 そして、あなたたちがダウンして見ることができるように ここでは、ソートされた配列を持っています。 それはちょうどとしなければなりませんでした その事実 我々はチェックし、 我々が比較された値、 我々は正しい値を見ていませんでした。 私たちは、同じものを見ていました ここで、実際にそれをスワップありません。 あなたは次のものを見ています それにしてから、交換することができます。 だから、一種のだったものです 前私たちのコードを盗聴。 そして、私はここでやったことはすべてです デバッガはあなたのために行っている可能性が 私はちょうどにそれをやりました ボード、それは簡単ですので、 しようとするのではなく、確認してください デバッガにズームインします。 それは誰にでも意味がありますか？ クール。 大丈夫。 私たちは話してに進むことができます 漸近記法、これ 言うだけの空想の方法です これらの種類のすべてのランタイム。 だから私は講義で、ダビデを知っています、 ランタイム時に触れました。 そして、彼は全体の式を経て 実行時間を計算する方法。 そのことについて心配はありません。 あなたは本当に好奇心旺盛であれば それがどのように機能するかについて、 セクションの後に私に話をして自由に感じます。 私たちは、ウォークスルーすることができます 一緒に式。 しかし、すべてあなたたちは本当に必要な 知っている、nが2の上に乗ということです nが乗と同じことです。 最も多くあるため、 指数は、最も成長します。 だから、私たちの目的のために、 私たちは気にすべて 成長しているということ巨大な数です。 だから何が最善のケースです 選択ソートの実行時？ あなたが必要があるとしている場合 リストを反復します して、反復処理 そのリストの残りの部分、 何回あります あなたは、おそらくに行きます 最悪case--で 最良の場合は、を介して実行しますかsorry--？ たぶん良い質問です 聞いて、最悪の場合何であります 選択ソートの実行時間。 聴衆：nの二乗。 ANDI PENG：それはnは、右の二乗です。 だから、これを考えるための簡単​​な方法は、似ています あなたは、ループのための2つのネストされている任意の時間、 それは、n乗することになるだろう。 あなたがしているためだけでなく、 再び通ります、 あなたが戻って行かなければなりません 周りとそれを介して実行します もう一度すべての値のための内部。 だから、その場合には、あなたは、nを実行しています n倍、申し訳ありませんis--れ、乗 n回N、N-二乗等しいです。 そして、ソートも少しあります 意味でユニーク これらの場合、それは問題ではないこと 値が順番に既にあります。 それはまだとにかく介して実行するために起こっています。 ちょうどこれは1、2、3、4であったとしましょう​​。 かかわらずであったか否か 順序は、それはまだ通って走っているだろう まだ最小値をチェックします。 それはいただろう チェックの同数 毎回、でもそれならば 実際には何も触れていません。 だから、このような場合には、最高の最悪 ランタイムは、実際には等価です。 そこで期待されるランタイム 選択ソートの、 これは、我々は記号で指定します シータの、シータ、この場合には、 また、N乗されることになります。 これらのすべての3つは、n乗されることになります。 理由の誰もが明確です ランタイムは、n乗のですか？ 大丈夫。 だから、僕はすぐに実行するつもりです ある種の残りを。 以下のためのアルゴリズム バブルは、覚えてsort-- これは最初のものでした ダビデは講義に渡りました。 基本的には、ステップ リスト全体を通じ あなたはちょうどあなたがswap-- 一度に2つを比較します。 そして、もう一つの大きい場合は、 あなたよりも、単にそれらを交換。 これらは大きいのであれば、あなたは交換します。 私はここの公式持っています。 それでは、あなたが8、6、4、2を持っていたとしましょう​​。 あなたは8と6を比較すると思います。 あなたはそれらを交換する必要があると思います。 あなたは8と4を比較します。 あなたはそれらを交換する必要があると思います。 あなたは8を交換する必要がある場合と 2、同様にそれらを変更します。 だから、そのような意味で、あなたは、見ることができます 長期間にわたって演じ、 どのようにバブルの値は親切に 我々はそれを呼んで終了し、 バブルソート。 私達はちょうど上で再びを通じて実行されます 私たちの第二のパス、と私たちの3番目のパス、 私たちの4パス。 本質的には、バブルソートだけで実行されます あなたまで、それ以上のスワップを行いません。 だから、そういう意味では、これはただです それのための一般的な擬似コード。 心配しないで、これらはすべてオンラインになることはありません。 私たちは、実際にこの上を行く必要はありません。 私達はちょうどカウンターを初期化します 0から始まり、変数。 そして、我々は全体の配列を反復処理。 そして、この場合は、1つの値がis--場合 値は、その値よりも大きいです あなたはそれらを交換するつもりです。 そして、あなただけです 続けるつもり。 そして、あなたはカウントするつもりです。 そして、あなたはただやり続けるつもりです このカウンタは大きいながら ことを意味よりも0、 毎回あなたが交換する必要があり、 あなたが行きたい知っています バックして再度確認してください。 あなたが知っているまでチェックを維持したいです あなたはもう交換する必要がありません。 だから最善と最悪のものです ケースは、バブルソートのためのランタイムを？ そしてhint--これは実際に異なっています 意味での選択ソートから これらの2つの答えは同じではないこと。 中に何が起こるかを考えてみて それはすでにソートされている場合場合。 そして、何について考えます それがあった場合はどうなります ケースでは、ソートされませんでした。 そして、あなたは一種の実行することができます なぜを通じてそれが起こっています。 私は、30のように、君たちをあげます それについて考える秒。 OK。 誰もがどのように推測を持っています バブルソートの最悪の場合の実行時間はありますか？ うん。 聴衆：それは、のように、n回だろう nはマイナス1またはそのような何か？ 同様に、それが実行されるたび、 それは1スワップ以下のような、ちょうどです どんなことがありました。 ANDI PENG：うん、そう あなたは完全に正しいです。 そして、これはであなたのケースであります 答えは実際にはより複雑でした 1よりも我々が与える必要があります。 だから、私はrun--になるだろう ここでこのすべてを消去する予定。 誰もが良いですか？ 私はこれを消去することはできますか？ OK。 あなたは、nを介して実行するつもりです 回初めて、右？ そして、彼らは介し​​て実行するつもりです nはマイナス1秒の時間、右か？ そして、あなたは維持するつもりです 行く、nは鉱山2、エトセトラ。 ダビデはどこに、講義でこれをやりました、 あなたはすべてのそれらの値を追加した場合、 あなたが何かを得ますlike-- yeah-- 基本的にだけ削減され、2オーバー までのn乗。 あなたが取得するつもりです そこに奇妙な割合。 そして、これだけのことを知っています nが常に乗 割合よりも優先されます。 ので、この場合には、最悪の ランタイムは、n乗されることになります。 それが降順にあった場合 ため、思う、あなた スワップ毎回行う必要があります。 潜在的に、何だろう、 最良の場合ランタイム？ リストがすでにあった場合は、ちょうど言ってみましょう ためには、ランタイムは何でしょうか？ 聴衆：N。 ANDI PENG：それはまさに、n個です。 そして、なぜそれがn個ありますか？ 聴衆：あなただけのため、 各一度にチェックする必要があります。 ANDI PENG：その通り。 だから、可能な限り最高のランタイムで、 このリストには、すでにあった場合 あなたは4--、のは1、2、3を言わせsorted-- ちょうどあなたがチェックする、通過だろう、 あなたは彼らのすべてが出てパン、ああ、見ることになります。 私は交換する必要はありませんでした。 私はこれで終わりです。 だから、その場合には、それだけのn ちょうどまたはステップの数は、 最初のリストで確認しなければなりませんでした。 そして、後に我々は今ヒット 挿入ソート、 このアルゴリズムは、本質的に分割することです それソートし、ソートされていない部分に。 そして、一つ一つ、 ソートされていない値は、 それらの適切なに挿入 リストの最初のポジション。 したがって、たとえば、私たちは持っています 再び3、5、2、6、4のリスト。 我々は、それが現在だことを知っています ソートされていない私たちはただたので それを見て始めました。 私たちは見て、我々はことを知っています 最初の値は、右のソートされて？ あなただけの配列を見ている場合 サイズ1、あなたはそれがソートだことを知っています。 だから我々はことを知っています 他の4つは、ソートされていないです。 我々は通過し、我々はその値を参照してください。 それでは、戻りましょう。 5の値を参照してください？ 我々はそれを見てみましょう。 我々は3と比較します。 我々は、それがより大きいだことを知っています 3、私たちはそれがソートされたということを知っています。 だから我々は今、最初の二つのことを知っています ソートされ、最後の3つがありませんされています。 私たちは2を見てみましょう。 我々は最初の5でそれを確認してください。 それが5未満のですか？ そうではない。 だから我々は見下ろして維持する必要があります。 その後、3から2をご確認ください。 それはより少ないですか？ いいえ。 だから、2を挿入する必要があります知っています フロントに3と5 両方が押し出されなければなりません。 6と4で再びこれを行います。 そして、私たちはただ、基本的にチェックしておきます ここで私たちは、チェックチェック、チェックしてください。 そして、それは右になるまで 位置、我々の種類のちょうど 正しい位置に挿入し、 それの名前はどこから来たのです。 だから、それはただのアルゴリズムですが、 擬似コード自体、一種の、 我々が実装する方法について 挿入ソート。 擬似コードはこちらです。 これは、すべてのオンラインです。 心配ない君たちがある場合 これを下にコピーしようとしています。 だからもう一度、同じquestion--何 最良と最悪のランタイムになります 挿入ソートのために？ それは、最後の質問に非常によく似ています。 私は、30のように、君たちをあげます 同様にこのことについて考える秒。 誰もがしたいん[OK] 私は最悪のランタイムを与えますか？ うん。 聴衆：nの二乗。 ANDI PENG：それは、n乗です。 そして、なぜそれがn個の二乗のですか？ 聴衆：であるため 順序を逆に、あなたが持っています is--れ、n回を経るNに ANDI PENG：うん、まさに。 バブルソートのようにだから同じこと。 このリストは、内にある場合 降順、あなたがしています 最初の一度をチェックしているつもり。 そして、すべてのと 付加価値、あなたがしています それをチェックしているつもり 右のすべての単一の値、？ だから完全に、あなたはするつもりです n個のパスの時間は、他のnは、通過します nが2乗さ。 何最良の場合はどうですか？ うん。 聴衆：nはマイナス1、理由 最初のものは、すでに2乗さ。 ANDI PENG：だから、近接しています。 その答えは、実際にはnです。 最初のものであるのに対しので、 並べ替え、それをactually--ない場合があります 私達はちょうどで、運が尽き その例、その2 最小数であることが起こりました。 しかし、それは必ずしもそうではありません。 図2は、すでに最初にソートされている場合 しかし、あなたは、見て、ここで1あります 1はそれをバンプする予定です。 そして、それが終了になるだろう とにかくぶつかっさアップ。 そのように最良の場合のシナリオにおいて、 それは実際にはn個になるだろう。 あなたが持っている場合は1、2、3、 4、5、6、7、8、あなたがいます 介して実行しようとして 一度そのリスト全体 すべてが正常かどうかを確認します。 ランニングの全員が明確にされています 同様に選択の時代？ 私が通って行くよ知っています これらの本当に速いです。 しかし、ちょうどあなたが知っていればことを知っています 一般的な概念は、あなたが良いことがあります。 OK。 だから私はちょうどのように、多分君たちを与えるでしょう、 あなたの隣人に話をする分 ちょうどいくつかであるものに 主な相違点の ある種のこれらのタイプの間。 我々はすぐにその上を行きますよ。 聴衆：ああ、[OK]をクリックします。 ANDI PENG：うん。 OK。 クール、のクラスとして再召集しましょう​​。 OK。 だから、これはあったような 意味でオープンエンドの質問 それらへの回答の多くがあること。 そして、我々は簡単にそれらのいくつかの上に行きますよ。 私はちょうどあなたたち取得したいです 差別何を考えます ある種のすべての3つのタイプ。 そして、私は偉大な、また、聞きました 何をするマージソートんquestion--？ グレート質問、それはだから 私たちは次のカバーしています。 だから一種であるマージ その機能一種 非常に異なる他の種類から。 君たちはsee--ように ダビデはそのデモを行いました 彼はすべてのクールなを持っていたところ マージ方法を見てのノイズ ソート無限に、のように、走りました 他の二つのタイプよりも速いですか？ OK。 だから、マージためです ソートその格差を実装 私たちはきた概念を征服 講義で多くについて話しました。 私たちが仕事をしたいという意味で あなたが分裂するとき、難しく、賢くありません 及び問題を克服し、それを破ります ダウンし、その後、それらを一緒に置きます 良いものは常に起こります。 マージだから方法 ソート基本的に動作します それが分割していることです 半分にソートされていない配列。 そして、それは配列の2つの半分を持っています。 そして、それはちょうどそれらの二つの部分をソートします。 それはちょうどで、半分に分割し続けます 半分、半分にすべてがソートされるまで して、再帰的に 一緒にすべてを置きます。 だから、本当に抽象です。 だから、これは擬似コードの少しだけです。 それはに意味がありますか それが実行している方法はありますか？ それでは、あなたが持っているとしましょう n個の要素の配列は、右？ nが2未満である場合は、返すことができます。 あなたが知っているので、それがあるかどう 唯一の事は、それをソートする必要があります。 そうでなければ、あなたは左半分をソートし、 そして、あなたは右半分をソートし、 そして、あなたはマージします。 だから、本当に簡単に見えますが、 現実には、それについて考えることです 難しいの一種。あなたが似ているので、 まあ、それはそれ自身で実行されているのようなものです。 右？ それはそれ自身で実行されています。 だから、その意味で、ダビデは触れ クラスの再帰に依存します。 そして、それは考え方です 我々はより多くの話をします。 なお、このことは、これらの2つのラインです ここでは、実際にはプログラムであり、 自分自身を実行するように伝えます 異なる入力を持ちます。 そうではなくて自分自身を実行します n個の要素の全体を、 あなたがにそれを打破することができます 左半分と右半分 し、再度実行してください。 そして、我々は、視覚的にそれを見てみましょう 私は視覚的な学習者だから。 それは私のために適しています。 そこで、ここでは視覚的な例を見てみましょう。 6、我々は配列があるとしましょう 要素、3,5、2,6、4,1、ソートされません。 すべての権利は​​、このページのたくさんあり​​ます。 だからみんなが見ることができる場合 ここで、第一段階、3,5、2,6、4,1、 あなたはそれを半分に分割することができます。 あなたは3,5、2,6、4,1を有しています。 あなたはこれらがあなたをaren't--ことを知っています 彼らはソートまたはしていない場合はわからないが、 あなたは半分に、それらを破壊し続けます、 半分に、半分に、最終的になるまで、 あなただけの1要素を持っています。 そして、もう一つの要素は常に正しい、ソートされていますか？ だから、私たちは知っている3、5、2、4、6、 1は、それだけではソートされています。 そして今、我々はそれらを一緒に戻すことができます。 だから我々は3,5を知っています。 私たちは一緒にそれらを置きます。 私たちは、それがソートされたことを知っています。 まだそこに2の。 私たちは一緒に4と6を置くことができます。 我々は、それがソートだことを知っています 私たちは一緒にそれを置きます。 1があります。 そして、あなただけを見て 右ここで、これらの二つの部分。 あなたは3,5、2、2、3、5を有しています。 あなたは比較することができます すべての始まり。 あなたはこれがソートされていることを知っているので あなたはそれがソートだことを知っています。 それでは、あなたもする必要はありません 5を比較し、あなただけの3を比較します。 及び2は、3未満であります あなたは2が最後に行かなければならない知っています。 あそこ同じこと。 図1は、ここに行く必要があります。 そして、あなたが入れて行くとき 一緒にこの2つの値、 あなたはこれがソートされていることを知っていて、 あなたはそれがソートされていることを知っています。 それでは、1と 図2において、1は2未満です。 それは1ことを示しています これの最後に行くべき でも、3または5を見ず。 そして4、あなただけのことができます チェック、それはここで右に行きます。 あなたは5で見てする必要はありません。 6と同じこと。 あなただけ6--ことそれを知っています 見てする必要はありません。 だからそのように、あなたがしています 自分だけを保存します あなたが比較している手順の多く。 あなたはすべてを比較する必要はありません 他の要素に対して要素。 あなただけのものと比較 あなたはに対してそれを比較する必要があること。 だから、抽象的な概念のようなものです。 そうでない場合は心配ありません かなり右まだあなたを打ちます。 一般的に、これは どのようにマージソートが動作します。 質問、迅速なご質問、 私は上に移動する前に？ うん。 聴衆：だからあなたはあなたが取ることを言いました 1、次いで4、及び図6 とに入れて。 だからthose--ではありませんされていません あなたはそれらを見て 別々の要素としてではなく、全体として？ ANDI PENG：うん。 だから、何が起こっていますか あなた、それは基本的に ブランドの新しい配列を作成しています。 だから、ここでは、私が持っていることを知っています サイズ3の二つの配列は、右？ だから、知っている私のソートされた配列 6つの要素を有する必要があります。 だから、あなただけの作成します メモリの新しい金額。 だから、ちょっと似ています メモリの無駄であること、 それは問題ではありません。 それは非常に小さいですので。 だから、1を見て あなたは2を見てください。 そして、あなたは1が2未満であることを知っています。 だから、1がで行くべきことを知っています それらの全ての始まり。 あなたもする必要はありません 3と5を見てください。 だから、1はそこに行く知っています。 次に、基本的には1を切り落とします。 それは、私たちに死んだ、のように、です。 その後、我々はわずか2を持っています、 図3、図5、及びその後4,6。 そして、あなたは、あなたのことを知っています 、4と2を比較します ああ、2はそこに行く必要があります。 だから、あなたがそれを切り落とす、2ダウンをウンチ。 だから、あなたはわずか3を持っています そして、4と6の5。 そして、あなたはそれをオフにチョッピング保ちます あなたは配列にそれらを置くまで。 聴衆：だから、ちょうど常にしています [聞こえない]を比較しますか？ ANDI PENG：その通り。 だから、そういう意味では、あなたがしています ただ、基本的に、比較、 他の数に対して1番号。 そして、あなたは知っているので それは、あなたをソートだこと 目を通す必要はありません 数字のすべて。 あなただけの最初のものを見ています。 そしてあなただけのウンチすることができます それらダウン、あなたが知っているので 彼らが属している必要がどこに属しています。 うん。 良い質問。 それから、あなたのいずれかの場合 少し野心的であり、 このコードを見て自由に感じます。 これは実際にあります 物理的実装 我々はマージソートを作成する方法の。 そして、あなたが見ることができる、それは非常に短いです。 背後にでもアイデア それはかなり複雑です。 だから、これを描くように感じる場合 宿題で今夜は、お気軽に。 OK。 ダビデはまた、講義では、この上で行ってきました。 最良の場合どのようなものがあります ランタイム、最悪の場合のランタイム、 そして、マージソートの予想ランタイム？ 数秒だと思います。 これはかなり難しいですが、種類の あなたが考えてみれば、直感的な。 大丈夫。 聴衆：最悪の場合は、nログn？ ANDI PENG：その通り。 そして、なぜそれがnのnを記録しています。 観客：それはないですので、 指数関数的に速くなり、 それは、その機能のようなものです 代わりに、単にnはの 乗か何か？ ANDI PENG：その通り。 だから理由 この上のランタイムは、n個のログです nが、あなたが何であるかbecause--です これらの工程の全てにやって？ あなたはちょうど、それを半分にチョッピングしていますか？ そして、私たちがやっているとき それはやっているすべてのことを、ログ 半分に問題を分割され、 半分に、半分に、より多くの半分インチ その意味で、あなたは親切なことができます 線形モデルを取り除きます 我々は、使用してきたこと。 あなたがチョップ時ので 半分に物事は、それがログです。 それはちょうど、数学的です それを表現する方法。 そして最後に、最後に、あなたがしています 一つだけ最後のパススルーを作ります 右の順序でそれらのすべてを置きますか？ だからあなただけにしている場合 一つのことを確認し、それは、nです。 だから、あなたは親切なのです 2一緒に乗算します。 あなたがその最終的なを持っているようなので、それはです n個のログとここにダウンnのチェック ここまで。 そして、あなたが掛けた場合 彼らは、それがN Nログです。 だから最高のケースと最悪 場合、すべてのnのnを記録していると予想。 それは別の一種のようなものです。 これは、選択ソートのようなものです それその意味で 何あなたの問題ではありません。 リストには、それだけで起こっているのであり、 同じことを一つ一つの時間をすることができません。 OK。 かかわらず、あなたたちが見ることができるように 我々は、n through--行ってきたのソート 乗、それは非常に効率的ではありません。 とにもこのNログnは 最も効率的ではありません。 あなたたちは興味があれば、 ソート・メカニズムがあります 彼らはしているように効率的であること ランタイムではほぼ横ばい。 あなたは、いくつかのログのnを持っています。 あなたは、いくつかのログログのnを持っています。 私たちはそれらに触れないでください このクラスの今。 しかし、あなたたちは好奇心旺盛であれば、 何、Googleにお気軽に 最も効率的な並べ替えのメカニズム。 私はありますが、知りません いくつかの本当に面白いもの、 いくつかは実際にありますlike-- 人々が作る面白いもの。 そして、あなたはどのように疑問に思います 今までそのことを考えて。 あなたには、いくつかのスペアを持っているのであれば、Googleの 時間は、上、いくつかの面白い方法は何ですか それは同様にpeople-- 効率的ways--人 ソートを実装することができました。 OK。 そして、ここだけの便利な小さなチャートです。 私は、そのクイズ0の前に、あなたのすべてを知っています お部屋になりますおそらくしよう それを記憶します。 だから、あなたたちのためにそこにうれしいです。 ただmade--ロジックを忘れないでください なぜこれらの数字が発生しました。 あなたは常に失われている場合は、単に作ります 必ず、種類が何であるかを知っています。 そして、あなたはを通して実行することができます あなたの心の中でそれら なぜそれらを把握します 答えはそれらの答えです。 大丈夫。 だから我々は移動するつもりです 最終的には、検索に、上。 あなたのもののようなので、 誰がPSETを読んでいます、 検索もの一部であります 今週の問題が設定されます。 あなたが実現するように求められます 検索の2種類。 一つは、線形検索で、 一つは二分探索です。 だから、線形探索はかなり簡単です。 あなただけの要素を検索します あなたはそれを得るかどうかを確認するために、リストの。 あなただけを反復処理する必要があります。 そして、それは何かと等しい場合、 あなたはちょうど、それを返すことができますか？ しかし、私たちが最もている1つを 話に興味 バイナリ検索、右は、あります 分割機構を征服します ダビデは講演で実証されました。 電話帳の例を思い出してみましょう 彼が育て続けていること、 彼は一種の苦労1 この1年間のビット、 あなたは半分に問題を分割する場合は、 半分に、半分に、何度も何度も、 あなたが探しているものを見つけるまで？ そして、あなたが持っています その実行時にも。 そして、あなたが見ることができる、それはです 著しく効率的 検索の他の型よりも。 だから、私たちが行くと道 バイナリ検索を実装 で、我々は配列を持っていた場合、 インデックス0〜6、7つの要素、 我々はright--、途中で見ることができます 申し訳ありませんが、私たちの質問であればfirst-- 私たちはの質問をしたい場合は、ありません アレイは、7の要素が含まれています 明らかに、人間であること、およびHAVING このような小さな配列は、それが私たちのために簡単です そう言って。 しかし、方法は、バイナリを実装します 検索は、途中で見えるようになるであろう。 我々は、インデックス3であることを知っています 途中、私たちのため 7つの要素があることを知っています。 何7 2で割りましたか？ あなたは余分な1ことを切り落とすことができます。 あなたが途中で3を持っています。 だから7に等しい3の配列ですか？ それは右、ではないのですか？ しかし、我々は、チェックのカップルを行うことができます。 3 7未満かの配列です 7より大きい3の配列ですか？ そして、我々はそれが7未満だということを知っています。 だから我々は、ああ、それはしなければならない、ということを知っています 左半分にはなりません。 我々は、それがなければならないことを知っています 右半分には、右？ だから我々はちょうど半​​分の配列を切り落とすことができます。 私たちもする必要はありません もうそれを見てください。 我々はそれを知っているので 私たちのproblem--の半分 我々は答えがであることを知っています 私たちの問題の右半分。 だから我々はちょうど今を見てください。 だから今、私たちは見て 残っているものの真ん中。 そのインデックス5。 私たちは再び同じチェックを行います そして我々はそれが小さいということを参照してください。 だから我々はその左に目を向けます。 そして、我々はそのチェックを参照してください。 配列の値ではあり インデックス7に等しい4？ それは。 だから我々はので、trueを返すことができます 私たちは私たちのリストの値を発見しました。 私は通過した方法はありません それは誰にでも意味をなさない？ OK。 私のような、多分君たちを与えるでしょう、 把握するには、3つ、4分 どのようにこれを擬似コードします。 だから私は書くためにあなたに尋ねた想像 返される関数と呼ばれる検索（） 値、ブール値、 それは、本当だったかのようにfalse-- あなたが見つかった場合はtrue 値、あなたがなかった場合はfalse。 そして、あなたがました 値で渡されます 値に探していたました ああ、私は間違いなくarray--入れます 間違った場所にあること。 OK。 とにかく、それは持っている必要があります 値の右側に行きました。 そして、int型のn数であります その配列の要素の。 どのようにしようとしに行きますか でその問題を擬似コードには？ 私はあなたのような人をあげます それを行うには3分。 いいえ、私はonly--あると思います ええ、ここで1右のアップがあります。 聴衆：私はできますか？ ANDI鵬：ええ、私はあなたを得ました。 作業ということですか？ うんいいね。 OK。 すべての権利みんな、私たちがしています でそれを抑制するに行きます。 OK。 だから我々は、この素敵なを持っていると仮定 その中のn個の値を持つ小さな配列。 私は線を描画しませんでした。 しかし、どのように我々は、約行くだろう これを書き込もうか！ 誰もがしたいん 私の最初の行を与えますか？ あなたは私に与えたい場合 この擬似コードの最初の行。 聴衆：[聞こえません] 観客：あなたがしたいと思います through--反復します 聴衆：ちょうど別のループのために？ 聴衆：--for。 ANDI PENG：だからこの1つは少しトリッキーです。 あなたがしたいと思いますabout-- このループを実行し続けるように 何度も繰り返し時まで？ 聴衆：[聞こえない]まで 値は、その値に等しいです。 ANDI PENG：その通り。 だから、実際にはwrite--ことができます 我々は、さらにそれを簡素化することができます。 私達はちょうど、whileループを行うことができますか？ だから、あなただけloop--持つことができます 我々はそれがしばらくだということを知っています。 しかし、今、私は行きますよ 何を通して - "ループ"と言うには？ ループがあるものuntil-- 私たちの終了条件？ 私はそれを聞いたと思います。 私は、誰かがそれを言うのを聞きました。 聴衆：値が真ん中に等しいです。 ANDI PENG：再びそれを言います。 聴衆：または、まで あなたが探している値 ためには、中間値に等しいです。 ANDI PENG：それはそこにない場合はどうすれば？ あなたが検索している場合は、値 ためには、この配列に実際にはないのですか？ 観客：あなたは1を返します。 ANDI PENG：しかし、私たちがしたいですか 我々は条件を持っている場合までループ？ うん。 聴衆：唯一つの値がありますまで？ ANDI PENG：あなたができるループ だから、あなたがしていることを知っていますuntil-- 右の最大値を、持っているつもり？ そして、あなたはあなたが行っていることを知っています 右の最小値を、持っていますか？ また、それが何かだから 私は、前に言うのを忘れました だその何か 二分探索に関する重要な あなたの配列がすでにソートされていることです。 行うための方法はありませんので この彼らはランダムな値をしている場合。 1のの場合は知りません 他よりも大きく、右？ だから、あなたが知っているあなたのmaxと あなたの分、右ここにありますか！ あなたが調整するつもりなら あなたの分とmid--であなたの最大値 ちょうどあなたを仮定しましょう ミッド値は右here--です あなたは基本的に行っています ループあなたの最小になるまで 右、あなたの最大と同じ、または約 あなたの最大は、あなたの分と同じでない場合。 右？ それが起こるとき、あなたがいることを知っているので、 あなたは最終的には同じ値をヒットしました。 つまり、あなたの分まで、ループにしたいです 以下to--は、おっとあります 以下に等しくありません、 最大around--他の方法があります。 それは意味を成していましたか？ 私は、その権利を取得するためにいくつかの試みを取りました。 しかし、ループあなたの最大値まで 基本的にはほとんど少ないです か、最小限に等しく、右？ あなたが知っているときです あなたが収束したこと。 聴衆：ときにあなたの最大のでしょう 値が最小値よりも小さいですか？ ANDI PENG：あなたが続ける場合 それを調整し、これ 私たちが行っているものです この中でやっています。 それは理にかなっていますか？ 最小値と最大値だけです 我々は、おそらくされている整数 維持するために作成するつもり 私たちが見ている場所のトラック。 配列が存在するため、 かかわらず、我々がやっているの。 同様に、我々は実際に物理的じゃありません 右の配列を、オフにチョッピング？ 私達はちょうど調整しています ここで我々は探しています。 それは理にかなっていますか？ 聴衆：うん。 ANDI PENG：[OK]をクリックします。 だから、私たちのループの条件だと、 我々は、このループの内側に何をしたいですか？ 私たちがやりたいと思っされようとしていますか？ だから今、私たちは持っています 最大値と最小値、右、 おそらくどこかにここに作成しました。 我々は、おそらくするつもりです 右、中央を見つけるには？ どのように我々はあることを行っています 中央を見つけることができますか？ 何mathematical-- 聴衆：マックスプラス2で割った分。 ANDI PENG：その通り。 それは理にかなっていますか？ なぜ私たちとあなたたちは見ています 我々はこれをしなかった理由はただuse--ませんでした だけではなく、やってN 2で割りましたの？ nが値であるからです それは同じままになるだろう。 右？ しかし、我々は我々の最小値を調整するとし、 最大値は、彼らが変更しようとしています。 その結果、私たちの真ん中 あまりにも変更する予定です。 私たちが望むだから、なぜです ここでこの権利を行います。 OK。 そして、今では 我々はええour--がわかりました。 聴衆：だけで簡単にquestion-- あなたは最小値と最大値を言うとき、 我々はそれを想定しています それはすでにソートですか？ ANDI PENG：ええ、それは実際にはです 二分探索のための前提条件、 あなたはそれがソートであることを知っている必要があること。 並べ替え、あなたに書く理由であります 問題は、二分探索の前に設定してください。 OK。 だから今我々はどこに私達の中間点を知っていること あなたがここで何をしたいか、何ですか？ 観客：我々は比較したいです 他のものにそれ。 ANDI PENG：その通り。 だから、比較しようとしています 値半ば、右？ そして、それは何を教えてくれありません 私たち私たちは比較すると？ 私たちは、その後何をしたいですか？ 観客：値が大きい場合 半ばより、我々はそれをカットします。 ANDI PENG：その通り。 値が大きい場合にはそう 半ばよりも、私たちはしています これらを変更するつもり 最小値とmaxes、右？ 私たちは、変更したいのですか？ 私たちが知っているのであれば値がどこかにありま​​す ここで、あなたは私たちが何を変更するのですか？ 私たちはを変更したいです 半ば、正しいと最小？ そして、他の、それはこの中だ場合 半分、私たちは、変更したいのですか？ 聴衆：あなたの最大。 ANDI PENG：うん。 そしてあなただけのつもり 右、ループ維持するには？ 今あるので、一回の反復後 あなたはここで最大を持っています。 そして、あなたは半ばを再計算することができます。 そして、あなたは比較することができます。 そして、あなたは続けるつもりです 分、maxesまで 基本的に収束しました。 そして、あなたがいることを知っているときそれはです あなたはそれの終わりをヒットしました。 そして、あなたはそれを見つけたのいずれか または、あなたはその時点で持っていません。 これは誰にでも意味がありますか？ OK。 これはかなり重要であり、 あなたが持っているだろうから コー​​ド今夜でこれを書いてください。 しかし、あなたたちはかなり良いを持っています あなたがやるべきことの意味、 これは良いです。 OK。 だから我々は、約7を持っています 分は、セクションを残しました。 だから我々はについて話をするつもりです 私たちがやっているだろう、このPSET。 だから、PSETは半分ずつに分かれています。 前半は含ま 検索を実装 これであなたは、線形探索、Aを書き込みます バイナリ検索、ソートアルゴリズム。 だから、これは最初のものです ここで、PSETの時間 呼ばれるもの私たちはあなたにみんなを与えることでしょう 配信コード、コードは 我々は、事前に書かれていること、 ちょうどオフいくつかの作品を残しました あなたが書き込みを完了するため。 だからみんな、あなたがこれを見て コー​​ド、あなたは本当に怖いかもしれません。 あなたは、私は、ああ、同じようにしている場合 それはやっているかわかりません、 私のような、それはそう、知りません ああ、リラックス、非常に複雑。 大丈夫です。 仕様をお読みください。 仕様は正確にあなたに説明します これらのプログラムのすべてが何をしています。 例えば、generate.cはプログラムであります それはあなたのpsetが付属します。 あなたが実際にそれに触れる必要はありませんが、 あなたはそれがやっているかを理解する必要があります。 そしてgenerate.c、それはやっているすべてがあります いずれかの乱数を生成します または、あなたは次のように、それにシードを与えることができます それが取る事前に決められた数、 それはより多くの数を生成します。 だから、特有の方法があります ここでgenerate.cを実装 あなただけの数の束を作ることができます あなたは他の方法でテストするため。 だから、あなたがしたい場合のために 例えば、あなたの検索をテストし、 あなたがgenerate.cを実行したいと思います、 数字の束を生成し、 そして、あなたのヘルパー関数を実行します。 あなたのヘルパー関数君がいる場所です 実際に物理的にコードを書きます。 また、ライブラリファイルとしてヘルパーを考えます あなたは、検索を呼び出していること書いています。 そうhelpers.c内および、あなたはよ 検索とソートを行います。 そして、あなたは本質的になるだろう ただ一緒にすべてを置きます。 スペックはどのように教えてくれます コマンドラインでそれを置きます。 そして、あなたがいるかどうかをテストすることができるでしょうか ないあなたのソートや検索が働いています。 クール。 誰もがすでに始まっていると 遭遇した問題や疑問 彼らはこれを今持っていますか？ OK。 聴衆：待ちます。 質問があります。 ANDI PENG：うん。 聴衆：だから私は始め helpers.cで線形検索 そしてそれは実際に働いていませんでした。 しかし、その後、私はちょうど私たちを発見 それを削除して、二分探索を行う必要があります。 それが動作しないのであればそれは問題ではありませんか？ ANDI PENG：短い答えはノーです。 しかし、我々はnot--ているので、 聴衆：しかし、誰の 実際に確認します。 ANDI PENG：私たちは決してなりません それを見に行きます。 しかし、あなたはおそらくしたいです 必ずあなたの検索が機能しています。 あなたの線形場合ので、 検索が動作しません、 その後、チャンスはあなたのバイナリで 検索は、同様に仕事に行くされていません。 あなたが同様の持っているので それらの両方のロジック。 そして、いや、それは本当に問題ではありません。 だから、唯一のものはあなたが有効にします ソート、バイナリ検索があります。 うん。 そしてまた、子供たちがたくさんいました helpers.cをコンパイルしようとしています。 あなたが実際に許可されていません これを行うには、helpers.c理由 主な機能はありません。 だからあなただけのはず 実際にコンパイルします 呼び出しを見つけるために、生成して見つけます helpers.cとその中の機能。 だから、デバッグになります お尻の痛み。 しかし、それは私たちがしなければならないものです。 観客：あなたはちょうど、すべてを作りますか？ ANDI PENG：あなただけのことができます ええ、すべて同様に作ります。 OK。 だから、何の観点から、それです PSETはあなたのすべてが何を求めています。 ご質問があれば、感じます セクションの後に私に質問して自由に。 私は20分、のような、のためにここにいますよ。 そして、ええ、PSET年代 本当に悪いことではありません。 君たちはOKである必要があります。 これらは、単にガイドラインに従ってください。 種類の、論理的に、何の意味を持っています 起こってされるべきであり、あなたは大丈夫です。 あまりにも怖がってはいけません。 多くのコードがあります すでにそこに書かれました。 あなたがいない場合、あまりにも怖がってはいけません すべてのことが何を意味するのか理解しています。 それは多くの場合は、それは完全に罰金です。 また、営業時間に来ます。 私たちは、あなたが見てお手伝いします。 聴衆：余分付き 機能は、私たちはそれらを求めますか？ ANDI PENG：ええ、それらはコードです。 15のゲームでは、の半分 それは既にあなたのために書かれています。 だから、それらの機能があります すでにコードインチ うん。 大丈夫。 まあ、最高の幸運。 それは嫌な日です。 だから、うまくいけば、あなたたちは、あまりにも感じることはありません 内部滞在し、コーディングの悪いです。