SPEAKER 1：ちょっとみんな！ セクションに戻っようこそ。 ここにあなたの両方のように多くのを見てとても喜んで、 とオンライン見ている皆。 だから、いつものウェルカムバックとして。 私はあなたのすべてが素敵なを持っていたことを願っています 残りの完全な週末、リラクゼーション。 昨日は出美しかった。 だから、私はあなたがアウトドアを楽しんで願っています。 したがって、最初の発表のカップル。 グレーディング。 だから、あなたのほとんどは得ているはず あなたのスクラッチのPset約私からのメール、 同様のPset 1のためにグレーディング。 だから、ちょうどカップルの事。 style50でcheck50を使用してください。 これらは、であることを意味する 君たちのためのリソース、 あなたが取得していることを確認します あなたができる限り多くのポイント 不必要にそれらを失うことなく。 だから、スタイルのようなもの 非常に重要です。 我々はそれのために離陸しようとしている。 皆さんの中には、既に持っている可能性 あなたのPsetからその気づいた。 そしてcheck50はちょうどです 確実にする本当に簡単な方法 私たちは実際に何を返していること ユーザに返される必要がある、 そしてそのすべてが正常に動作しています。 第二了承の上、ご確認してください 正しいフォルダに物事をアップロードする。 それは私の人生だけになり もう少し難しい あなたがPsetに1に2のPsetをアップロードした場合 私は物事をダウンロードする際なぜなら、 彼らが正しくダウンロードされません。 そして、私はそれが少しグラグラ知​​っている システム内に慣れるため、 ちょうどスーパーであること 慎重に、私だけのためであれば、 ようにするには、メールを取得しているとき 2のように午前でと私はグレーディングよ。 発生しない場合は私が見ている あなたのPsetのためのすべての周り。 涼しい。 私はそれが早いですけど、私 完全ガードを外さしまった 今週の金曜日に起因のエッセイによって、その 私の教授はちょうどええオハイオ州、のようなものでした。 覚えておいて、あなたが持っている 金曜日に起因するエッセイ。 だから、私は誰も好きではない知っている 中間試験について考え、 しかし、あなたの最初のクイズは、10月15日です その10月は今週始めている。 だから、それは早くかもしれない あなたが予想よりも全てです。 あなたは、ときにガードをオフにスローされていないように、 私は、ああ、その次の週のセクションに言及 あなたのクイズ来週、私は思った 私はあなたにもう少し与えるだろう 今までのヘッド。 だから、あなたの問題が設定され、3番。 どのように人々が読んでいる 好奇心からスペック？ [OK]をクリックします。 私たちはカップルを得た。 種類のダウン最後から 週ませんが、問題ありません。 私はそれは美しい出ていた知っている。 だから、ブレイクアウト。 間違いなくあなたが成し遂げる後 本日は、少なくともあなたのスペックを読んで ダウンロードするように試みる 流通コードと実行 最初のイニシャルのような 彼らはにあなたを尋ねるもの。 私たちが使用しているので、 流通コードとライブラリ 我々は唯一の--Itだけだusing--てきたこと 我々はこののPsetをやった二回目、 狂気の事が起こる可能性が あなたのアプライアンスと、 そしてあなたはそれを見つけたい 今対後で出。 それは木曜日の夜だかどうかだから 水曜日の夜といくつかの理由で アプライアンスはちょうどない ライブラリと実行したい または配布した コー​​ドは、その手段 あなたもコーディングをやって起動することはできません。 あなたがチェックすることはできませんので、 それが動作するかどうかを確認します。 ことができ、あなたのつもりはない それはコンパイルするかどうかを確認します。 あなたは、早期のものの世話をしたい あなたはまだ私にメールすることができ、週、 または他のTFの一つ そして我々は、固定のものを得ることができます。 それらは問題であるため、 それはあなたを停止しようとしている 任意の実際の進捗状況を作るから。 それがあることを、1バグようではありません あなただけの種類のオーバースキップすることができます。 あなたの問題を抱えている場合 アプライアンスまたは配布コード、 あなたは本当にそれが取ら取得したい 遅かれ早かれよりもむしろ後での世話。 だから、実際につもりしていない場合でも、 コー​​ディングを開始、ディストリビューションをダウンロード コー​​ド、仕様を読んで、確認してください すべてがそこに働いている。 OK？ あなたはちょうどそれを行うことができますなら、私 自分の人生が容易になります約束します。 だからあなたはおそらくつもり 今は右のそれを行うには？ [OK]をクリックします。 だから、そこにどんな質問？ 任意のロジスティック物事？ 誰もが良いことだ？ [OK]をクリックします。 のそれらのための免責条項 あなたの部屋で、オンライン。 Iスイッチしようとしているつもりだ アプライアンス内のPowerPointの間 私たちがしようとしているので、 いくつかのコーディングをやっている 匿名の好評につき本日 提案世論調査では、私が先週送った。 だから、我々はいくつかのコーディングをすることになるだろう。 だから、あなたたちもしたい場合 あなたのアプライアンスを起動するために、 あなたが電子メールを持っている必要があります サンプルファイルで、私から。 それを行う気軽にご相談ください。 だから、私たちはについて話をするつもりだ デバッガですGDB、。 それはあなたを助けるために起こっている 種類のどこに把握 物事は、あなたのコード内で間違って行っている。 それは本当にあなたがステップにするためだけの方法だ それが起こっているようにあなたのコードを通して、 と変数をプリントアウトすることができる または実際に何が起こっているかを参照してください。 あなたのプログラムの詩ボンネットの下に ただ実行している、それは断層のようなものだ、 あなたが、ないアイデアに似ている 何がちょうどここで起こった。 私はそれが失敗した時に何行か分からない。 それは間違っていたどこに私は知らない。 だから、GDBはそのお手伝いをしようとしている。 また、あなたがすることを決定した場合 はい継続し、61を取る、 それは本当に、本当にあなたになります 親友、私はあなたを伝えることができる原因 私は、そのクラスを通してつもりですので。 我々はバイナリを見てするつもりだ あなたたちは覚えている場合は、検索、 偉大な電話帳の例 クラスから光景。 我々はそれを実装することでしょうし、 、もう少しその中を歩い その後、我々は4を通してつもりだ バブルである異なる種類の、 選択、挿入、およびマージ。 涼しい。 だから、GDBは、私が述べたように、デバッガです。 そして、これらは大きなの一種である 物事、大きな関数やコマンド あなたは、GDB内で使用し、私は歩いていくこと あなた秒でそれのデモを通して。 だから、これはただではない 抽象滞在する予定。 私が試してみて、コンクリートとしてそれを作ってあげる 君たちのために可能な限り。 だから、破る。 これは、いずれかのブレークになるでしょう のような、いくつかの数は、どの プログラム内の行を表し、 または、関数に名前を付けることができます。 それで、あなたはメイン破る言うなら、 それは、メインで停止します そしてあなたは、その関数の中を歩くましょう。 同様に、いくつかの外部を持っている場合 スワップやキューブのような関数、 我々は先週見た。 あなたがそれらのいずれかを破ると言うなら、 あなたのプログラムがヒットするたびに、その それはあなたのために待っています 何をするか、それを教えてください。 それはちょうどので、あなたを実行する前 実際には関数の内部で進む可能性が そして何が起こっているかを参照してください。 だから、次は、ちょうどをスキップ 次の行は、関数より行く。 ステップ。 これらはすべて少し抽象的である。 だから、私はちょうどそれらを介して実行するつもりです、 しかし、あなたは第二での使用にそれらが表示されます。 関数にステップ。 だから私が言っていたように、 スワップと同じように、それはでしょう あなたが実際にあなたがしているかのようにできるように 物理的に内部のステッピングのように、 これらの変数を持つことができます混乱、印刷 彼らが何であるか、何が起こっているかを参照してください。 リストは、文字通り印刷されます 周辺のコード外。 だから、あなたは親切なの忘れてしまった場合 あなたがあなたのプログラムのどこにいるか、 またはあなたが迷っている 何がその周りで起こっている、 これはただのセグメントをプリントアウトします のその周りに五、六行が好きです。 だから、あなたは慣れることができます あなたがどこにいる約。 いくつかの変数を印刷します。 だから、あなたのような鍵を持っている場合 シーザーは、我々は見てみましょうという。 あなたは、任意の時点で印刷キーを言うことができる。 値がそうであるもの、それはあなたを教えてあげましょう その、多分どこかで道に沿って、 あなたの鍵を上書きしました。 あなたが実際にその理由を伝えることができます あなたが実際にその値を観察することができます。 地元の人々、ちょうど印刷中 あなたのローカル変数外。 だから、いつでもあなたがループ内でなら、 そしてあなただけのああ、のような見てみたい。 私の私とは何ですか？ このキーの値とは何ですか 私はここで初期化することを？ この時点でメッセージは何ですか？ それはちょうど、すべての印刷されます それらの、あなたはそのよう 個別にする必要はありません 印刷I.印刷メッセージ、と言う。 印刷キー。 その後表示します。 何それが行うのは、あなたのようになる プログラムをステップ実行、 それはちょうどそれがだことを確認してくださいよ いくつかの特定の変数を表示する すべての点で。 あなたが--it年代をalso--ように どこにショートカットの種類 あなたがああ、のように続ける必要はありません。 PRINTキーまたは印刷I.それだけ 自動的にあなたのためにそれを行います。 だから、それを、我々はつもりだ これはどのようになるかを確認します。 私が試してみて、スイッチするつもりです 私のアプライアンスにオーバー。 私はこれを行うことができます参照してください。 すべてのこと。 私達はちょうどそれをミラーリングするつもりだ。 クレイジーは何もありません とにかく私のラップトップ上で。 [OK]をクリックします。 これは、これである必要がある。 それはとても小さなです。 我々はこれを行うことができるかどうか見てみましょう。 [OK]をクリックします。 アリスは明らかに苦労している ここで少しだけ、 しかし、我々はモメントでそれを得るでしょう。 [OK]をクリックします。 私達はちょうどこれを増やすつもりです。 [OK]をクリックします。 誰もが親切なのそれを見ることができますか？ たぶん少し？ 私はそれが少し小さいことを知っている。 あなたが非常に把握することはできません これを大きくする方法。 誰もが知っている場合。 誰もがそれを大きくする方法を知っていますか？ [OK]をクリックします。 我々はそれをロールバックするつもりだ。 それだけだからとにかく問題ではありません それはその君たちがすべきコードです 持っている。 もっと重要なのは何 ここでは端末である。 そして、私たちはなぜそれが非常に小さいので、ここで持っている？ セッティング。 ああ。 真のアイク。 これはどうですか？ そこから取り出します。 それは誰にとっても良いですか？ [OK] ,. 涼しい。 あなたがCSにいるときあなたが知っている クラス技術的な問題 the--の種類の一部である それでは、これをクリアしてみましょう。 [OK]をクリックします。 だから、ちょうどここのセクションで、 その私たちがここに持っていた。 シーザーは実行ファイルです。 だから私はそれを作った。 だから、GDBと実現するための一つのことである それが唯一の実行可能ファイルに動作する。 だから、あなたはdotsy上でそれを実行することはできません。 あなたが実際に行う必要があります あなたのコードがコンパイルされていることを確認し、 それは実際に実行することができる。 だから、必ず、そうでない場合ことを確認してください コンパイル、それはコンパイルに取得、 ように、あなたは一種のそれを介して実行することができます。 だから、GDBを起動するために、すべてのあなたが、 グロリアは、GDBを入力し、[ちょうど あなたが望むファイル。 私はいつもシーザーのスペルを。 しかし、あなたは確認する それは実行可能なので、 TIのドットフラッシュするように あなたが行っていることを意味 あなたが実行しようとしているCSI実行する これは、どちらかのデバッガを使用してファイル。 [OK]をクリックします。 だから、あなたはあなたが得る、それを行う ちんぷんかんぷんのこの種。 これは、デバッガ約ちょうどすべてのものです。 あなたは本当にする必要はありません 今はそれを心配。 ご覧のように、我々はこれを持っている オープン括弧、GDP、近い括弧、 とだけの種類のように見える 私たちのコマンドラインは、右？ だから、私たちはdo--するかをしたい - SO、まず最初に 私たちが選択したいです 場所は、それを破壊する。 だから、1バグがあります このシーザープログラムにおける 私は、それを紹介していること 我々は見つけるつもりです。 それは入力を取り込みで、それが何をするか すべて大文字でBarfoo、およびいくつかの理由で それはA.それだけ葉を変更しません それだけで、他のすべて正しいです、 しかし第二の手紙 Aは変わらない。 だから、私たちがしようとするつもりだ つまり理由を把握。 だから、最初にあなた通常、 あなたは、GDBで起動するたびにやってみたい それを破るためにどこに把握である。 だから、シーザーはかなり短いプログラムです。 私達はちょうど、一つの機能を持っている？ シーザーにおける当社の機能は何でしたか？ 一つだけの関数、主な権利はあります？ 主な機能である すべてのプログラムのために。 あなたがメインを持っていなかった場合、私はかもしれない 、今は少し心配である しかし、私はあなたのすべてがそこにメインを持っていた願っています。 だから、何私たちにできることは、我々はできている ちょうどそのように、メインを破る。 だから、それは[OK]を、述べています。 私たちは、そこに私たちのブレークポイント1を設定してください。 だから、今覚えておくべき事はシーザーである 1コマンドライン引数権を取る そして我々はどこにもまだあることを行っていない。 だから、あなたは何をすべきかは、時です あなたが実際に実行するために行く プログラム、あなたがしている任意のプログラム GDBで実行されていることは、コマンドラインを必要とします 引数は、あなたが入力するつもりだ あなたが最初にそれを実行して起動したとき。 そこで、この場合には、何 3のキーで実行します。 そして、それは実際に開始されます。 ここで見るのであれば、我々は持っている RCは2に等しくない場合。 だから、君たちがすべて持っている場合 私が送り出され、そのファイル あなたはそのようなものだが、ことがわかります 最初の行私たちの主な機能は、右？ それは我々が持っているかどうかをチェックだ 正しい数の引数。 だから、あなたは迷っている場合は、 RCが正しい場合、 あなただけの印刷RCのような何かを行うことができます。 RCはある、2です 私たちが予想、右？ そこで、次に行くことができ、 そしてを通して継続。 だから、私たちはそこにいくつかのキーを持っています。 そして、我々は我々のキーをプリントアウトすることができます それは正しいです確認します。 興味深い。 私たちが期待したものはかなりありません。 だから、一つのことは実現する GDBでも、です あなたが実際にヒットするまで、そうではありませんことを 次に、そのあなたがちょうど見たライン 実際に実行される。 だから、この場合のキーで まだ割り当てられていない。 したがって、キーは、一部のごみ値である あなたはそこに底に見ている。 負の$ 120-- --Itの10億 何か変なことですよね？ それは我々が期待キーではありません。 しかし、我々は[次へ]をヒットし、あれば、私たち それは3だ、試してみて、Printキー。 誰もがそれを参照してください？ だから、あなたが何かを得れば あなたが似ていることを、お待ちしております。 これは完全にある 間違った、と私にはわからない すべて私がしたいので、これは起こるだろうか 番号を割り当てているためには、変数、 [次へ]を打つ試して、印刷を試してみてください もう一度、それが動作するか観察してください。 それだけで実行するために起こっているためと 実際にあなたの後に何かを割り当てる [次へ]を押してください。 みんなに意味をなさない？ uhハァッ？ SPEAKER 2：あなたがランダム 数字それが何を意味するのでしょうか？ SPEAKER 1：それはちょうどランダムです。 それはちょうどごみだ。 それはちょうど、そのあなたの何か コンピューターがランダムに割り当てられます。 涼しい。 だから、今私たちはを通して移動し、そうすることができます 今、私たちはこのプレーンテキストのGetStringを持っている。 だから、私はちょうど何を紹介しましょう 私たちがここで[次へ]を打ったときに起こります。 私たちのGDBは一種の右側、消え？ それが原因のGetStringだ 今実行している、右？ 我々が見たときに、プレーンテキストに等しい のGetString、オープン括弧と括弧、 そして我々は持って[次へ]を、ヒット 実際に今、実行。 だから、それは待っている 入力何かに私たち。 だから、私たちは私たちの食べ物どの入力するつもりだ 私はあなたに言ったように、それが失敗しているものである それはちょうどそれがだと言っている 閉じたことを、実行が終了 ブラケットは、それがであることを意味 そのループの外に出た。 そこで、[次へ]を打つことができる、そして今、私はとして 必ず、すべてのシーザーから精通している、 これは、この行が何を何が起こっているのか、である。 それはint型私は0に等しいためだ、Nに等しく STRLEN、プレーンテキスト、その後 I nは、I、プラス、プラス未満である。 どうするつもりこのループは何ですか？ あなたのメッセージを開きます。 涼しい。 それでは、それをやって始めましょう。 したがって、この状態ははず 私たちの最初の1のために、一致する？ それがBの場合は、プレーンテキストⅠ。私たちだ 私たちの地元の人々についての情報を得ることができます。 だから、私は、そのゼロであり、6の場合 私たちは期待し、私たちのキーが3個である。 意味をなすこと、すべて、右？ これらの数字が全てです 正確に彼らがどうあるべきか。 だから、ハム？ スピーカ3：私が持っている 鉱山のための乱数。 SPEAKER 1：まあ、我々は--weをcheck--できる 第二でそれについてチャットすることができます。 しかし、あなたはこれを取得する必要があります。 だから、我々は資本を持っている場合 私たちの最初の1のためのB、 この条件では右、それをキャッチする必要があり？ 私たちは次を打つのであれば、我々はを参照してください。 この場合には、実際に実行されるように。 あなたがフォローしている場合には理由 あなたのコード内に沿って、 このここで行、プレーンテキスト私は この算術に置き換えられ、 場合にのみ実行された場合 条件が正しい権利である？ GDBはだけお見せしようとしている 実際に実行しているもの。 このIf条件が満たされていなかったのであれば、それはだ ちょうど次の行にスキップするつもり。 OK？ だから、私たちはそれを持っている。 このブラケットは、それがであることを意味 今そのループの外に閉鎖した。 だから、それは再び開始する予定だ。 ちょうどそのように。 だから、私たちは情報を得ることができること ここに私たちの地元の人々約、 そして我々は我々の最初のことがわかります 手紙は、右変わりましたか？ それがあるべきように、それは、今、Eです。 だから、私たちは上継続することができます。 そして、我々は、このチェックを持っている。 そして、このチェックは、右動作するはず？ それが変更されるべきだA. フォワードの三文字。 しかし、あなたは、私たちに気づいた場合 別の何かを得る。 だからここに、この場合、最大では、それがキャッチ それので、この行が実行され、 私たちのBを変更している しかし、ここで、この場合、 我々はそれがちょうどそれをスキップすることを持っている、 そして[に行きました？ L個のSIFF。 ？] だから、何かが起こっている。 それは何それはあなたを語っていますです、 我々は、それがここにキャッチする必要があることを知っている しかしそうではありません。 誰もが何を参照することができます私たちの 問題は、その行にある？ それは非常に微細なことだ。 そして、あなたはまた、あなたのコードを見て可能性があります。 また、それが何であるかのラインを忘れline--だ there--にそれは[聞こえない]にあります。 はい？ スピーカ4：それはより大きい上にある あなたは本の中でそれを読めばページ。 SPEAKER 1：その通り。 だから、デバッガは言うことができませんでした あなたでなく、デバッガ ラインにあなたを得ることができる あなたが機能していないことを知っている。 そして、時には、場合に特に 後で学期、中 あなたが百、Aを扱っている 数百行のコード、そしてあなた それは失敗だか分からない、 これはそれを行うための素晴らしい方法です。 だから、私たちは私たちのバグを発見した。 あなたは、あなたのファイルにそれを修正することができ、 その後、あなたは再びそれを実行することができ、 すべてが完璧に動作します。 そして最大のものです これはOK、のように見えるかもしれません。 うん。 涼しい。 あなたが探しているものを知っていた。 だから、あなたは何をすべきかを知っていた。 GDBはあなたのためのスーパー役に立ちます あなたこれらすべてのものをプリントアウトすることができます ないだろう。 それは、はるかに便利なのprintfよりもだ。 どのように多くのあなたの使用 のprintf文のような バグが、右のあった場所を把握するには？ だから、これで、あなたはしないでください 戻って保持する必要があり、 とにコメントしたい PRINTF、またはコメントアウト、 何を把握 あなたが印刷されるべきである。 これは実際にあなたがすることができます ステップスルー、物事をプリントアウト あなたを介して行っているようなので、次のことができます 彼らはリアルタイムでどのように変化するかを観察し、 あなたのプログラムとして実行されている。 そして、それは少し時間がかかりますか に慣れるのビット。 私は非常に親切なだけで推薦する それを少し不満であることの 今のため。 あなたは時間以上を費やしている場合 来週GDBを使用する方法を学んで、 あなた自身を救う 後でそんなに時間。 文字通り。我々は言う この人々に、毎年、 私が取ったとき、私は覚えている クラス、私は罰金になります、のようだった。 いいえ。 PSET 6は、上来て、私がいた のような、私は学ぶつもりだ 私はしませんので、GDBを使用する方法 ここで何が起こっているか知っている。 ですから、そのように時間がかかる場合は、 小さいプログラムでそれを使用 あなたがするつもりだこと 作業のように、上の作業 のようなものを通して このようなVisionare、。 あなたが余分な練習をしたい場合、または、私は確信している 私は、バグのあるプログラムを思い付くことができ、 あなたが好きな場合は、デバッグするために。 しかし、あなただけの取得に時間がかかる場合は、 それに慣れ、ちょうどそれで遊んで、 それは本当によくあなたを提供します。 そして、それは本当にの一つだ あなたそれらの事ばかり 試してみて、そしてあなたの手を汚す あなたが本当にそれを理解する前に、と。 私は本当に一度だけ、それを理解 私はそれで物事をデバッグしなければならなかった、 そしてそれはのアイデアを持っているために非常に良くだ どのようにすぐにではなく、後にデバッグします。 [OK]をクリックします。 涼しい。 私はそれが一種のようなものだ知っている GDBのクラッシュコース、 と私は間違いなく得る上で動作します これらは次回に大きく見えるように。 涼しい。 だから、我々は戻って私たちのPowerPointに行けば。 これが仕事に行くされていますか？ AWH。 はい。 [OK]をクリックします。 だから、あなたは今までのいずれかを必要とする場合は、 それらを再度、リストがあります。 だから、バイナリ検索、そのすべての人 ダビデの偉大な光景を記憶しています 半分に電話帳をリッピング。 私は本当に得ることはありません もはや電話帳、 あなたを行う場所が好きなので これらの日電話帳を取得？ 私は本当にわからない。 バイナリ検索。 誰もが覚えているん どのようにバイナリサーチの作品？ まったく誰ですか？ うん？ スピーカ5：あなたが知っているとき あなたが半分を見て それはこれに基づき、中だろう、 そして残りの半分を取り除く。 SPEAKER 1その通り。 だから、バイナリ検索は、それがのA--ようなものだ 分割統治、それを呼びたい--we。 だから、あなたがやるものです あなたは、途中で見てみましょう それが一致した場合、あなたが表示されます あなたが探しているもの。 そうでない場合、あなたはしよう 把握するには、左されようとしている 半分または右半分。 あなたが探しているのであれば、これは可能性があります アルファベット順だ何かで、 あなたがああ、参照してください。 アリソンは、Mの前に来ていますか？ はい。 そこで、我々はするつもりだ 前半を見てください。 それとも、番号を持つようになる可能性があります。 そのあなたが何かできること 比較するには、ソートすることができる。 あなたは上のバイナリ検索を使用することができます。 だから、誰もがこれを覚えている グラフまたはこれが何であるか？ それは漸近複雑だ。 だから、このグラフだけ どのくらいの時間を説明 ような問題を解決するために移動します あなたは物事の数を増やす あなたが使っているという。 そこで、線形時間であるNを持っています。 わずかに2以上のN、もし より良い、まだ超高速成長する。 そして、我々はある、ログインしている 私たちは、バイナリ検索を検討してください。 我々は気付いた場合、あなたの問題など 、はるかにはるかに大きくなる それを解決するためにかかる時間 本当にそれほど増加しない。 それは同等のようなものだ ここで初めに。 [OK]をクリックすると、似ている。 ここで何が本当にしません 我々が使用する1問題、 しかし、あなたは、万人に億を出す。 あなたはsome-- --you'reを見つけようとしている 干し草の山の中から針を見つけようとする。 私はあなたがこの問題をしたいと思います。 あなたは、この複雑さをしないしたい あなたのためにすべてのために線形 あなたのつもりを検索することがわかっている 各個別の針、干し草のもの、 あなたの針を探すようにしよう。 そして、それは私の意見ではあまりにも楽しいではありません。 私が速いのが好きです。 私は効率的なのが好きです。 そして勤勉な学生として、あなた みんな、あなたがよりスマートに働く知っている、ある タイプの事難しくありません、どのように これらのアルゴリズムを構成することができます。 だから、私たちは歩くつもりです ちょうど簡単な例を通して。 私はあなたたちが持っているべきだと思う バイナリ検索上の手、 しかし場合に誰もが少しある ファジー、それを強化したい、 私達はちょうど行くつもりです ここでの例を通して。 そこで、もし探している 配列には7が含まれています。 ですから、私たちが最初にすることはある 右、真ん中に見える？ また、あなたがコーディングことになるだろう ちょうど第二のバイナリ検索。 だから、それは楽しいことになるだろう。 だから我々はに見える 真ん中の少しの配列3。 図3は、7に等しくしていますか？ しません。 それは6です。 だから、それは以下である または7より大きい？ 未満である。 はい。 ニースの仕事の連中。 私は私が必要がありますように感じる キャンディーを持っている私がいるので ヤードにそれを捨てたい。 それは私が来週するつもりですんだ。 それは鋭い君たちを維持します。 そこで、我々はそれを捨てる 前半、右？ それは以下であった。 我々はそのすべてを知っている その左側 未満であると何が起こっているか 私たちは実際に探している。 だから、する必要はありません それに注意を払う。 ちょうどそれを忘れる。 だから、今私たちは私たちの右側を見て、 そして我々はあそこに真ん中を見て、 今では9です。 だから、9 is-- --Everyone？ 私たちは何をしているよりも大きい 右、先をお探しですか？ だから、私たちはスローするつもりだ 右に離れてすべてのもの。 そのような。 今、すべての私たちは一つですが残っている。 だから我々はチェックし、この1であるもの 私たちは探している？それは。 我々は、我々が望んで見つかった。 だから我々は完了です。 バイリニア検索。 そして、あなたは、私たちに気づいた場合 そこに7の入力を持っていた。 それは3回だけのように連れて行ってくれました、 しかし、あなたは億のようにやっている場合には、 君たちは、どのように多くのステップそれは知っているだろう 我々は40億物事を持っていた場合取る？ 任意の推測？ それは32だ。 何かを見つけるための32ステップ 40億中 なぜなら、2の累乗の要素の配列。 だから二人は、32にある40億にある。 だから、かなりクレイジーどのようにあなたはまだ内だ ステップのかなり少数のような で何かを見つけるために 40億要素。 だから、そのノートに、私たちはしている これをコーディングする予定 そうあなたたちは、実際に缶 種類の、これはどのように動作するかを参照してください。 すべての権利、君たちはコーディングすることができますように。 私は君たちようにするつもりです 少しのために話す。 である、あなたの周りの人々を知ってもらう 何誰かが最後のセクションから望んでいた。 だから、あなたの周りの人々を知るようになる。 少しのために話す。 そして、すべて私はあなたから欲しい 連中は、今だけである 擬似コードのアウトラインを作成してみてください。 OK？ おっと。 私はあなたたちから欲しいすべては、あなたがしているである ちょうどこのしばらくケースに埋めるつもり。 だから私は、これらの上限を設定している と下限いる 始まりを表す 私たちの配列のと終了。 そして、あなたが実際にしようとしている ループを通ると把握 我々は、このwhileループ内で何をやっている。 あなたがゆうパックで把握することができますので、もし私が持っている ケースが何であるかをthere--ヒント 私たちがここに持っている？ あなたが把握したいのであれば ケースは、我々はそれらを擬似コードます その後、我々は実際にそれらをコーディングします。 そしてそれは、私になるだろう それがうまくいけば、と思う あなたが予想よりも少し簡単にしてください。 なぜならそれがその多くのコードではありません、 実際に、これは本当にクールです。 MM-HM？ 学生：[聞こえない]？ 講師：はい。 何かがあった 途中で見つけるために。 学生：だから我々はそれを使用することができます。 [OK]をクリックします。 講師：パーフェクト。 だから、それは我々が最初に必要なことだ。 だから、真ん中を見つける。 グレート。 だから、どのように我々はかもしれないという考えを持っていない 実際にコードとの真ん中を見つける？ 学生：うん。 2オーバーのn？ 講師：だから、nは2オーバー。 だから、覚えておくべき一つのことということです あなたの上限と下限が変わります。 私たちは、一部を収縮保つ アレイで我々はに探しています。 だから、nは2の上にのみ機能します 最初にのために私たちはやる。 そこで考慮上下取る どのように我々はその中間の要素を得るかもしれない？ 私たちは中央をしたいので 右、上下の間に？ MM-HM？ 学生：[聞こえない]。 講師：だから我々はいくつかの真ん中を持っている。 そして、それは、上側プラス2オーバー低くなるでしょう。 恐ろしい。 私たちはそこに行く。 1行下。 君たちはあなたの方法にある。 だから今我々は持っていること 真ん中には、我々は何をすべきかをしたいですか？ ただ一般的には。 あなたはそれをコーディングする必要はありません。 はい。 学生：[聞こえない]？ 講師：あなたがしているので、だから、プラスだ 2間の平均を見つける それらの。 だから、として親切それらを思えば 側面からの高まりの、 あなたが近づくとそれについて考える 真ん中のは、あなたがそのようにしたい。 だから、のいずれかの側にあった場合は、 ミドル、そして我々は5,7のように持っている。 あなたはあなたにそれらを一緒に追加すると 12を取得し、あなたは2で割る、6です。 時にはそれが難しいです その作業の理由を説明し、 しかし、あなたはを通して作業している場合 例時には、 それはあなたがどうかを把握お手伝いします それがプラスまたはマイナスにする必要があります。 はい。 学生：[聞こえない] 丁度真ん中に 彼らはどこにケースを持っていた場合 小さい数字がたくさんあり​​ます 1つの大きな番号のような？ 講師：だから、すべてあなたが必要 アレイの中央である。 ですから、少数の束を持っていた場合 その後1本当に多数 最後に、それは問題ではありません。 重要なのは、ということです 彼らは、あなただけでソートしている の真ん中を見てみたい アレーあなたはまだだから 半分にあなたの問題をスライスする。 涼しい。 だから今我々が持っていること 真ん中には、私たちは次に何をしますか？ 学生：比較してください。 講師：比較。 だからvalue_wantedために中間を比較します。 涼しい。 ですから、私たちが持ってここに参照してください。 この値は、我々はここにアップしたい。 これは配列であることを忘れないでください。 だから、真ん中はインデックスを参照。 だから我々は真ん中の値をやってみたい。 あなたがしたい場合を忘れないでください 、二重の等号を比較することができます。 あなたがしているシングル等しいん ちょうどそれを再割り当てするつもりは、 その後、もちろん、それがだ あなたが希望する値になるだろう。 だから、それをしないでください。 だから我々はどうするつもりだ 途中での値 私たちが望む値に等しい。 あなたの中括弧を忘れないでください。 Dropboxは離れて行く必要があります。 だから我々は、この場合に何をしますか？ それが仕事だ場合、我々は返すようにしたいですか？ 私たちは言おうとしている。 学生：オフ印刷します。 講師：まあ、我々 オフ印刷しない。 だから、これはここにブールですので、我々 trueまたはfalseを返すようにしたい。 我々は、この番号である、と言っている [？ RRA？ ？]だからである場合 私達はちょうどそれが真を返す。 私は真綴ることができる場合。 学生：なぜあなたは、ゼロを返しませんでしょうか？ 講師：あなたができるよう あなたが望む場合はゼロを返します。 しかし、今回のケースであるため 私たちの関数はブール値を返し、 私たちは、trueまたはfalseを返す必要があります。 学生：あなたがしている ブール式を言って、 あなたはそれをfalseに等しくなるように設定することができますか？ 私が言いたい場合には、もしこのような状態 アッパーはfalseに等しいように、満たされていない。 ちょうどあなた場合、それは理解できるであろう 反対側にfalseを置く？ 講師：うん。 だから、実際にあなたがいるなら 今までに何かをして 上限であるか、または低くなるような、 それは、trueまたはfalseを返します そしてそれは実際に悪いスタイルだ 等号がtrueに等しいかイコール言う 偽等しい。 あなたはその結果を使用したい あなたのチェックとして、それ自体として。 私が望んでいないもの。 それは私が欲しかったものだ。 だから例に求めている Cでこれを保存するような何かについて。 そこで、int型メイン（ボイド）がある場合 そして、このような何か。 上側のであれば、あなたが持っている あなたがしているといくつかの入力の あなたが行うことができますかどうかを尋ねる このような何か？ 右？ 学生：私がしようとしていた それ[聞こえない]することができません。 なぜならば、it's-- 講師：右。 だから、あなたは正しい、これが偽になりたい？ 学生：うん。 講師：だから、この場合はあなた それは本当ではない場合は、それが実行したい。 だから、あなたがクールな事はこれがあります。 だから、感嘆を覚えている ポイントは、物事を否定？ これは、[聞こえない]ではないことを意味言う。 我々だけを見ればそう ここではこの部分、あなたがしたい それがあると評価言う あなたはそれがしたいようにはfalseを返します。 偽ではないが真である これが実行される可能性がありますことを意味します。 それは理にかなっていますか？ 学生：うん。 講師：恐ろしい。 [OK]をクリックします。 だから我々はただ返すことができます この場合は真。 だから今我々は他の2を持っている この場合の例。 我々の2つの他のケースは何ですか？ ちょうどこのようにそれをやってみましょう。 それでは、誰から始めましょう もし途中での値 私たちが望む値未満である。 だから、途中で私たちの値が小さい 私たちが探している値よりも。 だからを行う​​バインドいる 我々は更新したいと思いますか？ 上部または下部？ アッパー？ 配列のだから、どちら側 我々はを見ているつもりですか？ 学生：低い。 講師：私たちは、私たちがしようとしている 左を見られる。 少し値が小さければ、そのように他の。 ここにだからあなたの中間値 私たちが望むものよりも小さい。 だから我々は利用したい 我々のアレイの右側。 だから我々はするつもりだ 私たちの下界更新します。 だから我々は我々の下を再割り当てします。 そして、あなたは下がどうあるべきかだと思いますか？ 学生：中間値？ 講師：だから、真ん中value-- 学生：プラス1。 講師：--plus 1。 誰もが、なぜ私を伝えることができます 我々はそのプラス1を持っている？ 学生：[？値なし？] それにより平等である。 講師：右。 我々はすでに知っているので 我々の中央値は、に等しくない それ、我々はそれを除外したい 後続のすべての検索の。 あなたはそのプラス1、これを忘れた場合 無限にループを好きになるでしょう。 そして、あなたはただでキャッチされます 無限ループして、あなたがセグメンテーション違反だろう そして物事は悪くなる。 だから、いつもあなたがわからないことを確認してください ちょうどあなた値を含む を見た。 だから我々は、プラス1でそれの世話をする。 だから今、私たちは私たちの最後の条件を持っている 安全のためのためにどのいつも私 あなたはでの値であれば、他の、ここで確認することができます 中間の値よりも大きい 私たちは欲しい。 つまり、私たちが望むことを意味します 左側半分。 だから、その一つ、我々は更新するつもりですか？ アッパー。 と等しくなるようにしよう、この1は何ですか？ 真ん中のマイナス1なぜなら、 もちろん、我々は欲しい 私たちがわからないことを確認します 再びその中間の値を見て。 そして、我々はそれを持っている。 それはそれだ。 つまり、バイナリ検索がすべてです。 それは右、その悪くはない？ これは、10行のようなものだ ホワイトスペースを使用してコード。 あなたは意志、非常に便利なので、非常に強力な あなた以降のPsetのいずれかでそれを使用する。 そうでないかもしれない、この1が、後。 だから、それを学ぶ。 それを愛する。 それはあなたによく扱います。 だから、誰もがいずれかを持っているん バイナリサーチに関する質問？ はい。 学生：それは問題ではない あなたのnが偶数か奇数か？ 講師：いいえ。 我々のように真ん中にキャストしているので int型は、それはちょうどそれが切り捨てられます。 だから、整数に滞在し、それは意志 最終的にはすべてのものをソート。 だから、そのことについて心配する必要はありません。 みんな良い？ 恐ろしい。 涼しい。 だから、君たちはこれを得た。 スライドショー。 私たちが話していたように、私は知っている Davidは複雑ランタイムを言及。 そこで最良のケースでは、それだけだ 我々は一定の時間を呼び出す1、。 それはかもしれない、なぜ誰も教えてもらえますか？ それは、シナリオはどのようなタイプを伴うだろうか？ MM-HM。 学生：[聞こえない] first-- 講師：だから、真ん中がいる 我々はに来て最初の要素は、右？ だから、1の配列のいずれか、または 私達はちょうど探しているものは何でも 真ん中にピシャリDABであることを起こる。 だから、私たちの最高のケースです。 おそらく、本当の問題にしない取得 その多くの場合、[聞こえない]に到達しようとして。 何私たちの最悪のケースはどうですか？ 私たちの最悪の場合には、ログnである。 そして、それは全体に関係しています 私が話を2のべき乗の事。 そこで最悪の場合、それが意味する 私たちはダウン配列をチョップしなければならなかったこと 、一つの要素になるまで。 だから我々はそれを半分に切り倒す必要がありました 何度でも我々はおそらくできる限り。 それはログnの理由だ理由です あなただけの2で割る保つ。 仮定、物事あなたはとても あなたが今までしているかどうかを知る必要があり バイナリ検索を使用するつもり。 あなたの要素はソートする必要があります。 彼らは理由にソートされなければならない それはあなたの唯一の方法だ あなたができるかどうかを知ることができます それの半分を捨てる。 あなたはこのごちゃ混ぜ袋を持っていた場合 数字のあなたが言っている、 [OK]を、私は真ん中をチェックするつもりだ 数と私が探している数 それよりも少ないですが、私はちょうどつもりです 任意の半分を捨てるため。 あなたの場合は知っているだろう その残りの半分の数字。 あなたのリストをソートする必要があります。 同様に、これであってもよい 先に少し行く、 しかし、あなたは、ランダムアクセスを持っている必要があります。 あなただけのことができるようにする必要があります その中央の要素に移動します。 あなたが横断しなければならない場合 何かを通じて またはそれはあなたの余分なステップを取る その中間の要素を取得するには、 それはログに記録nはもはやなぜならないです あなたはそれに多くの作業を追加している。 そして、これは少しを行います 2週間でより多くの意味、 しかし、私はちょうど種類の序文たかった、 君たちに何のアイデアを与える 来て。 しかし、これらの2つである 重要な仮定 あなたがバイナリリストについて必要があると。 それはソートだことを確認してください。 つまりにとって大きな一つだ あなた今、みんな。 その上、我々は入ることができます 私たちの種類の残りの部分。 だから、4 sorts--バブル、 挿入、選択、およびマージ。 彼らはクールのすべての種類だ。 君たちは、CS 124取ることを決定した場合、 あなたは種類のすべての種類について学びます。 そして、あなたはそこに、XKCDファンなら 本当にクールな漫画うとしている 本当に効果のない種類のように、どのI 非常にあなたが見に行くことをお勧めします。 その一つは、パニックソート似ているある ああ、いや、ランダムな配列を返す、などである。 停止システム。 ままにしておきます。 だから、マニアックなユーモアは常に良いです。 だから、誰もが親切覚えてません ちょうど一般的な考えのように バブルソートがどのように動作するかの。 あなたは覚えていますか？ 学生：うん。 講師：それのために行く。 学生：だからあなたを介して行っていると それは大きいです場合は、2を交換。 講師：MM-HM。 正確に。 だから、あなただけの反復処理。 次の2つの番号をチェック。 1は前に大きい場合 その後1より、 あなただけでそのようにそれらを交換 このように高い数値のすべて リストの終わりに向かってバブルアップ とそれ以下のすべての数字バブルダウン。 彼はクールな君たちを示しましたか ビデオをソートする効果音？ それは、クールのようなものだ。 だから、ロバートは今言ったように、アルゴリズム あなただけのリストをステップ実行することを、 隣接する値をスワップ 彼らは順番にいないのであれば。 そして、ちょうど繰り返し続ける あなたまで、あらゆるスワップすることはありません。 そんなに悪くないよね？ だから我々はちょうどここに簡単な例を持っている。 だから、これは並べ替えしようとしている 昇順でそれら。 だから我々は最初に通過するとき 時間は、私たちは8に目を通す そして6は明らかではありません ために、我々はそれらを交換。 だから、次の1を見てください。 エイトと順番に4ません。 それらを交換。 その後8および2は、それらを交換。 私たちはそこに行く。 だからあなたの最初のパスの後、あなた あなたの最も多くのことを知っている すべての道になるだろう それだけだから一番上にある 絶えずになるだろう 他のすべてよりも大きい そしてそれはちょうどバブルに起こっている そこに最後まですべての方法まで。 それは皆に理にかなっていますか？ 涼しい。 それでは、私たちは私たちの第二のパスを見てください。 六四、スイッチ。 六二、スイッチ。 そして今、我々は順番にいくつかのことを持っている。 すべてのパスのように、私たち 私達の全体のリストを作る 我々は、多くの数字のようにそれを知っている 終了時にソートされているであろう。 だから我々は3回目のパスを行う、 その1スワップです。 その後私たちの第四の上 我々はゼロスロットがあり、合格する。 そして私たちは知っている私たちの 配列はソートされている。 そしてそれは大きいです バブルソートとの事。 私たちは、そのときに我々を知って 、そのゼロスワップを持っている そのすべてを意味します 完全なオーダーである。 それは我々がチェックする方法のようなものだ。 だから我々はまた、バブルをコーディングしようとしている また、悪いことではありませんソート。 これらはどれもそれほど悪くはありません。 私は、彼らが少し怖いように見えることができます知っている。 私が取ったとき、私は知っている クラス場合であっても、私 のためのクラスを教えていた 初めて昨年、 私は、私はこれをどのように行うのですか、のようだった？ それは、理論的には理にかなっているが、 私たちは実際にこれをどのように行うのですか？ 私も歩きたい理由である ここに君たちとのコードを通して。 だから私は擬似コードを持っている 今回は皆さんのために。 だから、同じようにこれを覚えておく 我々はオーバーに移行しようとしています。 だから我々はいくつかのカウンターを持っている 私たちのスワップを追跡し、 我々は確認する必要がありますので、 我々はそれをチェックしていること。 そして、我々は、配列全体を反復 私達はちょうどこの例で行ったように。 要素は、以前よりも大きい場合 私たちがどこの後の要素、 私たちはそれらを交換し、我々は我々のをインクリメント カウンター、我々はスワップや否や理由 私たちはカウンターがそれを知らせたい。 そこにどの質問？ 何かがこっちに面白いと思われる。 学生：あなたがゼロにカウンターを設定してください あなたは、ループを通過するたびに？ あなたは続けるしないでください ゼロに戻るたびに？ 講師：必ずしもそうではありません。 だから何が起こるかは私たちがここを通過している。 だから、これをしばらく覚えていますか 必ず一度実行されます。 だから、設定するために起こっている ゼロに等しいカウンタ それはを反復処理するために起こっている。 それが反復処理として、 それはカウンターを更新します。 それはカウンター更新など、それが終了したときに、 それは、配列の最後に到達だとき、 私たちのリストがソートされていない場合、 カウンタが更新されています。 だから、それは条件をチェックし、それ [OK]を、ゼロよりカウンターも大きい、と言います。 もしそうであれば、再びそれを行う。 あなたはそうしたときにことをリセットしたい 通過すると、カウンタはゼロに等しい。 あなたは、ソートを通過した場合 アレー、何も変化し、 これが失敗し、 ソートされたリストを返す。 それは理にかなっていますか？ 学生：それは少し中かもしれません。 講師：OK。 他のは、あるとすれば 立ち上がる質問。 はい。 学生：何だろう機能 要素をスワップするためのもの？ 講師：だから我々は実際に書くことができます 私たちが今するつもりならそれ。 涼しい。 そのノート上のように、アリソンに起こっている アプライアンスに戻って切り替えます。 それは楽しみになるだろう。 そして、私たちは私たちの素敵なを持っている ここにバブルソートの事。 だから私はすでにサイクリングをしました 配列を通して。 私たちは、スワップを持っている ゼロに等しい。 だから我々は、隣接入れ替えたい 要素は、彼らは順不同でなら。 だから我々がする必要がある最初の事は 私たちの配列を反復処理されません。 それでは、どのように我々はかもしれないと思うん 私たちの配列を反復処理？ 私達はのために持っていると私は0に等しい。 私たちは、私はあまりなりたい nはマイナス1マイナスkより。 そして、私は、第二にそれを説明します。 だから、これはここで、最適化され、 私はすべてのパスの後に言った方法を覚えて アレイ·私たちを通して 何がon--だということを知っている だから、1パスの後、私たち これがソートされていることを知っています。 二つのパスの後、我々は知っている このすべてがソートされていること。 3つのパスの後、私たち それはソートだね。 私は繰り返し処理していそうな方法 ここでは、アレイを通して、 それだけで行くことを確認していますされている 私たちが知っていることを通してソートされていないです。 OK？ それはちょうど、最適化だ。 あなたはただ単純にそれを書くことができます すべてのものを反復、 それだけで長い時間がかかるだろう。 これ4ループで、それはだ ちょうどいい最適化 我々はその後、すべての完全な知っているので、 ここで、アレイを通して反復、 ここにすべての完全なループのように、私たちは知っている これらの要素のもう一つのその 最後にソートされます。 だから我々はそれらを心配する必要はありません。 それは皆に理にかなっていますか？ そのクールな小さなトリック？ その場合、もしそうであれば 我々は、を反復している 我々はかどうかを確認したいことを知っている 配列nとnプラス1が順序である。 [OK]をクリックします。 だからここ擬似コードです。 私たちは、アレイのnかどうかを確認したい そしてnプラス1が順序である。 だから我々はそこに何を持っているのでしょうか？ それはいくつかの条件になるだろう。 それは場合になります。 学生：配列​​nがされた場合 配列nはプラス1未満である。 講師：MM-HM。 さて、以下より大きい。 学生：より大きい。 その後、我々はそれらを交換したいと思います。 正確に。 だから今我々は何に入る それらをスワップするためのメカニズム？ だから我々は、この簡単に通り抜けた、 スワップ関数の型は先週。 誰もがそれが働いた方法を覚えていますか？ だから我々はちょうど、それらを再割り当てすることはできません？ そのうちの一つが失われてしまいますので。 我々は、AがB、次いでBに等しいことを特徴とする場合 Aに等しく、両者の突然 Bにちょうど等しい だから我々がしなければならない私たちです の一時変数を持っている 我々しばらくのいずれかを保持するために行く 我々はスワッピングの過程にいる。 それでは私たちが持っていることは我々はいくつかのint型があるでしょうです あなたがそれを割り当てることができto-- tempが等しい あなただけの、欲しい方1へ あなたがit--を追跡することを確認してください ので、この場合には、私はするつもりだ 配列nはプラス1に割り当てます。 だから、何でも保持するために起こっている 値は、その第二のブロックである 私たちが見ていること。 そして、我々は行くことができますし、我々が行うことができますです 先に、配列nのプラス1を再割り当て、 私たちを知っているので その値が格納されている。 また、これは大きなの一つです あなたのいずれかの場合にthings--私は知らない あなたは2を切り替えた場合の問題を持っていた コー​​ドの行が突然物事が働いた。 順番は、CSで非常に重要である。 だから、必ず図作る 物事出可能な場合 実際に何が起こっているかに関して。 だから今、我々はするつもりだ 配列nのプラス1を再割り当て、 私たちを知っているので その値が格納されている。 そして、我々は、配列にそれを割り当てることができます nまたはこの場合、アレイ内のi。 あまりにも多くの変数。 [OK]をクリックします。 だから今我々が再割り当てした配列にi プラス1は、配列のiに何があるかに等しい。 そして今、我々は戻って行くことができます 何に配列iのを割り当てる？ 誰ですか？ 学生：10。 講師：10。 正確に。 そして最後にひとつ。 我々は今それをスワップしている場合は、 私たちは何をすべきかが必要ですか？ 一つのことは何ですか それは私たちに伝えるために起こっている 我々はこれまでに、このプログラムを終了させる場合はどうなりますか？ 私たちを教えてくれる ソートされたリストを持っている？ 私たちはどんなスワップを実行しない場合、右？ スワップに等しい場合 これの終わりにゼロ。 だから、あなたは私たちのように、スワップを実行するたびに、 ちょうどここでしたが、我々はスワップを更新したい。 そして、私はそこにいた知っている 質問以前の約あなたができる 代わりに、ゼロまたは1を使用 trueまたはfalseの。 そして、それは、これは、ここで何をするかだ。 だから、これはそうでない場合スワップを言います。 だから、スワップは常に私をis--ゼロである場合、 私の真理と取り違え私falsesを得る。 私たちは、私たちは評価したい trueにし、そうではありません。 それがゼロだのであれば、それは偽だ。 あなたはそれを否定した場合 [？強打？]それは真になる。 それでは、この行が実行されます。 真理と虚偽と ゼロと1の狂気を取得。 ちょうどあなたがゆっくり歩けば それを介してそれが意味をなすでしょう。 しかし、それはどのようなこの小さなだ コー​​ドのビットはここにいます。 だから、これはどうかを確認し 我々はすべてスワップを行っている。 だから、何かほかにあればだ ゼロ、それが偽になるだろう 全体の事はある 再び実行しよう。 クール？ 学生：ブレークは何をしますか？ 講師：ちょうどブレイク ループの外にあなたを壊します。 この場合、それはそうだろう ちょうどのようなプログラムを終了 そしてあなただけでしょう あなたのソートされたリストを持っている。 学生：アメージング。 講師：ごめんなさい？ 学生：以前に私たちのため 書かれたゼロの上に書かれた1を使用 場合にそれを提示する それは仕事をしたりしません。 講師：うん。 だから、ゼロまたは1を返すことができます。 この場合、我々は実際にわからないので、 関数で何をやって、 私達はちょうどそれが壊したく。 私たちは本当にそれを気にしないでください。 ブレーキもあれば良いです それが勃発するために使われている その4つのループまたは状態の あなたが実行を保持しない。 それはちょうどそれらのあなたを取る。 それは、ニュアンスの事少しだ。 ありますような気がします の手振りの多くは、 のようなあなたはすぐにこのことについて学びます。 しかし、あなたはすぐにこのことについて学びます。 私は約束します。 [OK]をクリックします。 だから、誰もがバブルソートを取得していますか？ あまりにも悪くはない。 使用して、スワップ物事を反復処理 temp変数は、我々はすべてそこに設定されている？ 涼しい。 恐ろしい。 [OK]をクリックします。 戻るPowerPointに。 一般的にどの質問 これまでのところ、これらはどうですか？ 涼しい。 MM-HM。 学生：[聞こえない]通常はメインint型。 あなたは、このためにそれを持っている必要がありますか？ 講師：だから我々はちょうど探していた ただ、実際のソートアルゴリズムで。 あなたが以内にそれを持っていた場合 より大きなプログラムのように、 あなたはint型のメインのどこかを持っているでしょう。 どこに依存 このアルゴリズムを使用して、 それは何決定するであろう それによって返される。 しかし、私たちのケースでは、我々は厳密にしている 実際にこれを行う方法を見て 配列を反復処理。 だから我々はそれについて心配しないでください。 だから我々は最良のケースについて話していたと バイナリサーチのための最悪の場合のシナリオ。 だから、やることも重要です 私たちの種類のそれぞれについて、その。 それで、あなたは最悪ですどう思いますか バブルソートの場合ランタイム？ 君たちは覚えていますか？ 学生：Nマイナス1。 講師：Nマイナス1。 だから、ある意味 nはマイナス1の比較。 だから、実現するための一つのことである 最初の反復でその、 我々は、比較、通過 これらはtwo--ので、それが1だ。 これらの二つ、三つ、四つ。 だから、1反復後、私たち すでに4比較を持っている。 私は、ランタイムとnについて話しているとき。 Nは、比較の回数を表す どのように多くの要素の関数として 私たちは持っている。 OK？ だから我々は、我々は4を持って、通過。 あなたが知っている次の時間、私たちにはありません このの世話をしなければならない。 我々は、これら2つを比較し、 これら二つは、これらの2つ、 そして我々はその最適化を持っていなかった場合は、 私が書いた4ループと、 あなたはとにかく、ここで比較されることになる。 だから、しなければならない アレイを介して実行 n個の比較のnを作る 回、毎回私たちのため それを介して実行するソート一つのことを私たち。 そして、我々はを介して実行するたびに アレイは、我々は、n個の比較を行う。 したがって、このための私たちのランタイムがある 実際にnの二乗いる 私たちの中でずっと悪いです そのため、最後のログ 我々は4を持っていた場合には意味 億の要素、それはだ 私たちに40億を取るつもり 代わりに32の二乗。 そうではない最高のランタイム、 しかし、いくつかのもののために、 あなたが以内なら、あなたが知っている、 要素の特定の範囲 バブルソートを使用するの罰金かもしれません。 [OK]をクリックします。 だから今最良の場合ランタイムは何ですか？ 学生：ゼロ？ または1？ 講師：だから1になる つの比較も。 右。 学生：Nマイナス1？ 講師：だから、ええ。 だから、nはマイナス1。 あなたは、nのようなコンセプトを持っているときはいつでも マイナス1、我々はそれをオフにドロップする傾向がある そして我々はちょうどあなたが持っているので、nの言う these--各対のそれぞれを比較する。 だから、1 nとマイナスであろう、私たち 私達はちょうど約nであると思います。 あなたは、ランタイムを扱っている場合には、 すべてがに近似している。 限り指数であるので 正しい、あなたはかなり良いよ。 それは我々がそれに対処方法を説明します。 最良のケースでは、nはあるように リストが既にソートされていることを意味し、 そして我々が行うすべてを介して実行されている それはソートだことを確認してください。 涼しい。 わかりました。 私たちは、ここで見るように ただ、いくつかの複数のグラフを持っている。 だから、nの二乗。 楽しい。 我々が見るように、nよりもはるかに悪化し、そして ログ2n個よりもはるかに、はるかに悪い。 そして、あなたはまた、ログのログに入る。 そして、あなたは124を取る、あなたが入る 狂ったようになっているログの星、などである。 だから、もし興味があるなら、 ルックアップログスター。 それは楽しみのようなものだ。 だから我々はこの偉大なチャートを持っている。 ちょうどヘッドアップ、このA 持っている素晴らしいチャート あなたの中期のための私たちのため あなたにこれらの薄くなりを聞いて長い。 だから頭までは、上でこれを持っているあなたの あなたの素敵なチートシート上中期 そこに。 だから我々はちょうどバブルソートを見ました。 最悪の場合、N N、最良の場合の二乗。 そして、我々は他の人を見てするつもりだ。 そして、あなたが見ることができるように、唯一の 本当によくないもの 私たちは、なぜに買ってあげるマージソートです。 だから我々はに行くつもりだ 次の1 here--選択ソート。 誰もがどのように覚えていますか 選択はソート働いた？ それのために行く。 学生：基本的に通過する 秩序と新しいリストを作成。 そして、あなたは要素を入れているのと同様に で、適切な場所にそれらを置く 新しいリストで。 講師：音になるよう 挿入ソートのようなより。 しかし、あなたは本当に近くだ。 彼らは非常によく似ている。 でも、私は彼らが時々混同取得。 このセクションの前に私は待つ、のようだった。 [OK]をクリックします。 だから、あなたがしたいもの やる選択ソートされ、 あなたが考えることができる方法 それと方法に関する 私は私が取得しないようにしようことを確認してください 彼らはそれが通過され、混同 それは選択 最小数とそれ あなたのリストの先頭にそれを置きます。 それは、その最初のスポットでそれを交換します。 彼らは実際に私のための例があります。 恐ろしい。 it--選択について考えるのでちょうど方法 ソート、最小の値を選択します。 そして、我々はするつもりだ 例を介して実行 私がいるために役立つと思うこと 私はビジュアルは常に助けと思います。 だから我々は何かから始める それは完全にソートされていないです。 赤は、ソートされていないとなります 緑がソートされます。 それはすべて秒で意味をなすでしょう。 だから我々は通過し、我々は反復処理 最初から最後まで。 そして、我々はOK、2は、言う 私たちの最小数。 だから我々は2を取るつもりだと我々はつもりだ 私たちのアレイの前面に移動します それはだから 私たちが持っている最小数。 だから、これはここでやっているものだ。 それはちょうど二人を入れ替えるために起こっている。 だから今我々は、ソートしている パートとソートされていない部分。 と覚えているのは良いものだ 選択ソート約 我々は唯一の選択しているある ソートされていない部分から。 ソートされた部分は、あなただけの一人で去る。 MM-HM？ 学生：どのようにそれが何であるか知っている それを比較することなく、最小の アレイ内のすべての他の値に設定します。 講師：それは、それを比較しない。 我々はそれをスキップしたい。 これにより、全体単に一般的である。 うん。 我々は、私はコードを記述する場合 あなたがより満足だろうと確信して。 しかし、あなたが最初にこれを保存する 最小の要素として。 あなたが比較します [OK]を、それは小さい、と言う？ はい。 それを維持する。 ここでは、小さくなっている？ いいえ？ これは、あなたの最も小さい あなたの値に再割り当てします。 そして、あなたは非常に幸せになるでしょう 私たちはコードを行くとき。 だから我々はそのように、その後、我々はそれを交換し、通過する 我々は、このソートされていない部分を見てください。 だから我々は3アウトを選択するつもりだ。 私たちは、でそれを上に置くつもりだ 私たちのソートされた部分の端。 そして、私たちはただやり続けるつもりだ それは、それをやって、それをやって。 だから、これはここでの擬似コードの私たちのようなものです。 私たちは、第二に、ここでそれをコーディングします。 しかし、単に何かが歩く 高レベルの貫通。 あなたがから行くつもりです iが0に等しいnはマイナス2。 それはまた別の最適化だ。 それについてはあまり心配しないでください。 ようにあなたが言っていた。 ヤコブは言っていたように、どのように我々を行う 我々の最小値が何であるかを追跡する？ どのように我々は知っているのですか？ 私たちは、比較する必要が 私たちのリストのすべて。 だから最小のiに等しい。 それはちょうど、この場合に言っている 私たちの最小値のインデックス。 だから、それはを反復処理するだろう jはiのプラス1に等しいから、それは行く。 だから我々はすでに知っている それが私たちの最初の要素です。 私たちは自分自身にそれを比較する必要はありません。 だから私たちは次のと比較することを開始 それはnまでのiプラス1である理由である1 マイナス1、 そこ配列の末尾。 そして、我々は、アレイであれば言った jは、配列minより小さい その後、我々はどこに再割り当て 我々の最小のインデックスである。 そして分として、私に等しくない場合 ここで、我々はここに戻って終わった。 私たちは最初にこの1をやったときに好き。 この場合には、で開始する ゼロ、それが2になってしまうだろう。 だから、minは最後に、私と等しくないであろう。 つまり、私たちがそれを知ることができます 私たちはそれらを交換する必要があります。 私は具体的な例のように感じる これよりはるかに役立ちます。 だから私はあなたたちにこれをコーディングします 今、私はそれが良くなると思う。 ソートは、その中でそのように動作する傾向があり それはちょうどそれらを見るために、多くの場合、良いでしょう。 だから我々が何をしたいです 我々は最初の最小たい 配列内のその位置にある要素。 まさにヤコブは言っていた。 あなたは何とかそれを格納する必要があります。 だから我々はここに開始するつもりだ 配列を反復。 私たちは、それが私たちだと言うつもりだ ちょうどで始まる最初の1。 だから我々はint型を持っているつもりされている 最小のiにおける配列に等しい。 だから、一つのことは、すべてのに気づくこと このループの実行時間、 私たちは一緒にさらに一歩始めている。 我々は起動すると、私たちはこの1つを見てください。 私たちは反復処理次回、 私たちはこの1つで開始している それに私たちの最も小さい値を割り当てる。 だから、バブルソートと非常に似ています 我々はその1パスの後知っている場合には、 この最後の要素はソートされます。 選択ソートと、 それはちょうど反対だ。 すべてのパスでは、我々は知っている 一つ目はソートされます。 第二のパスの後、 もう一つはソートされます。 そして、あなたはスライドの例で見たように、 私たちのソート部分はちょうど成長続けている。 だから私たちの最も小さい1を設定することにより、 アレイに私は、すべてがそれがやっている 何を収縮さ 我々としてそう見ている 数を最小限にする 比較の我々は作る。 それは皆に意味があるか？ あなたは私がそれを介して実行する必要がありますか 再び遅い、または別の言葉で？ 私はうれしいです。 [OK]をクリックします。 だから私たちは保存している この時点での値、 我々はまた、インデックスを格納したいと思います。 だから私たちは保存するつもりだ 最小の位置 ちょうど私であることを行っている1。 だから今ヤコブは満足している。 私たちは、格納されているものを持っている。 そして今、我々は目を通す必要がある 配列のソートされていない部分。 この場合には、このそう 私たちのソートされていないだろう。 これが私です。 [OK]をクリックします。 だから、私たちがやろうとしている forループになるだろう。 あなたがする必要がある場合は、必ず 配列を反復処理、 あなたの心には、forループに行くことができます。 いくつかのint kについてそう 私たちは何を思いますかequals-- kは、で開始することに等しくなるように起こっている？ これは私達が私達の最も小さいとして設定したものである 値、我々はそれを比較したい。 私たちは、それを比較するために何をしたいですか？ それは右、この次の1になるだろう？ だから我々は、kが初期化されたい 私はプラス1開始するまで。 そして、我々は、この場合におけるKたい私たち すでにサイズがここに保存されている、 私たちは単にサイズを使用することができます。 サイズは、アレイのサイズである。 そして、私たちはちょうどしたい 1ずつのkを更新します。 涼しい。 だから今我々は見つける必要がある ここで最小の要素。 だから我々は繰り返し処理をした場合、私たちは kで配列した場合、言いたい 私たちの最も小さいvalue--より小さい 私たちが実際にいる場所です 何を追跡する 最小here-- その後、我々は再割り当てしたい 私たちの最小値は何ですか。 これはああ、私たちはしている、ことを意味します ここを反復処理する。 どのような値がここにある ではない私たちの最も小さいもの。 我々はそれをしたくない。 我々はそれを再割り当てしたいと思います。 だから、我々はそれを再割り当てしている場合、何をすべきか あなたはここで、このコードにあるかもしれないと思いますか？ 私たちは再割り当てしたい 最小の位置。 だから今最も小さい何ですか？ 学生：配列​​のk。 講師：配列のk。 そして位置は今何ですか？ のインデックス何ですか 私たちの最小値はありますか？ それはちょうどKです。 そのように配列kは、kは、それらが一致。 だから我々はそれを再割り当てしたかった。 その後の後に私たちは最小のを見つけ、 forループこれの終わりにそう ここでは、発見した何を私たちの最も小さい 値があるので、我々はそれを交換します。 この場合、私たちのようなと言う 最小値はここにある。 これが私たちの最も小さい値です。 私達はちょうどである、ここでそれを入れ替えたい 一番下にどのようなことをスワップ機能 私たちはちょうど書いた、やった 一緒にカップル分前。 だから、おなじみのはずです。 そしてそれは単に反復処理します それはすべての方法に至るまでを通して あなたことを意味して終わり、に ソートされていないゼロ要素を持っている そして他のすべてがソートされている。 理にかなって？ もう少し具体的に？ コー​​ドのヘルプ？ 学生：サイズの場合、あなたは決して 実際にそれを定義したり、それを変更し、 それはどのように知っているのですか？ 講師：だから、一つのことに int型のサイズは、ここまでに気づく。 だから我々はこのsort--ソートで言っている この関数は、それがだcase--さ 選択ソート、それが渡された 機能付きで。 だからそれが渡されなかった場合 で、あなたが何かをするだろう 配列の長さを持つように またはあなたが反復処理だろう 長さを見つけるために。 しかし、それは渡されたので、 で、私たちはそれを使用することができます。 あなただけのユーザーことを前提としてい あなたに有効なサイズを与えたこと 実際に表している あなたの配列のサイズ。 クール？ 君たちは、これらを持つ任意の問題が発生した場合 以上の練習コーディングのソートをしたい 自分で、あなたがすべき study.cs50に行く。 それはツールだ。 彼らはチェッカーを持っている あなたが実際に書くことができます。 彼らは、擬似コードを実行します。 彼らはより多くのビデオやスライドを持っている 私がここで使うものも含めて。 あなたはまだ感じているのであれば 少しファジー、それを試してみてください。 いつものように、あまりにも、私に話してくる。 質問？ 学生：あなたが言っている サイズは、以前に定義されている？ 講師：はい。 サイズは以前に定義されている ここでは関数宣言で。 だから、それが渡されていますことを前提としてい ユーザーによる、および簡略化のため、 私たちはと仮定するつもりだ ユーザーは、私たちに正しいサイズを与えた。 涼しい。 だから選択ソートです。 Guysは、私たちは、今日多くのことを学習している知っている。 これは、セクションの密集したデータです。 それとだから、私たちは行く 挿入ソートに移動します。 [OK]をクリックします。 だから、その前に私たちはしなければならない ここに私たちのランタイム分析。 だから、最良のケースでは、 私がお見せした以降に付与された テーブルすでに私 種類のそれを譲った。 しかし、最良の場合ランタイムは、私たちは何を思いますか？ すべてがソート。 Nは二乗。 誰でも説明してい あなたが考える理由のために？ 学生：あなたはthrough--比較している 講師：右。 あなたはを通して比較している。 にもかかわらず、すべての反復で 私たちは、1によって、これをデクリメントしている あなたはまだを通して検索している 最も小さいものを見つけるためにすべて。 だから、たとえあなたの最小値 初めにここにある、 あなたはまだそれを比較している 他のすべてに対して それは最も小さいことだことを確認します。 だから、通る終わるだろう 約n倍の二乗。 わかりました。 最悪の場合は何ですか？ あなたが行っているので、また、n個の二乗 その同じ手順をやっている。 したがって、この場合には、選択 ソート何かを持っている 我々はまた、予想されるランタイム呼び出すことを。 だから、他の人に、私たちは知っている 上限と下限。 どのように狂気に応じて、私たちの リストであるか、それがどのようにソートされていない、 彼らは、nまたはn乗の間で変化する。 私たちは知りません。 しかし、選択ソートは、同じを持っているので ことを教えてくれる最悪と最良の場合、 入力に関係なくどのようなタイプの、我々 それが完全だかどうか、持っている ソートまたは完全に それはだ、ソートされたリバース 同じ時間がかかるだろう。 その場合だから、あなたの場合 私たちのテーブルから覚えている、 実際には、その値を持っていた これら二つのソートは、持っていない そのランタイムが期待されている。 だから我々はいつでもことを知っている 我々は選択ソートを実行し、 それがに保証さだ nの二乗の時間を実行します。 そこにはばらつきがありません。 それは、単に期待だ。 そして、再び、あなたが知りたい場合は より、春のCS 124を取る。 わかりました。 私たちはこの1つを見てきました。 涼しい。 だから、挿入ソート。 そして私はおそらくつもりです このを通じて燃え盛る。 私はあなたたちはそれをコーディングしていません。 私達はちょうどそれを歩くだろう。 だから、挿入ソートは、一種である 選択ソートと同様の その中で、我々は両方のソートされていないを持っている とアレイの一部を選別した。 しかし、何が異なるのは、ということです 私たちは一つ一つを通過として、 私達はちょうど何でも数を取る 私たちのソートされていない中で隣にあり、 そしてそれを正しく並べ替える 私たちのソートされた配列に変換する。 これは、例を挙げてより多くの意味をなすでしょう。 だから、すべてがソートされていないとして開始、 ただ選択ソートで好きです。 そして、我々はこれをソートするつもりだ 我々がされているように昇順。 だから私たちの最初のパス上の 我々は最初の値をとる 私たちは、OK、あなたは、言う 今自分でリストにある。 あなたは、リストにあるため、 自分で、あなたが並べ替えられています。 であることのためにおめでとう この配列の最初の要素。 あなたはすでに自分ですべてをソートしています。 だから今我々は、ソートしている そしてソートされていない配列。 だから今我々は最初を取る。 ここで何が起こるの間 そして、ここで、私たちが言うことです [OK]を、我々は見てするつもりだ 私たちのソートされていない配列の最初の値 私たちは、その入力にそれを行っている ソートされた配列内の正しい場所。 だから我々は5を取るされている私たちは何をすべきかと 我々は、[OK]を、5は3よりも大きい、と言う 私たちはちょうどそれを挿入 その右に。 我々は良いよ。 それでは私たちは次のものに行く。 そして、我々は2を取る。 私たちは、[OK]を、2未満である、と言う 3よりも、私たちはそのことを知って であることが必要 今私たちのリストの正面。 それでは私たちは、私たちがダウンして3と5をプッシュです そして我々はその最初のスロットに2を移動します。 だから我々はちょうどに挿入している それがあるべき正しい場所。 その後、我々は我々の見 次は、私たちは6と言う。 [OK]を、図6は、より大きい 私たちのソートされた配列のすべて、 私たちは終了間際にそれを上のタグ。 そして、我々は4を見てください。 図4は、6未満であり、それは以下の 5よりもそれが3より大きいです。 だから我々はちょうどに挿入 3と5の間の中間。 これほど少ないことを確認する もう少し具体的な、 こちらの一種である 何が起こったのかのアイデア。 各ソートされていない要素についてだから、私たち どこでソートされた部分で決定 それは。 だから、念頭に置いて ソートされ、ソートされていない、 我々はを通して横断する必要があり、図 それはソートされた配列に収まり場所を。 そして、我々はシフトすることによって、それを挿入 その右側にダウン要素。 そして、我々はちょうど続ける 私たちまでを反復 完全にソートされたリストを持っている 今やゼロソートされていないです ソートが占め 私たちのリストの全体。 だから、再び、さえ物事を作る より具体的な、我々は擬似コードを持っている。 そこで、基本的に、私はあるために nはマイナス1と0に等しい、 それが私たちの配列の長さだけです。 私たちは、に等しいいくつかの要素を持っている 最初のアレイまたは最初のインデックス。 私たちはそれと同等のJを設定します。 jはより大きいながらそう ゼロと配列、Jマイナス1 より大きい 要素、すべてのようにやっている ことを確認している あなたのjは本当に表し 配列のソートされていない部分。 だから、物事がまだある一方、 マイナス1を並べ替えるとjすることが何をis-- 要素、彼女は何ですか？ Jはここで定義されていませんでした。 それは迷惑なのようなものだ。 [OK]をクリックします。 とにかく。 だからJマイナス1、あなたがチェックしている その前の要素。 [OK]をクリックすると、要素であり、言っている 私がみましょうam--どこの前に 実際にこれを引き出す。 それでは、これは言わせて 私たちの第二のパス上のような。 だから私は同じになるだろう 1に、これはここにある。 だから私は1に等しいことになるだろう。 これは、図2、図4、図5、図6、図7であろう。 わかりました。 この場合はそのように私たちの要素 4に等しくなるだろう。 そして、我々はいくつかのJを持っている 1に等しいことになるだろう。 ああ、jはデクリメントされる。 つまり、それが何であるかです。 だから、jはiのに等しいので、これは何ですか ことわざは、我々が前進するようにということで、 我々は念の作っている 我々は終わっていないだということ 私たちがしようとしている。このようにインデックスを付ける 私たちのソートされたリストに何かを挿入します。 そこでjが、この場合、1に等しいとき そう配列jのマイナスひとつ選ぶ配列jはマイナス1 それはだ場合は、このcase--で2です 要素よりも大きく、 その後、このすべてをやっている 物事をシフトダウンされている。 この場合、アレイのjから1を引いたので 2である配列ゼロ、であろう。 図2は、4以下である これは実行されません。 だから、シフトは下に移動しません。 これは、ここで行うことはただです あなたのソートされた配列を下に移動する。 この場合、実際には、我々 do--できたのは、この3を作成してみましょう。 だから、私たちが通って歩いているなら この例では、我々はここで、今だ。 これがソートされます。 これがソートされていないです。 クール？ だから私はそのように、2に等しく、 我々の要素は3に等しい。 そして、私たちのjは2に等しい。 だから我々は我々と目を通す [OK]を、配列jはマイナス1である、と言う 要素よりも大きい 我々は見ていることを？ そして答えは右、yesです？ 図4は、図3およびjよりも大きい 2であるので、このコードが実行されます。 だから今我々が配列を何 図2は、右ここので、私たちはそれらを交換。 だから我々はちょうど、[OK]を、配列を言う 2時現在、3になるだろう。 jは等しくなるように起こっている 1であるJマイナス1、。 それは恐ろしいですが、 あなたたちは、アイデアを得る。 Jは今1に等しい。 そして配列jはちょうどになるだろう 4であった私たちの要素に等しい。 私はいけない何かを消去 何かを持っているか、miswrote、 しかし、あなたたちは、アイデアを得る。 それは、nで移動。 これがあった場合には、その後、ループだろ 再び、それはOK、jは、今1である、と言うでしょう。 およびアレイjはマイナス1は今2である。 図2は、私たちの要素より小さい？ いいえ？ それは我々がしたことを意味します この要素を挿入する 私たちのソートされた配列内の正しいスポットで。 その後、我々はこれを取ることができ、我々は言う、 [OK]を、私たちのソートされた配列はこちらです。 そして、それはこの数6を取るとなります のように、[OK]を、この数値より6少ない？ いいえ？ 涼しい。 私たちはいいですよ。 再びそれを行う。 我々は7を言う。 端より7少ない 私たちのソートされた配列の？ いいえ。 だから我々はいいですよ。 だから、これはソートされるだろう。 基本的にすべてこのことを行い それはテイクを言っているされている の最初の要素 あなたのソートされていない配列、 それがどこに行くかを把握 あなたのソートされた配列中。 そして、これは単に面倒を見る そうするスワップの。 あなたは基本的にスワッピングしている それは右だったと評価されるまで。 視覚的なイメージは、あなたがしているということです そうすることによって、すべてのものを下に移動する。 だから、ソート風の半分バブルのようなものだ。 研究50をチェックしてください。 私は非常にしようとお勧めします 自分でこれをコードに。 あなたはすべての問題を持っているか、あなたがしたい場合は 挿入ソートのためのサンプルコードを参照してください。 私に知らせてください。 私の周りは常によ。 そこで最悪の場合の実行時 そして最良の場合のランタイム。 あなたは男私はすでに表から見たように あなたにあった、それは両方のN乗とn。 とても親切の私たちが話したもののオフに行く 我々の以前の種類と程度、最悪 ケースランタイムがあればということです それは完全にソートされていないですが、 我々は、これらのn回のすべてを比較しなければならない。 我々は比較の全体の多くを行う それは逆の順序でのifなぜなら、 我々は、[OK]を、これを言うつもりだ これは良いですが、同じであり、 この1つを比較する必要があります 最初の1に対して後方に移動する。 そして、私たちは向かって取るにつれて テールエンドは、我々は持っている 、コンペアすると、 すべてに対して比較。 だから、なってしまう 約n乗。 それは、あなたが正しいだ場合 あなたは良いしている、2、[OK]を、言う。 図3に示すように、あなたは2と比較している。 あなたは良いね。 4、あなただけのテールと比較。 あなたは良いね。 図6は、あなたがいいですよ、テールと比較。 だから、すべてのスポットのためにそれは既にだ場合は、 ソートは、1つの比較を作っている。 だから、ちょうどn個だ。 そして、我々は最良のケースのランタイムを持っているので、 nとnの最悪の場合の実行時の 乗、我々は、予想されるランタイムを持っていません。 それはちょうどに依存 そこに私たちのリストの混乱。 そして再び、別の グラフと別のテーブル。 種類の違いそう。 私はちょうどを通してそよ風するつもりです、私 私たちは広範囲に話したように感じる どのようにすべての種類の約 の変わりと一緒にリンクします。 だから、マージソートすることは最後のものである 私はあなたたちを産んだものとします。 我々はかなりカラフルな絵を持っている。 だから、ソート再帰アルゴリズムであるマージ。 だから、あなたたちは何を知っていますか 再帰関数はありますか？ 誰もが言いたい？ あなたは試してみたい？ だから、再帰関数はただである 自分自身を呼び出す関数。 だから、あなたたちは精通している場合 フィボナッチ数列と、 そのためには、再帰的なものとみなさだ あなたは前の2つを取る と一緒にそれらを追加 あなたの次のいずれかを取得します。 私はいつも思うので、再帰 スパイラルなどの再帰の ので、あなたはそれにダウンスパイラルのようにしている。 しかし、それは単なる関数です それは自分自身を呼び出します。 そして、実際に、本当にすぐに私 それがどのように見えるかをお見せすることができます。 私たちが見れば、ここでそのように再帰的な、これは 配列をオーバー合計する再帰的な方法です。 だから、すべて私たちがやることです 我々は、合計機能を有する 大きさや配列を受け取り合計。 そして、あなたが気づけば、サイズ 1ずつ減少します。 xが等しい場合およびそれがないすべてである zero--もしそうであれば、配列のサイズ それがゼロを返しzero--に等しい。 それ以外の場合は、これを合計し 配列の最後の要素、 その後の和をとる 配列の残り。 だから、ちょうどそれを破壊している より小さな問題に変換する。 長い話を短く、再帰、 自分自身を呼び出す関数。 それはあなたがこのの外に出たすべてだ場合は、 それは再帰関数が何であるかです。 あなたは51を取る場合は、あなたは非常に取得します、 再帰と非常に快適。 それは本当にクールだ。 それは次のように意味を成していた 午前3時から1つの夜。 そして、私は、なぜ、のようだった 私はこれを使用することはありませんか？ マージソートのためにそのように、基本的に 何それを行うために起こっていることは、それがだです それを打破し、それを破るつもり それだけで一つの要素になるまでダウン。 シングルの要素は並べ替えが容易です。 我々はそれを参照してください。 あなたは一つの要素を持っている場合、それはだ すでにソートされたと考えた。 だから、n個の要素の入力で、 nが2未満である場合、 ちょうどことを意味するから戻す それは我々が見てきたように、0または1のどちらかです。 それらは、ソートされた要素が考慮されます。 そうでない場合は半分にそれを破る。 第二のソート、前半を並べ替える 半分、次にそれらを一緒にマージする。 なぜそれがマージソートと呼ばれています。 我々はこれらを並べ替えるよだから我々はここにある。 だから我々はそれらを持つ保つ 配列サイズが1になるまで。 それは1だときに、私達はちょうど返す これは、ソートされた配列であるため、 これは、ソートされた配列であり、それはです ソートされた配列は、我々はすべてのソートしている。 それでは、私たちは何をすべきか、我々はある それらを一緒にマージし始める。 あなたができるような方法 マージがある考える あなただけ小さくを削除 サブアレイのそれぞれの数 ちょうど浮上し、配列に追加します。 だから我々が持っているときに、ここに見れば これらのセットは、我々は、4,6、及び1を有している。 我々はこれらをマージしたい場合は、 我々はこれらの最初の二つを見て そして我々は、OK、1の方が小さい、と言う、 それはフロントに行く。 4と6、比較するものはありません それは、終了間際にそれを上のタグである。 我々はこれら二つを組み合わせるとき、私たちだけで これらの2つの小さい方を取る そう、それは1だ。 そして今、我々は取る これら2、SO 2の小さい方。 これら2、3の小さい方。 これら二つの、4、5、6より小さい。 だから、あなただけのこれらをオフに引っ張っている。 そして、彼らがしたので、 以前にソートされて、 あなただけのものを持っている 比較そこに毎回。 ここので、より多くのコードだけ表現。 だから、途中で開始し、 あなたの並べ替え、左右 そして、あなたはちょうどそれらをマージ。 そして、我々はコードを持っていない マージのために右ここに。 しかし、再び、あなたは上に行く場合は、 50を勉強、それはそこでしょう。 そうしないと私に話を来て あなたはまだ混乱している場合には。 だからここにクールなことは、最良の場合で、 最悪の場合、および予想されるランタイム 、nはすべてログに記録されている 私たちがしたよりもはるかに優れている 私たちの種類の残りのために見られる。 我々は、n乗を見てきました 実際に、どのような私たち 偉大である、nはn個のログですここに来る。 つまり、どの程度改善を見てください。 このような素敵な曲線。 だから、はるかに効率的。 あなたは今まで、ソートマージ使用することができます。 それはあなたの時間を節約できます。 その後、再び、私たちが言ったように、もし あなたは、この下部領域にダウンしている それはそれを行いません 大きな違い。 あなたは、何千も起きる と入力の何千人も、 あなたは間違いなくしたい より効率的なアルゴリズム。 すべてのと、再び、私たちの素敵なテーブル あなたたちは、今日学んだ種類。 だから私はそれが密な日だった知っている。 これは、必ずしも予定されていません あなたのpsetのお手伝いをします。 しかし、私はちょうど免責事項を作りたい そのセクションはただのpsetに関するものではありません。 すべてこの材料は、公正である あなたの中間試験のためのゲーム。 そしてまた、あなたがしなければ、CSを続行、 これらは、本当に重要な基礎である ことをあなたが知っている必要があります。 だから、何日かは次のようになります もう少しPSETヘルプ、 しかし、いくつかの数週間は次のようになります ずっと実際のコンテンツ それはスーパー思えないかもしれません 今のあなたに役立つ、 あなたが続けば、私は約束します 上は非常に、非常に有用であろう。 だから、セクションのためにそれだ。 ワイヤーにダウン。 私は1分以内にそれをやった。 しかし、そこに行く。 そして、私はドーナツやキャンディーを持つことになります。 アレルギー誰もがする​​ことです ところで何でも、？ 卵と牛乳。 だから、ドーナツはありませんがありますか？ [OK]をクリックします。 わかりました。 チョコレートなし？ スターバースト。 スターバーストは良いです。 [OK]をクリックします。 私たちは持っているつもり その後来週スターバースト。 それは私が買ってあげるものです。 君たちは素晴らしい週に持っている。 あなたのスペックをお読みください。 ご質問があるなら、私に教えてください。 PSET 2グレードがあるべき 木曜日によってあなたに出。 あなたが質問があれば 私は何かを段階的方法については、 またはなぜ私は道私が何かを等級分け 、私に話を来て、私にメールしてくださいました。 私はこの小さなクレイジーだ 週、私は約束します 私はまだ24時間以内に返信されます。 だから、偉大な週皆を持っている。 あなたのpset上の幸運。