[Powered by Google Translate] [第3週は、続く] [デビッド·J·マラン - ハーバード大学] [これはCS50です。 - CS50.TV] かしこまりました。お帰りなさい。これはCS50であり、これは3週目の終わりです。だから慣れていない人、昨年のハーバード大学は、イノベーション·ラボと呼ばれるものを立ち上げ HBSのキャンパス内に川を渡って素晴らしい建物ですまたはi-ラボ、それは大学生、GSAS学生、すべてにわたってキャンパスからの学生に開かれている教員を含めて、それは革新的なもので動作するように一緒に来る場所ですが、特に起業家の事あなたと0個以上の友人が起業家の何かを考えているのならこのクラスの中に、このクラスの後、またはそれ以降のいずれか。だからJの期間にわたり、彼らがやるべきことのひとつは、これらの旅行であり、の一つはニューヨーク、シリコンバレーになっているものになります。スペースが非常に限られているが、それはMBA取得者と肩をこする機会だと大学院生キャンパス全体と実際にはそれぞれの分野での時間を過ごす、スタートアップを起業チャットをチャットなどが挙げられる。興味があればそこで、ここでは、次のURLをご覧ください。また、オンラインスライドで提供されています。我々はトーンダウンして家のオーディオを少しだけもらえますか？あなたは今週の金曜日ランチにご参加を希望される場合は、ファイアー＆アイスで1:15 pmは、そこに向かうください。フォームが既にあなたがそこに着く時間によって満たされている場合の謝罪。しかし、我々はこの伝統以降を続けていきます。今日、私たちは、私たちが解決できることを様々な問題のより高いレベルの議論を続ける少なくとも、コード上で、はるかにアイデアに今日、あまり焦点を当てています。だから、我々は半分に電話帳を引き裂いたときに戻って0週に思うの目的は、確かに、何かを少し劇的なものであった必ずしも、検索がでなければならない点を送信するには、あなたが思うように一見して明らかなように。そして一般的に、問題解決は、必ずしも常に最善ではないかもしれません - 最も明白な解決策は、必ずしも最善ではないかもしれません。だから我々は、率直に言って、この部屋に私たちのすべてが本能を持っていた、この電話帳を持っていたし、最も可能性の高いマイク·スミスを探しているときに途中で起動して、左または右に移動します私たちは結局、たまたまアルファベットの何文字目に基づく。しかし、私たち人間はあまりにも長い間、当たり前のことができるものとし、単純なアイデアが本当にあなたの心の最前線に来て開始する必要があります問題ははるかに複雑な電話帳より得るために、それらと同じように、簡単な操作、華麗な洞察が私たちを許そうとしているものであるはるかに複雑で、より興味深い問題を解決するために、近頃はすでに当たり前にそれらの間のいくつかを紹介し、我々はかかる。そこにWebページの数十億、まだGoogleとBingなどそのように私たちのために何かを見つけることができます。それはすべての可能なWebページを検索し、線形探索を用いて、何が起こっていない。 Facebookは、すべてのあなたの友人の友人の友人であるか、誰なのかを伝えることであるとあまりにもがこれらの日の一瞬に、一見行うことができること彼らは数百万人のユーザーを持っているにもかかわらず。そして、我々が実際にその規模で問題を解決する方法を最終的に削減しますアイデアを我々は今日、もう少し0週で見て。我々に再実行されません、このアルゴリズムが、我々はまた、0週目にこの練習をしたリコール私たちは誰もが立ち上がったところで、1番を取るそれから私達は、一緒にあなたの番号を追加、オフペアリングすることによって、誰もが自己のカウントを持っていたその後ギャングの半分は反復ごとに腰を下ろした。だから我々は500人250から125に行ってきましたなど。そこに我々は月曜日に言ったように、強力なアイデア我々はその問題の大きさを倍にした場合ということでしと正義またはEC 10からすべての子供たちが部屋に戻ってきて、私たちに参加まあ、我々はおそらくその全体集合グループをカウントすることができループのちょうど1より大きい反復で彼らだけ多分サイズが倍になるので、またはEC 10の場合にビット以上のサイズを倍にする。そして私たちは、もう少し時間を費やさなければならないでしょうしかし、我々は400または700以上のステップを費やす必要はありません。ほんの少し抽象的な方法でこの絵を描くために、全員が立ち上がっていませんしてみましょう。しかし、今日のオーケストラに座ることにしましたあなたの人々は気にしないのであれば、立っ我々が最も高い人が誰であるかをあなたがたのうちに見つけ出すことができるかどうかを確認してみましょう比較アルゴリズムと同じ種類のものをすることによって。あなたはオーケストラ、私の謝罪が、ステップ1で座っているのであれば、立ち上がる。ステップ2では、あなたが近く誰とペアになる、背が高い人を把握し、短い場合座る。その後繰り返す。 [学生がさらさら] オーケー。オーケー。一つは、放置されています。あなたの名前は？ >>アンドリュー。アンドリュー、今日はオーケストラ·セクションで最も高い人です。おめでとうございます。 [拍手と歓声]オーケー。座席を持っている。だから我々はアンドリューを発見した。しかし、どのくらいの時間がアンドリューを見つけるために、例えば、私にかかっていたでしょう 50歳かそこらの人々のこのオーケストラセクションの？私はかなり単純なアプローチをとっており、ここから始めている可能性があります。そして、私は2人が立ち上がっていると私はちょうどそれらを比較その後、私は若干短くなって誰に言って、 "さて、あなたは、座って" と私は背の高い人が誰であったか覚えているつもりです。それから私は、繰り返し繰り返し、繰り返し、私が一番背が高いの人にハングアップする私はその時点で、それらよりも、誰かが少し背が見つかるまでわずかに短い人がダウンして座っている。しかし、このオーケストラのセクションにあるアルゴリズムで、もし、あなたのnそこどのように多くの手順は、そのアルゴリズムはかかるとしている？ >> [生徒] N. それは、最悪の場合には、いわばので、右、nを取るつもりです最も背の高い人は、私だけランダム不運によって得ることは非常に最後の一人です。だから、最悪の場合には、そのアルゴリズムの実行時間が線形である、それは、Nのここで、nは、空間内の人々の総数は、問題の大きさです。このアルゴリズムについてはどうですか？あなたは、すべて立ち上がってから、再度あなたの半分座っているという事実あなたの半分は座って、あなたの半分は座った。ここでのnがある場合、その何措置を講じている必要がありますか？ [学生] Nログn。悪化するだろう。>> n個のログを記録します。だから、あなたはかなり対数とは何か覚えていない場合でも、ログn 今のところ、それはこの半減と半減と半減に何とか関係していることに感謝します。それは2倍にする必要はありません。それは、3つの要因である可能性があります。しかし、それは問題の大きさがここから始まることをそのような要因の同じ種類のこの繰り返しだしかしその後すぐに次にここ、ここ、次に、ここ、ここに行く。あなたが問題の小さい刺されを取り出していない、あなたは本当にそれで離れてチョッピングしているビッグで急襲するたびに落ちた。だから我々は、12½または13人が立った後、その後、25％、50人がいたやっとちょうどアンドリューが放置したまでなどその後の6½と。だから我々はnのそのログを呼び出すつもりだし、次のようにあなたはこれを視覚化することができます。線形アルゴリズムが赤い線のようにここで、ここでこの絵を思い出してください黄色の線は、我々は学生をカウントするために使用すること2Sアルゴリズムでカウントしていた過去に、今日は聖杯は、この緑の線のままになるだろう私たちはオーケストラのセクションの人々の数を倍増した場合、または単に言わ場所、地獄のような大したこと、立ち上がるのは、全体の室内の全員を持っていないようにしましょう私たちは、大体ここでどのように多くの人がダウンしているので、ダブル、 1以上の繰り返し、問題ではありません。我々は、アンドリューまたは誰アンドリューより背が高いことを起こることがわかりました中二階やバルコニーインチ電話帳に付与された私たちがそんなにかかったこの単純なアイデアだから、我々はそれを適用することができるので、さまざまな場所があることを認識しています。、第一実際にではなく、専門用語 - ちょうどいくつかの専門用語を平手打ちする私はここにこの絵に行きましょう。今、私たちは、nとn / 2について語った後、nの対数私たちは学期のコースで意志としてではなく、我々は確かに、思い付く実行時間のこの一般的な概念を説明する数式の他の並べ替え。長い前に、我々が表示されますので、これらは今の文脈から外れているこれらは実際に表しているアルゴリズム。しかし、ここで気付く直線nの直線は、現在のポインティング実際には非常に低いです。それは我々がちょうどx軸が何を表しているかを変えるという点で、目の錯覚のようなものだ y軸は、我々は我々が望む任意の方向に直線ポイントを作ることができます。しかし、それは、今では一見フラットだという理由我々ははるかに遅い実行時間はこのグラフ上のスペースを作るために必要とされるためです。現時点では、生活の中でいくつかの非常に悪いアルゴリズムがあることを知っている、そのうちのいくつかは、n個のステップを取るか、いっそのこと、nステップログオンしますが、よりありません。だからライン上記nここ底予告でnのn回ログが、そこそして我々はずっと前にこれが何を意味するかわかります。その上にはnの二乗、そして我々はまだ、任意のn乗のアルゴリズムを見ていないが、我々がしようとしています。そして、それは本当に悪いよう。 2はさらに悪く感じるN、指数関数的に何か、にあります。しかも、不思議なことに、その後、あなたが先に考えるのソートならnの三乗は、そこ実際にnに数学、2を行うのには、種類が非常にまっすぐになった場合、 nよりもはるかに高いアップあなたが十分出軸を見れば三乗。そこで、これらの軸はx軸上に任意に2〜10アールたった今気づく。そして、それは何を意味するのか？部屋の中で10人に2人を意味している。問題の大きさ、文脈が何であっても：それはすべてのxの手段だ。縦軸は現在秒ステップ数の数です - 時間のいくつかのユニット。しかし、それは0から60と0から10までだということに気づく。しかし、もしあなたがExcelまたはいくつかのチャートソフトでのかもしれませんが、ズームアウトの我々は親切で、そして我々は、20万に上がる2のようなnに、何かに気づく完全乗nの実行時間を圧倒しようとしている、 nは乗は、nログn - 私たちはこれまでについて話したことのすべて。あなたは、Facebookのようなものについて話し始めるときに、まだキャッチですあなたは多くの、多くの、多くの人々が相互接続されたすべての場合にあっては、あなたが人々をnした、それぞれの人は、nの友人のように多くの可能性があり誰もが世界で大の仲良しの一種である場合、まあ、既にn倍のnそのため、そののn乗可能友情、少なくとも1つの方向は、n乗可能友情インチだから、Facebookのソーシャルグラフを検索することをすでに示唆している、いわば、式のこれらの種類で表現することを開始することができます。我々は、戻って来て、これははるかに具体的にするだろう次の何週間もなく、今のところ、客観アルゴリズムやコードの実装について行かないことを確認するために起こっているそのようなものと同じくらいの時間を割いてまで終了。しかし、コンピュータ·サイエンスについての魅惑的な事は、あなたは、このフィールドに進み場合、CS121、CS124のようにクラスを理論のコースはどちらも取って、この世界に存在するいくつかの問題が実際にあるということです根本的に、私たちの知る限り、それ以上速く解くことができないことこれらのグラフの最悪よりも実際に示唆している。だから、人間がこれまで持っているよりもはるかにうまくやるために、この世界では、オープンな問題が多数あります。したがって、この例でそれから始めましょう。我々はあまりにもぎこちなくビデオでは、このカメラでショーンの闘争を見た。ショーンは、このようにボード上の7番を見つけることを任務とされたときしかし、現実には、あった私は "これらの紙片や白扉の向こうのどこかにある、と言ったことを思い出す "7番。ショーン、私たちのためにそれを見つける。" そして、それは見ていて驚くほど下手だっ彼は本当にこの問題に苦しんでいたからです。しかし、現実には、ショーンが部屋の中で誰もがやっていることができるだけでなく、やっていた。彼は、典型的な人かもしれないよりも少し時間がかかりましたしかし彼は、この問題にはいくつかのトリックがあったと仮定彼は何かが欠けていたと仮定した。そして、それは目の数百が彼に迫ったことを助けていない。しかし、現実には、問題への入力が乱数の束である場合であっそしてあなたは、1等番号を見つけるために求められているあなたができる最善のは、線形検索です。左から始まり、右に移動したり、左に移動し、右から始まります。遡及的に、我々は考えるかもしれませんが、 "ショーン、なぜあなたはもう一方の端から開始しませんでした？" まあ、7は同じように簡単に、無作為にここにあったかもしれない私は彼が年末に開始することはないだろう考え出したので、私は意図的にそこに置く。だから私は、一種の状況を操作しますが、偶然7がどこだったかもしれない。だから右端から開始すると、改善してあったかもしれませんしかし、私は他の場所で7を動かす何来年場合はどうなりますか？それが問題の根本的に新しい解決策ではありません - 1端または他のから始まる - あなたが他の仮定を与えられていないしているとき。だからショーンは数字を探し始めたと彼は言った、 "5。それはここではありません。" それから彼は、ここに行って、19を見て、その後、彼は約20秒間一時停止その後、彼は13のためにこれを開けると、それが明らかになりましたここにパターンがあるように思えないこと。それは、1、2、3、4等はありませんでした。助けにはならなかった数字のギャップはありました。そして、あまりにも、私は数字をカバーするために、紙のこれらの安価な部分を使用しているという事実なぜなら私は、紙のすべてのこれらの部分を削除した場合、実際には意図的なもので私たちのほとんどは、ショーンが含まれている、おそらくある種の肉眼ちらっと見ただろう黒板でと "ああ、7は右が明らかだ"と述べた。私たちは、即座にそれをやった。そして、それは、人間の脳がある程度機能する方法かもしれないしかし、現実には、彼の目や心は、おそらく右から左へ番号スキミングでしうちの真ん中、左から右へ - 何かが生理的に起こっていたそれは瞬時に起こっていたようにそれは感じたことなど、しかし、オッズは、内部的に7を見つけるための方法論のいくつかの種類があったとしても、そこにあります。そして実際に、今、私たちは、配列とデータ構造の話をしていることをコンピュータのメモリと内側、私たち人間ができる唯一のこと同時に個々のメモリ位置1を見ています。したがって、すべての他の場所も同様に紙のいくつかの作品で隠蔽される可能性があり我々はとにかくそれを見ることができないため。我々は一度に1つのことを行うことができます。したがって、この場合には、ショーンの場合には、我々はここに行きましたし、我々はここに行きましたその後、我々はここに行きました、ここ、ここ、ここ、年末までに巧妙だとだけの種類は任意にこれをスキップして、そこに7を発見した。この1つは、特に特別なものではありませんでした。それはあまりにも狂った。しかし、彼は最終的に7を発見した。しかし、今は持ち帰りは本当にあなたができる最善の情報を全く与えられなかったときにということであるランダムに並べ替え数字以外の左側から開始するか、右から開始することです。または一体、ランダムに扉を開くことができますが、その時でさえ、何それはランダムであることが意味するのでしょうか？さて、私たちは、何とかそれはここに開始するために何を意味するかを正式なものにする必要があると思います次にここに行き、その後、ここに行く。ショーンはよくやった、それは見ていて楽しいだけだった。可能ならば、代わりに我々は、問題を少し変更して、今年のショーンを持ち出す場合はどうなりますか？誰もがステージに上がってくるとわずかに異なる問題を解く快適になるとカメラに表示される？君たちは非常に今日既に関与してきたための、オーケストラを超えて行こう。方法についてはピンクで、帽子の中に？ダウンさあ。あなたの名前は何ですか？ >>アレックス。 >>アレックス。オーケー。だからアレックスは、今年のショーンとなり、今後数年間に表示されます CS50講義の価値がある。アレックス、あなたに会えてうれしい。あまりにもよろしくお願いします。>> あなたのために目の前にある試練は、あなたはそれが少し楽に持っているということですという点で、私は、同じ数字がここにありますが、それらは今ではソートされているあなたに言っています。だから今、あなたの目標は、7番を見つけることです。そして実際に、我々は実際にこれをしなければならない - 不正行為のyou're種類を、コンピュータ好きではないだろう、何を見て、数字は少し前だった。チョークで、これは実際にすべてのその多くを支援するつもりはないが、しかし、あなたが、元の配列が何であるかを知らないことを考えてみましょう。あなたが今知っているすべてはあなたがソートされた数字の配列を持っているということですそれはそれらの間のギャップがあるかもしれませんが、あなたの目標は、7番を見つけることです。どのようにして、合理的な人間は、7番を発見すればよいのでしょうか？ローからハイへ行く？オーケー。>>安いものから高いものへ行く。それらをはがすません。我々はそれらを再利用できるように、単にそれらを持ち上げてみましょう。わかりましたので、1。待ってください。あなたが続ける前に、それは、明らかに間違って1でした。それでは、次のあなたの心を介して起こっているのでしょうか？あなたの次の一手は何ですか？次の1。オーケー。>>次の1。グッド。そう間違った3。あなたの次の一手は何ですか？行き続ける。 >>すべての権利。行き続ける。 5。だから行き続ける、と私は後世のためにあなたにこれを渡すことができます。 7。優秀。>>非常に良い。 7番を見つけました。 [拍手] だからそれは良かったけど、ショーンはあまりにも数が7を発見した。そして、私は、あなたが本当にこの情報の追加部分を悪用していないことを主張するこれは、これらの番号がソートされていることである。だから我々はより良いことができますか？ここに任意の提案ですか？ええ、戻ってインチ [学生]はバイナリ検索。 >>私はバイナリ検索が何であるか見当がつかない。 [学生]途中でスタート。 >>真ん中にスタート。オーケー。だから我々はそこに着くことができるかどうかを確認してみましょう。代わりに、もしそうならあなたが先に行くと、真ん中のドアを開けて、真ん中からスタートするそうだ。そこにそれらの8ですので、あなたは任意にどちらかを選択する必要があるとしているわずかに左または右に。オーケー。 7！非常に良い[拍手]。さて、しかし、我々はこれでどこに行っていた？ちょうどあなたがここに始まったタイを破るために仮定してみましょうその等しく同様に起こったかもしれないので。我々は、ちょうど7があったことを知っていることを起こった。だから、これは13です。だから彼らはソートしていると我々がちょうど中央で開始された場合、最適な次の一手は何だったでしょう？左に行く。ので、ここでは電話帳の例では、再び来る。 13はここにあり、私たちは、リストがソートされているわかっている場合は、その後、紙のこれらの作品のすべてが今、私たちにつまらない我々はすでに7が左側になければならないことを知っているので、これらの数字はソートされ、我々は13を発見された場合。だからここにあなたの次の一手は何ですか？ >>が左に移動します。 >>さて、良い。だから左に移動し、 - ちょっと、ちょっと、ちょっと、待って。それは浮気だ。だから、7を見つけましたが、我々だけで適用されるアルゴリズムは何でしたか？途中で開始します。グッド。>>だから同じ考えの論理的な拡張子は何ですか？ああ、ちょうどこれらのため。まさに>>。 >>は、だから私はここから始めましょう。グッド。>> だから今我々は再び少し左に行ってきました。それは、3です。しかし興味深い持ち帰りこれで1が気にする必要はないものですか？これらの2。これら>> 2。だから今はこの1が離れて行くことができ、この1つは離れて行くことができます。さて8だった問題は、今サイズ4であったサイズ2です。我々は、かなり近づいた。繰り返しますが、これら2つの要素の中央に移動します。オーケー。今、我々は常に我々は丸めダウンしているので、残って行っていることは残念なものだそれはそう。今我々はわずか7で私たちを残して、それ以外はすべてこれを投げるので、しかし、それは大丈夫です。拍手を与えてみましょう。我々は再び7を発見した。 [拍手]オーケー。かしこまりました。ただ、他に1秒間にしがみつく。その次のプロセスの種類のは、我々はそれがそう感じたよりも少し時間がかかったにもかかわらず、率直に言って、あなたの最初の本能は、最高の右でしたか？私たちは7瞬時に発見した。しかし、我々は、より速く、この1対関係なく、この例では、何を、7を発見しなかっただろう数字がすべてソートされている場合があるため、多くの電話帳のページのように、あなたは確かに何度も何度も問題の半分をみじん切りにすることができます。とそれだけで8桁の数字でこれを見て非常に簡単ではありませんあなたが本当に視覚的にそれを参照してください1,000ページの電話帳とは対照的に、しかしこのケースではここでショーンは7を探していたときに、どのように多くの最悪の場合のステップ、それは彼を取ったでしょう？ >> [生徒] 7。最悪の場合には7。まあ、最悪のケースではない7 8扉ここにありましょう。それは彼に8つのステップを取ったでしょう。だからそこのnドアなら、それは数年前にnステップのショーンをとっているかもしれません。さて、あなたのケースでは、これらの番号がソートされているアレックス、与えられた - 我々は、我々はこの物語の中で、これまでしてきたところから推測する一種のこの缶 - アレックスのよりインテリジェントなアルゴリズムの実行時間は何ですか途中から開始し、その後の繰り返し？ [生徒] 3。 >>だから、それはあなたが2〜1から8から4に行けば、大体、3になるだろう。 3ステップSOまたは、より一般的には、それがログn再びです。あなたは半減と半減と半減と半減しているいつでも、それはログnのこのアイディアの表現だ。そしてそうそれはあなただけの3つの手順を取ったでしょうし、実際にそうしましたかつて我々は、ドア半減と半減を開設これに対し、ショーンにいくつかの7または8の措置を講じていただろう。だから今年は私達と一緒にいることに感謝します。 >>ありがとうございます。お会いできてよかったですアレックスに感謝します。同様に。>> [拍手] 次にこれの本当の意味合いは？今では、率直に言って、私たちのすべてが何かを見つけることができる、8戸、ではないことを想像する紙の部分を引き裂き、私たちの本能と一緒に行くでわずか8ドアの後ろにはかなり迅速。しかし、それは万人ドアものなら？それは40億の扉の場合はどうなりますか？ 40億ドアの場合には、あなたは本当に、アレックスのアルゴリズムと一緒に行きたいとしている我々は、より一般的には、それを呼び出して起動したり、分割統治説明するようにバイナリ検索、あなたは問題を半減と半減続ける場合には、あなたは40億ドアを持っている場合は、何回半分に40億切り刻むことができるので？ [学生] 32。 >>これは、実際には32です。あなたは一枚の紙、あるいは、あなたの頭の中でこれを回避できます。あなたは250万ドル、ドット、ドット、ドットに、5億に1000000000から2000000000 to 40億行く。あなたが数学を行う場合、あなたは確かに32を取得するつもりだ、我々は通常、2の累乗で数えるので、それは実際にコンピュータサイエンスに関する。 32から2は40億であることを起こる。だから、コンピュータサイエンスの2のべき乗のこれらの種類への関連性が多数あります。しかし、どのような約80億？ 80億ドアがある場合はどのように多くの手順を実行することは取るつもりですか？ [学生] 33。 33だから。>> 160億ドアがある場合はどうなりますか？どのように多くの手順を実行することは取るつもりですか？ [学生] 34。 >> 34。我々は一種のこのうんざりを続けることができた。しかし、それは強力なものだ。あなたは、あなたの問題に複数の入力の数十億ドルを導入しないけど、大したことができますあなたはそれの1つの追加の一口を取るので、私達に二分探索のような何かを与えるまたはより一般的には、分割統治。しかし、私はここにカンニングのようなものだよね？アレックスのアルゴリズムの場合には、彼女がショーンに対して優位性を持っていた。彼女は、これらの番号がソートされたことを知っていたが、アレックスは彼ら自身をソートする必要はありませんでした。私は事前に確認しました黒板と種類のところに来私はソートされた順序でそれらすべてを引き出したことを確認してから、私は紙でそれらをカバーしました。しかし、それは私にどれだけの作業がかかりましたか？我々はいくつかの一見ランダムな順序でこれらの番号で始まっていた場合 - この場合、これらの単純な数字、ここでは1〜8 - 私たちは、これらの値をソートする方法を教えてください。このタスクを与えられた人間だったら、直感的なアプローチの種類はかかるだろう数字の全体の束を選別する？これらのものは、パズルのピースのようにレイアウトされた。うん。私はそれぞれの番号を取得し、それぞれにそれを比較します[学生] そして左に行き続ける。 >>さて、良い。だから、その横に1と比較し、それぞれの番号札を取るその後、ちょうどあなたが行くように物事をrejiggeringの一種で、リストに沿って動かし続ける。そこでここでは、関与するためにはより多くの多分少数の人々のための機会を持っています。我々が出てくるのが大好きだ8より多くのボランティアを持っていますか？あなただけではないでしょうから少し圧力。 1、2、3、4、5、6、7、8。ダウンさあ。君たちは8までの数1になるだろうしている。我々は、私が事前にそれをやったのと同じ方法でずっとアレックスでは、このソートを行うことができないかどうかを確認してみましょう。 1、2、3、4。先に行くとあなたが希望の場合は、ここに譜面台と私の間にステージ上でラインアップ画面上のスライドと同じ順序でおっと。我々は、次の例にあなたを操作します。ああ、待って、待って。ここに私達は行く。待ってください。次の例は今です。ほらナンバー8。アップで来る。かしこまりました。並べ替えは、これに応じてがた。音楽ここに立つの側に少しだけスライドさせます。だから我々は、4、2、6を持っている - そこは、ここを介して、そこに取得 - 3。うん。オーケー。あなたはこっちに行く。いいえ、あなたはそこにとどまる。ええ、すぐそこ。いいえ、私は間違っている。すぐそこ。さて、非常に良い。オーケー。だから今度は昇順にソートしてみましょう。どのように私はこれをやって行くことができますか？少し前に提案されたアルゴリズムは、なぜ我々だけで比較していないでしたその後、隣同士に種類のものであり、人々は、どんなミスを修正左から右へ移動する。そこでここでは明らかに、順不同の4と2を持っています。のはあなたを交換しましょう。オーケー。だから今私は行を下に移動するつもりです。 4と6、いや。 [笑い] 6と8、かなり良い。 8と1は、私が君たちを入れ替えることができます。かしこまりました。 8と3のように、君たちを入れ替える。 8と7は、私は君たちを入れ替えることができます。優れた5と8。私はあなたにソートされたリストを与える。かしこまりました。そうではありません非常に。しかし、それは良いですので、大きな数字 - ケース8点で - 左の上から右にバブルアップの種類を持っている。だから私は、右のそれらの1を得たが、それはかなりの問題を解決しなかった、このように感じている。だから、あなたは私たちが次に何をするかを提案するだろうか？ >> [生徒]それをやり続ける。 >>我々はそれをやり続ける。そして再び、実現する、私達はちょうどすべての人間を持っていることによって物事を設定インテリジェントにその絵に自身がベースのアレンジの並べ替え、しかし今、我々ははるかに整然としなければならない。我々は、我々がコードを書いているかのようにそれについてのアルゴリズミックでなければならない - この場合は口頭での擬似コード。だから私はちょうどそれをもう一度試してみましょう。これはかなりうまくいった。それは、それを解決していない。しかし、それは疑うとき、ちょうど試してみて、もう一度試してください。だから、2と4はもう助けにはならなかった。 4と6。ああ！少し良くなった6、1、。良い6および3。 6と7,7と5,7と8、良い。彼はリストの末尾だから、あなたが知っている、私はおそらく今8を無視することができます。多分、我々は、誰かが彼を過ぎて行く心配する必要はありません。しかし、それは安全な仮定の場合、見てみましょう。今すぐリストです - いまいましい - ソートされません。のは、再びこれを試してみましょう。 2と4,4と1,4と3はそう。 4と6、良い。 6,5、良い。図6、図7、図8、良い。しかし、通知は、私はちょうど今ここに停止して、今ここに止めることができますか？ [学生]はい。 >>うん？あなたの一つはあそこにずっと9番だった場合はどうなりますか？これは、ソートされていただろう。グッド。>>それは最初の頃にソートされていました。グッド。それでは、もう一度戻ってみましょう。私たちはほとんどがしています。 1と2、2と3,3と4,4と5,5と6,6と7,7と8。、私は今やっていますが、やはり、私は私が何を聞いて何をすることができるコンピュータだと私の唯一の思い出は、今私は実際にちょうど仕事のビットをしたということです。何かがここに変更しました。だから私は、技術的に視覚的に、またはアルゴリズム的にこのリストは確かにソートされていることを確認していない。だからちょうど良い測定のために、ちょうどこのことについて肛門であることが、この1のより多くの時間を行いましょう。 1と2、2、3、3と4だから。そして、あなたは何を知っていますか？ちょうどよい測定のために、私は私の手で、この時間を追跡するつもりだ私はちょうどので、私は実際にどのくらいの行ったこと知っているどのように多くのスワップを行う。 3と4、4と5,5と6,6と7,7と8。いいえスワップません。だから今は、合法的に再びこれを行うための馬鹿だろうなぜなら、私は人間のこの峠を通って仕事もしなかった場合、その後、明らかにそれらのどれもランダムのソートされていない場合、再び起こるだろうこと adversarially自らを動き回る。だから今は、停止することができます。それでは、質問をしましょう、これは実際に私にどれだけの作業がかかりましたか？それはどのように多くのステップを取るのですか？ >> Nの2乗。ええので、n乗。あなたはどこから入手するnの二乗のですか？あなたは、各numをチェックする必要があります - そこnは数字があり、あなたは他のn個の数値で各番号を確認する必要がある。グッド。 >>だからそれはNの二乗。グッド。>> それは非常によく、右乗nのかもしれないようなので、それは感じている？ 8は、この場合には具体的には、これらの人のそこにNさん、私は2番目のに対して最初の人を比較した私は、このリストを通過したが、毎回、第三に対して二つ目は何度も何度も、そして私が最後に着いたとき、私は何をしましたか？私はそれをやり直し。我々はこのような説明を一般化した場合そこで、我々は人々をnしていると私は、このアルゴリズムを通過するたびに、8つのステップ、nステップ、明らかに作ってるんだ。しかし、どのように何度も最悪のケースでは私は、人々のこのリストを通過しなければならないのですか？ [学生] N回。おそらく>> nは、右なぜなら、最悪の場合には、おそらく、最初からこれらの人の最悪の場合の取り決めは何ですか？彼らは完全に順序を逆にしている場合ので、ちょうど精神的に仮定し、let's - あなたの名前は何ですか？ >>ボーエン。ボーエン。オーケー。だからボーエンは、ちょっとこっちに来て。、ボーエンは、アルゴリズムの最初からここにあったと仮定しそして、私たちはこのアルゴリズムによると、ここで誰もが何かを知っているが、ボーエンはありません - そしてあなただけの私と一緒に散歩したい場合は - 彼は最初の頃に行ったように、バブルまでに起こっている、最後までずっと。しかし、ボーエンの隣の人は7番だったと仮定します。私は戻って、私はここに戻ってすべての道を行かなければならないことを意味番号7を、取得する必要があります。今私は7番である人と同じ散歩を持っている必要があります。しかし、番号6は同様に彼の隣にあったその後はどうでしょうか。それから私は戻って、6を取得する必要があります。だからもう一度、このループを繰り返すたびに私は、n人のそれぞれに話していると私は私が引っ張っていることを確認するために、これらのn散歩をしなければならないかもしれませんリストの一番最後に戻って、戻って、戻って最大のすべての要素。ので、n物事n回ちょうどn回nまたはn乗です。だからここですでに私たちはもはや、もはやログnんnは、んなアルゴリズムを持っているそれは我々が前にやった何よりも実際に悪いです。だからアレックスの種類のは、私が彼女のために明らかにフロントまで、すべての作業をしたという点で幸運彼女はこのバイナリ検索アルゴリズムで楽しむことができるように、高価なすべての作業、これは、nのログです。しかし、これは月曜日のテーマと一致している。私たちは、実行時間をスピードアップするために、我々はより多くのビットを使用し、少しより多くのスペースを与えた。そんなに時間と空間の間のこのトレードオフがあるように、また、単に移動する準備ができて物事を得るためのフロントの並べ替えをそこに費やした時間の間のトレードオフかもしれないそして実際に検索などのアルゴリズムを実行する。別のものを試してみましょう。君たちはただ速くがたは再び一致するように再配置する気にしないだろう場合は、それは非常に簡単ではないどこにわずかに異なる何かをしようとしてみましょうとして単にスーパー直感的ですすべてのペアワイズ誤りを修正してください。代わりにもう少し意図的であるとこれを実行してみましょう。あまりにも私が提案すると、この1つはおそらくかなり直感的です。何度も何度もリストから最小の人を選択してみましょう。だからここに私達は行く。 4、あなたは、私がこれまで見てきた最も小さい人ですので、私は精神的にちょうど今のあなたで指すことによってそれを覚えているつもりです。 2。ああ！番号4のことを忘れる。私はちょうどこのリストに新しい最小の要素を発見した。私はこの種のことを覚えておくつもりです。 6,8。ああ！ 1。さようなら。だから今は、数字の1を覚えてするつもりです。我々は1が最小であることを知っているが、私はコンピュータです。 0は何があったのなら？ -1は何があったのなら？私は続ける必要があります。だから3、7、5、いや。オーケー。だから、番号1が最小であった。私は、リストからユーザーを選択してみましょう - we'llはこの道を行く - そしてリストの先頭に任意にあなたを置く。今、ちょっと待って。だまされたのだと考えます。これらの人はいない8人のリストではなく配列を表す場合連続したメモリ領域のうちの8つのチャンク - あなたがちょっと後退を気にしますか？右ここにあなたのためにスペースは実際にありません。では、どのようにするためのスペースを作るのですか - あなたの名前は何ですか？ >>サミー。 >>サミー。どのように我々はサミーのためのスペースを作るのですか？私たちは、私の前には、nを移動します。オーケー。>> だから我々は、彼の前には、n人を動かすことができる君たちが左に1意図的、劇的な一歩を踏み出すことをお望みであれば。、彼らはすべてのユニゾンであることをしましたが、最後の時間私はいくつかのコードを書いたあなたはすべてを一度に多くのものを移動するのソートすることはできません。我々は時間に一度皆を移動、ループ内でそれを行うことができます。君たちは、右に後退気にしないだろうそうだとすれば、サミー、あなたのための余地はまだありませんので、バックステップができれば、今これを行うにしてみましょう。どこサミーは少し前だったのですか？すぐそこ。だから、そこにギャップがあるのです。だからあなたは、サミーのスポットに移動することができます。今すぐ次の人まで、今すぐに次の人、次の人。今、私たちはサミーのための部屋を持っています。観客からさて、誰かが - 良かった、正しかった、それは少し時間がかかると感じた - 速いのは？うん。 [学生]新しい配列？ >>あれは、何ですか。 >> [生徒]新しい配列？ >>さて、良い。ちょうどトレードオフのこのテーマにしたので、一貫した、なぜ私はちょうど新しい配列を作成しないその後サミーは、例えば、これらの人々の前のスペースで泳いされます私達はちょうど完全に新しい配列を充填を開始することができます。それはあまりにも働くだろう。しかし、私は今日、より多くのスペースを費やすことに興味はない。別のアプローチは何ですか？ [学生]スワップ。オーケー。>>我々は、ちょうどこれらの2人を入れ替えることができます。あなたの名前は？マリオ。 >>マリオ。マリオだから、あなたは現在ここにいた。サミーは、あなただけの一瞬をバックアップすることができますか？マリオはここにあった。我々は、あなたがサミーがどこに行く気にしないだろうそうだとすれば、もうあなたのための部屋を持っていない我々はここでサミーを置くことにしましょう、そして今、私はサミーのスワッピング操作がはるかに速かったと主張していると思います。我々は、これらの人を交換する、または多分2これらの人を交換する1操作をしたしかし、我々は良い感じているので、1、2、3、4をしませんでした。今、ちょっと待って。番号4は先頭に近いのようなものだったので、私は何かの問題を悪化させた。今、数字の4はこの目的のために少し近いですが、私は実際に知っているか、そのことについて気にしませんでした。だから、これは数字の4は、少し遠くにその運命づけられた場所からのものであることをただ単に運が悪いだけです。だから今は、このアルゴリズムを繰り返してみましょう。限り、その話があったように、要約すると、すべての我々は、リストの中を歩くんでした番号の小さい人を探しています。だから今、もう一度やってみましょう。我々はもはやサミー心配する必要はありません。私達はちょうどここに行くことができます。ああ！番号2。これはかなり少数です。 6、8、4、3、7、5。さて、良い。そして、ありがたいことに、偶然、私が移動する必要はありません - >>ウィリー。ウィリー彼は今、彼の右の場所でだからです。再びこれを行うと、これらの2人の男を無視してみましょう。 6。これはかなり少数です。ああ！ 8は間違いなく大きくなっています。 4。の4に焦点を当ててみましょう。ああ！ 3はさらに良いです。 7と5。だから我々は今、何をすればよいでしょうか - >>ロジャーは。 >>ロジャー？のは数字6で彼を交換しましょう。だから6と3が交換したい場合は、我々は今、一種のその6でラッキー得ている彼女は、あるべき場所に近い、それはここに単なる偶然だ。だから今ここに行きましょう。 8はかなり少数です。ああ！ 4は小さくなります。 6、7、5。我々は今何をしますか？ >>スワップ。まさに>>。だから今より速いのこの種のことを行うてみましょう。 8、6、7、5。 5はどこへ行くのでしょうか？グッド。オーケー。 6、7、8。 6は彼女がどこに滞在するために取得します。あなたの名前は？ >>ロザリー。ロザリーは、彼女がどこに滞在するために取得します。見てみましょう - 7のために取得します。 7,8。オーケー。だから7は、彼女がどこに滞在するために取得します。あなたの名前は？ >> Amna。 >> Amna。だからAmnaは彼女がどこに滞在するために取得し、彼が今どこにあるべきか8番が既にインストールされていますさて、良い。我々だけでも、ここで自分自身のための仕事を作成しているように感じている。最終的にはこのアルゴリズムの実行時間は何ですか？我々はしない8としてではなく、nとして、これらの人々のことを考えるか？ >>それはnです。それはnステップだが、我々は一つ一つの時間をチェックしています。オーケー。 Nしかし、あなたはすべての単一の時間をチェックしている？それはステップをNの場合さて、しかし、私はちょうど1、2、3、4を行くことによって、あなたをソートすることはできなかったでしょうか？ああ！さて、それは大きな違いだ。だから、nが乗なぜですか？本当に何が起こっているの？そこにこのリストのn人ですが、リストの中で最小の人を見つけるために最悪の場合には、どのように多くの手順は私が取らなければならないのですか？ N. >> N、右、最悪の場合には、番号1は、あそこにすべての方法であるため、それで私は彼を取得したり、彼女の行かなければならない。そして私はついに1が最小であったがわかると、それはそれらを交換するのはかなり速いです。しかし、今私は初めからスタートして、誰のために見なければならない？ 2である次に小さい人。最悪の場合には2はどこですか？ああ、私の神。それは年末にこちらにすべての方法です。だから今私はちょうど別のnステップ、別のnステップをやった。そして、我々は、n個の人々を持っていると、最悪の場合には最小の人が離れてnステップである場合、それは再びn回nのだ、と私たちは再び持つn乗。これはとても良い感じていない。そして、実際には、最高の状態でも - 彼らはソートされ始めたとします - それは私がこれらのn人を並べ替えるには、このアルゴリズムを使用するためにどのように多くの手順がかかりますか？ Nは二乗。 >>私が聞いたNの2乗。 nは乗はなぜですか？あなたはまだ一つ一つの時間を確認しなければならないからです。 >>うん。そして、あなたはそれらを交換する必要があります。私たち人間は全知の一種であるにもかかわらず>> 私達はちょうど種類のこのがソートされていることを見ることができる視覚的な意味で、コンピュータは、スマートではありません。それは、こことこことここを見てになるだろうしかし、それが何を探していると、最小の要素である場合、あなたは、あなたがどの時点で最小の要素を見つけたことを知っていますか？一度は終わりにしている。しかしその時点では、現在最小の要素を見つけることができました。あなたは、必ずしも世界の状態について何も知りません。だから、何度も何度も行かなければならない。私がチェックしているので、私は本当にばかを見ないように、今回は大丈夫、2、あなたが最小だ、しかし、私はまだ合計でそれを知らない。 3、4、5、6、7、8。さて、良い。 2は確かに小さかった。今度は、次の最小を見つけることができます。オーケー。 3、あなたは現在、最小だ。見てみましょう。 4、5、6、7、8。さて、再び幸運。 3は正しい場所に確かにあった。しかし、私は何度も何度もこれをやり続けるつもりです。どのように我々はほんの少し良く行うことができますか？代わりにアップペアワイズ最小から最大に人バブルを持っていることのその代わりに、次に最小の人を選択してリストを行き来しての、なぜ我々は代わりにステップによって、新しいリストのステップにこれらの人々を挿入しませんか？これを試してみましょう。今私はこの事の挿入ソートを呼ぶことにしましょう。そこでここでは、ここにある。ナンバー1。私はこのリスト内の誰を気にしないでください。私の目標は、今すぐにソートされたリストの先頭に数字の1を置くことです。そして私は私が唯一のメモリのうちの8つのチャンクを持っているので、提案するつもりだ、任意に、今私は、私のおそらくソートされていないリストの間の壁ですと私は主張するつもりだ私の後ろにいる誰もがソートされます。だから今我々は数字の1を持っています。、私は、ソートされたリストに彼を挿入したいので、私はちょうどここに上で、私の壁を移動するつもりですそして今、私はこのリストがソートされている主張は、このリストはソートされていないです - 少なくとも今のところ私が知っている。私は一度にすべての数字を見ることができません。今、私はナンバー2が発生しても。私は彼と一緒に何をしますか？私は、ソートされたリストの中に今、あなたを挿入します。しかし、それがいかに簡単にわかります。私はただ見ている。番号1があります。ああ、明らかに2が1番の側に行く。今私は3で何をすればいいですか？私は、ソートされたリストにあなたを挿入します。しかし、それは超簡単でした。これは超簡単です、これは超簡単ですが、これは超簡単、超簡単、超簡単です。そして今、すべては私の後ろにソートされ、それがどのように多くのステップを取るのですか？ [学生] N. >>だからそれはnです。我々は幸運。それだけであったn個の理由は？ >> [生徒]リストがソートされていましたので。リストがすでにソートされています。だから我々はラッキーだった。しかし、我々は、運のようなものを生かした今回のアルゴリズムを設計不必要な時間を無駄にしないことにより、その最良のシナリオ。だから我々は、今、私たちは、バブルソートを呼んでいるものがあるどこペアワイズまでバブルの人々は親切。我々は今我々が何度も何度も最小の人を引き抜く選択ソートを持っています。そして今、我々はそれが属する場所に我々はある種の積極的に人々を置く挿入ソートを持っているますますソートされたリストインチ我々は可能性がある場合、ここでこれらの人のために拍手。 [拍手] のは、ここで我々の5分間の休憩を取りましょう。そして、我々が戻ってくるとき、私たちは水のうち、これらのアルゴリズムのすべてを爆破する良いものを持つ。かしこまりました。どうも有難う。あなたは、お土産としてそれらを保つことができます。かしこまりました。我々は戻ってきた。と実際の高速を要約するために、我々は、ソートにこれらの3つの異なるアプローチを持っていたの全体のポイントは、ポイントを取得することでしたどこにアレックスのような人ショーンができたような人よりも早く番号のリストを検索することができます。そして、我々は8つの数字でそのような単純な例を持っているにもかかわらず、あなたは8 Webページ、80億Webページに簡単に外挿することができる Facebook上または8億友人。だから、これらのアルゴリズムは、確かに、価値観のこれらの種類に拡張することができますやアイデアは、最終的には同じです。バブルソートは、我々の種類が最大の人をバブルアップここで、最初だったので、ペアワイズの人を交換することによって右へのすべての方法。その後、我々はここで私は、もう少し慎重に我々は選択ソートと呼んでいるものであった、、リストを調べ、何度も何度も最小の番号を選択して、再度保たの論理的な結果は、リストが最終的にソートされていることです。その後、3分の1に、私は、彼らの適切な場所に人々を挿入そして我々はリストが既にソートされたことで非常に不自然な例をしました、それは、挿入ソートのケースであるというメッセージを送信することであったあなたは幸運を得ることができます。番号がソートされていたとき、それだけで、できるだけ確認するようにnステップを取ることになるだろう選択ソートのに対し、あなたはもう少し視野狭窄しているそしてあなたは今までにリストはすでにソートされていることに気づいていません。だからここにアクションでバブルソートを見てみましょう。次の例では、垂直バーを参照しようとしているその高さは我々が起こるをソートする視覚化の並べ替えができるように番号を表しています。小さなバーは、小さい番号;大きなバー、大きい数字。そして、我々は、このデフォルトの速度でそれを再生します。それは今のところ少し速く移動するために起こっているが、赤は2つのバーを示しているものです横に並べて比較している。あなたが密接に見ればと、何が起こるかは、バーは順序が一致していない場合ということです小さい方は、左、右に大きい方に移動されるそして、あなたは前進続ける。我々は何度も何度もこれをすればそれで、最小バーことに気づく左への道をインチング維持しようとしているそして最大のバーが右への道をインチング維持しようとしている。そして実際、我々は右側にはるばるパターンが見え始めている同じように我々は最終的に私達の人間のリストの遠端に湧き上がって8、次に7を見ました。だから、これは非常に迅速に少し面倒なので、私はしばらくの間これを停止させるつもりされています。私は非常に高速になるように速度を変更してみましょう。私はアルゴリズムを変えていないよ、私はただ、アニメーションがより速く起こる作ってるんだ。まだバブルソート、同じアルゴリズム、しかし今、あなたは私たちの言葉によるデモよりもはるかに速い見ることができますする最大の要素は確かに一番上に湧き上がっています。余談ですが、これらのほとんどの左下の四角と右下のようにあなたがやっているどのように多くの比較ににちょっとリマインダです。しかし、今のところ、我々は、形状を取っているピラミッドに集中することができ、そこに行く。最小の要素は、左右上で最大、との間ではその正反対です。今ではなく、選択ソートを見てみましょう。私は先に行くとストップをヒットするつもりです。私たちはバーの新しいランダムなセットを取得するつもりだ。選択ソート、リコールは、何度も何度もリストを通過最小の要素を摘採。だからここに選択ソートです。私たちはペアを比較していないので、それは今起こっているそこの少ない仕事のように見えるしかし、我々は桜を右から左への最小要素をピッキングするだけでソートしている。それは非常に少し時間がかかったので、二分法はすでにある。アルゴリズムはバブルソートのように、Nの2乗の時間がかかると言われていたからといってと選択ソートと同様に、それらは、最悪の場合の実行時間は本当にあります。例えば、の場合には、、、と言うの選択ソートしてみましょう私は実際には最小の人を選択していますし、ここに彼または彼女を置くその後、私は再びそれをやっているし、私は再びそれをやっている、私が作ることができる若干の最適化がありました。その場合にはサミー - 私はここに番号1を移動するとすぐに - 私はその後彼と一緒に何をするかが必要でしたか？ >> [生徒]彼のままにしておきます。右、彼を残しましょう！何もない。ので、私は最小の要素を選択した場合、私は二度とサミーに話をする必要はありませんでしたそしてここで彼を入れ、なぜ時間を無駄には私の全体のリストの最後に行くの？次の繰り返しで私は実際にのみ番号3に、番号2にのみ移動することができます。だから、現実には、私はn個のものをn回やっていなかった。 1物事には、n - 2 - 物事には、n - 3つの事、私はその後、n個、nをやっていたその後、n - 4、ドット、ドット、ドット。私達はちょうど意味等比級数のビットを持っているあなたは徐々に小さく数字を追加しています。ないN + N + N + Nが、N + 7 + 6 + 5 + 4 + 3 + 2 + 1です。一般的になるように動作していることと何が - 私はちょっとここで私のボードを台無しに行くよ - / 2 - それはN（N-1）のようなものになるように動作するように起こっているあなたはすべてのチートシートを持っている数学の本の裏を見たならば、我々はちょうど一種式について。あなただけの何かを追加する場合は、nは+ N - 1 + N - 2、それは、このようなものになるように動作します。私達はちょうど種類の乗算これをした場合と、それはマイナスn / 2のn乗。でも、私は言ってNの2乗保たれ、私は精神的なショートカットを取ることのようなものだっただからです現実には、n個のマイナス乗nは2で割った値は、実際のステップの真の数であるため、私たちが本当にカウントアップの場合、選択ソートのようなアルゴリズムがかかるだろうそれらすべての比較と我々がやっていた少し忙しい仕事のすべて。しかし、率直に言って、一度nは一体何が気に百万円、みたいになり得るあなたは2で割っ億乗マイナス億をやっている場合はどうなりますか？乗億は膨大な数である。あなたとそれのさらに10億オフを取ることができます - nを。そんな大したことではありません。だから数値が大きければ得るほど、重要なこれらの低命じた用語である。あなたがステップ数のquadrillionsの話をしている場合は、2で割る場合に誰が気に？だから一般的に、コンピュータ科学者は、すべてのものが、最大の用語を捨てる傾向にある私達はちょうど一種の世界を単純化し、そのアルゴリズムと言うほぼNの2乗の手順を取った。つまり、アルゴリズムの実行時間です。だから我々は、いくつかの具体的な例と一瞬でこれに戻ってくるしかし今のところ、それはちょうど私たちの世界を単純化するの背後にある直感的な動機のようなものだとなく、これらすべてのファンシー数式に取得するよりも最も重要な用語について話している。だからそれは選択ソートであり、我々はそこに少しの幸運。挿入ソートを見てみましょう。私が先に行くと同様にこのいずれかを始めましょう。今起こっているパターンに気づくことは、少し異なっていますそして我々は、ランダムな数字で開始しかし、我々は実際には、最悪の場合にはステップ数をカウントアップする場合リストには、正しい順序で完全に起動した場合、我々は唯一の限りを実現するためにnステップを取るだろう。しかし、リストは後方現実のものとなった場合 - 例えば、この場合はここで - その後、我々はこのケースで実際に多くの作業を行う必要が気づく。この1が難しく作業の一種であるように、それは一種のあなたに感じるはず左側にそれらの小さい要素を取得し、我々は不運だだからですます。リストは、逆に誤ってソートされました。挿入ソートとは、対照的に、我々はここで我々の人間でやったことを模倣した場合起動しソートされ、みんなと一緒に起動することによって、それは右、かなり良いアルゴリズムですか？これは、すでに、実際には、ソートだ。だから、これらの事は私達を取っている正確にどのくらいの時間を要約してみましょう実際にははるかに簡単だ専門用語や表記のほんの少しを導入することにより、を示唆しているのfanciness·ソートより。ここでこの事は、画面上のこのビッグOは、コンピュータ科学者は、一般的に使用されるものですアルゴリズムの実行時間は最悪の場合を説明する。繰り返しになりますが、最悪のケースで、それは完全に文脈依存です。我々は最悪のケースではどのような意味は全く我々が話をしている問題に応じて異なります。しかし、ソートの場合、最悪のシナリオは何ですか？私たちのために多くの作業を意味しているように、それだけで感じているので、すべてが逆向きになる。私は、私たちがこれまで見てきたアルゴリズムのいくつかを書き留めている：線形検索、電話帳や紙の破片を持つような二分探索、その後、バブルソート、選択ソート、挿入ソートのように我々は、我々人間と見た最終的にマージソートと呼ばれるように起こっていること、その後他1。 7番を見つけるために、最悪の場合には線形探索では、どのように多くの手順がかかりますかショーンのような顔をしたn個の扉がある場合はどうなりますか？ >> [生徒] N. Nである従って私達はnの大きなOを記述するつもりです。私はいくつかの空白を埋めるつもりです。これはただの空白のグリッドです。しかし、線形探索で最良の場合には、図7に示すように、リストの一番先頭にあったかもしれないとショーンは、リストの先頭に探し始めている可能性があります。あなたは、線形探索を使用していて、ちょうど左から右にも左にも右にチェックしているかもしれないので、もし - 彼らは同等だ - 最良のケースでどのように多くのステップかもしれない線形探索、ショーンのアルゴリズムのように、取る？わずか1ステップ。だから私は、オメガ表記だと言うつもりです。これはただの首都オメガです。オメガは、最良の場合の実行時間を言うだけセクシーな方法です。だから最良のケースで実行されている時間は、シングルステップまたは一定数のステップは - この場合は1が - しかし、最悪の場合には、大きなO、それは実際にnステップです。そしてここでこの1、シータ、私たちは実際に今見てするつもりはない。それは、この特定の例に関連していません。しかし、今のは、バイナリ検索を試してみましょう。バイナリ検索に最悪のケースでは、どのように多くの手順は、7番を見つけるために連れて行くまたは我々が探しているものは何でも？ >> [生徒]ログn。同じように、アレックスが不運になったので、まだnログを取るつもり私たちは本当に念入りに問題を通じて勤務したときそして、彼女は、彼女が見て、非常に最後の扉まで、7番を見つけられませんでしたもかかわらず、公平に見て、彼女は、道に沿って一定の扉を捨てるようになった最悪の場合にはバイナリサーチはログnの実行時間を持っています。そして再び、それはこの分割と征服に語っています。しかし、どのような最良のケースではどうですか？彼女がステージに上がってきたとき、アレックスは実際に右のその最高の症例を経験した。ことは、バイナリ検索でどのように多くのステップを取るのですか？ >> [生徒] 1。 1、ちょうど彼女は幸運だ。オメガがベストケースのシナリオを参照しているので、しかし、それは大丈夫です、それだけでランダムなまぐれだとしても最良の場合入力、。さて、これはあまりにも私たちは、今のところ空白のままにしておくだけの種類に行くんだ。バブルソート今はどう？バブルソートの最悪のケースでは、誰もが、逆の順序であるので、我々は、バブルの多くを行う必要があります。しかし、どのように多くの手順は、最悪の場合に取るしようとしていること？ >> [生徒] Nの2乗。あなたが考えてみればこれは、、、Nの2乗であったリストは完全に下位である場合 - 8はこっちです、1はこっちです - 事はバブルに開始すると、数字の8は、この方法で、この方法で、移動しようとしているこのように、この方法が、ここでは、最悪の場合には7番ですか？ここで彼女はあそこにまだある。だから我々は何度も何度もそれをしなければならない。 1のステップと、n - 2 - 手順私たちはその後、nステップ、nはどこで取得すると、それはです。そして、あなたはそれのための私の言葉を服用している場合 - あなたは一種のそれを掛けることがあれば、それは我々がちょうど今のところ無視するだろうといくつかの他の用語と最後にはほぼNの2乗だ - ワーストケースのバブルソートではnの二乗、与えるか、または取る。しかし、バブルソートで最高のケースについてはどうですか？最良のシナリオは何ですか？数字のすべてがすでにソートされています。そして、私が使用されるヒューリスティック、私が使用したトリックは、何だったの私は仕事をしていなかったため、早期に停止することを実現するためには？ [学生]を一度に確認してください。 >>一度それを確認してください。しかし、私は道に沿って何をやったのですか？私は私が作ったどのように多くのスワップを追跡しました。そして私は私が私の指上の任意のスワップをカウントしていない場合、私は全く仕事をやった気づいた。私は確かに再び全く仕事をしないことを試みるべきではありませんので、私はちょうど停止することができます。だからリストが既にソートされてバブルソートの最良のケースで、あなたは最高のケースは、実行時間、オメガ表記が何であるかを言うでしょうか？それはちょうどn個です。我々は、いくつかの作業を行う必要があるが、我々は唯一の仕事の1分の散歩をしなければならない。そしてここにも私はこの部分を空白のままにするつもりです。そして今、選択ソート。選択ソートは、私は何度も何度も、最小の人を摘採していた。そして、我々はそれがあった場合の実行時間は何を言ったの？それがあったN最悪の場合に乗。そして残念なことに、最良のケースでは、それはまた、Nの二乗私は全世界の全知のビューのようなものを持っていないので; 私は確かに最小の人を発見した際に完全な反復だけを知っている。だからの選択ソートの一種で、その意味で吸うしかし利点は、直感的なのそれの一種である。あなたがしなければならないすべては、ネストされたforループのカップルを書いてあるので、それは、アップコーディングするのはとても簡単です一般的に、それが最小の要素を探して通過するそして、それはリストの末尾に属する最小の要素を配置します。だからここにあまりにもトレードオフがあるように起こっている。それはあなたが考えることと、実際にコードを書くことで何かを開発するのに要する時間あなたがより良いアルゴリズムと高速なパフォーマンスをしたい場合は非常によく、より多くの時間がかかることがあります。しかし、最大迅速かつ汚いコード何かのあなたが本当にちょうど一種場合とだけの種類の、あなたが考えることができる足らない可能アイデアを取り、コードにあなたに数分かかることがありますでなく、大規模なデータセットを持つあなたのアルゴリズムでは、実行するために時間がかかる場合があります。とさえ私は大学院では、時々、これらのトレードオフになるだろう。それが午前3時になる、私はいくつかの非常に大規模なデータセットを分析しようとしていた私がやっていたセキュリティの研究に関連し、それはどちらの5分を費やした調整データを分析し、スリープ状態に入るために私のプログラムそれは瞬時に実行され、スリープしないように、またはちょうどそれを取得して8時間を費やしています。それで、そこにも、それは意識的な決断のようなものだ。少ない開発時間、より多くの睡眠。今にして思えば、私はおそらくことを奨励するべきではありませんここでの目標は、コードの品質を最適化することであるときに、しかし、それはあまりにも現実の世界では非常に合理的なトレードオフです。少ない時間、少ない性能またはその逆。そこでここでは、最終的にシータについて話をする機会を得る。シータ記法は、コンピュータ科学者が会話で持ち出すことができるものですビッグOとオメガは、同じことが起こるとき。あなたは、シータは本当にこれがタイトバインドの一種であるというメッセージを送るように言っています。シナリオが良いか悪いかどうかに関係なく、それは乗該当なしだ。だからそれはちょうどここにこれらの物語の関連はありません。挿入ソートは、我々が見た最後のものであるここで私はちょうどいい場所に皆を挿入しました。我々はそれをここに見たように、最良のケースでは何が挿入ソートの実行時間でしたか？ [学生]最良のケース？ >>最良のケース。最良のケースでは、誰もがソートされたので、それは、Nされましたとサミーと他の誰もが本当に全く動かなければならなかった。彼らは適切な場所に存在していた。最良のケースで非常に挿入ソートは、この場合には、nです。しかし、最悪の場合は乗nのようなものだ。なぜですか？人間の私のリストが逆順になっている場合は、私は最初の8番から始まると私は右ここにある右の位置、に彼を挿入したり、彼女の。側への移動の私は一種。これらの人がソートされていない、彼または彼女は、ソートされます。しかし、今私は次の人見つけることが起こる？ >> [生徒] 7。それは逆の順序でだから最悪の場合には7。そこでここでは7です。 7はどこに属しますか？間違いなく私の後ろに。しかし、今、7は実際には、すぐに私の後ろが、8番の後ろに属していないので、私はあなたがこのように移動してくださいすることができます、、失礼ですが "と、数字の8を言わなければならない "7のための部屋を作るには？"今私は6に遭遇。 "ああ、、8番と7番すみません、あなたは6のために場所を空けるために移動することができますか？" だから、他の言葉で、挿入ソートと、私はあまり運動していないよあっても、私の後ろの人々がより多くの仕事をしているし、誰かの時間を要するようになったということ。これは、コンピュータの時間をコストになるだろう。だから、挿入ソートの場合、我々はまだ苦しんでいます。あなたがステップの合計数を足し起動した場合、我々は、ほぼNの2乗当たってしまうこれらの人は、そのリストの中に挿入することが人間のためのスペースを確保する必要があるためです。ので、この場合にはシータはちょうど手元に特定のストーリーには適用されません。それはすべて素晴らしく、良いことだ。我々は、実行時間の話のこれらの3つの異なる方法があります。我々は実際にアルゴリズムをコーディングしようとした場合しかし、これは実際に本物の言葉で何を意味するのか？そこにさらに良いアルゴリズムがあることを私は提案してみましょうことは、それ自体がいくつかのトレードオフがあります。我々は、それがマージソートを呼び出すつもりだ、そしてそれはこの魔法のようなアルゴリズムのようなものだそれはただ速く何とか動作し、それは、少なくとも擬似コードで、表現することは簡単だ。このアルゴリズムはマージソートの実装は次のようになるだろう。健全性チェックがある第一 - 何でもn個の数値は、n人々、 - あなたは、n個の要素を与えられているとき。 nが2未満である場合、ソートはマージだけを停止します。それはいわば、返します。 nが2未満であれば、なぜあなたは止めるだろうか？ >> [聞こえない学生の応答] 右。そして再び、nは、リストの番号ではありませんが、n個のリストのサイズです。 nが2未満である場合、それは、あなたのリストのいずれか1であることを意味しますそれは1つの数字だかどうかは明らかにソートされている場所、ソートするには何もありません、その場合、または0、ので、我々は、ベースケースのこの種を必要としています。リストには何もすることだけでありませんように短ければ、文字通り何もしない。返す。それ以外の場合の要素の左半分を並べ、その後、要素の右半分を並べ替えるその後2ソートの半分をマージします。私はどのように要素をソートする方法を求めていることにより、この種のは少しチートのように思えるそして、あなたが私に言っている、 "右半分を並べ、左半分をソートします。" 私は、のようだ "すべての権利。どのようにして左半分を並べ替えるのですか？" "、左半分の左半分を並べ左半分の右半分をソートし、次に完了しました。" あなたは、それが周期的に並べ替えることが何を意味するかを定義するの一種だしかし、それは、このケースでは実際に華麗だと判明した。それは本当に終わりのないこの悪循環はありませんときにそれが終わらないので、？ >> [学生]は1の事に達する。あなたは1点ものに到達したとき。は、8人で始めるかもしれませんし、私が言うと、 "これらの人々の左半分を並べ替えるようにもかかわらず、これらの4人が、 "次に私が言う、"どのように左半分を並べ替えるのですか？ " "さて、ここで2人を並べ替えます。"そしてあなたは、のようにしている "すべての権利、結構です。" "どのようにそれらの人々の左半分を並べ替えるのですか？" "ちょうどここに、この1人をソートします。"鮮やかな啓示は今何ですか？私は1人を並べ替える必要がある。完了しました。私はすべての作業を行う必要はありません。しかし、今私はこの人を並べ替える必要があるが、彼らは一人の人は何の関係もしている。だからマジックは明らかにこの第三段階にありますソート半分をマージします。だから、マージソートは、この鮮やかな洞察力を要することは、大きな問題を打破する場合 2より小さく、同じサイズの問題にその後終わりに小さいソリューションを結び付けるだけの種類、私は、我々は、はるかに良い多くを行うことができることを提案する[タップ音を] 選択ソートや挿入ソートのいずれよりも。私は実際には半時間のためにそれを無視してきたが、私は実際に何が起こっているか分からない今日外。 [ヒューという音] [笑い] だから我々は我々の友人ロブボーデンから少し助けを借りてこれを見ることができるかどうかを確認してみましょう。マージソートの過程で、2つの大きなステップがあります。まず、継続的に半分にコップのリストを分ける我々はそれらのちょうど1カップとリストの束を持っているまで。リストには、奇数が含まれている場合は心配しないでくださいそして、それらの間完全にきれいにカットすることはできません。ちょうど任意インチ余分なカップを含めるリスト選ぶそれでは、これらのリストを分割してみましょう。今、私たちは2つのリストを持っています。今、私たちは4リストを持っている。今、私たちは、各リスト内の1杯で8リストを持っている。だからステップ1のそれだ。手順2の場合我々は繰り返し我々の前に学習したマージ·アルゴリズムを使用してリストのペアをマージします。 108と15のマージは、リスト15、108で終わる。 50と4をマージすると、我々は4、50で終わる。 8と42をマージすると、我々は8、42で終わる。と23と16のマージは、我々は16日、23日で終わる。これで、すべての私達のリストのサイズは2である。 4の各リストがソートされていることに注意してください、ので、我々は再びリストのペアをマージを開始することができます。 15と108と4と50をマージすると、我々は最初、15、4を取る次に50、次に108。 8、42、16、23をマージし、我々はまず、8、16を取るその後、23、42。だから今我々はソートされているそれぞれのサイズ4のちょうど2つのリストを持っています。だから今我々は、これらの2つのリストをマージします。まず、4を取るし、我々は、8を取るし、我々は15を取ると16と23と42と50と108。そして、我々は完了です。我々は今、ソートされたリストを持っています。ロブは、我々はまだ終わっていないことを何かを活用してのようなものだった。それが示唆されたが、我々は実際にそれをしなかった。彼は示唆しているカップを物理的に何かをやっていた彼は時間のほかに、いくつかのリソースを費やしていました。 >> [生徒]スペース。 >>それは空間であった。彼はここのスペースを持っていたところ、彼はバイレベルテーブルのこの種を持っていたという事実そしてここにスペースは実際に彼が2倍の容量を使っていることを示唆した挿入ソート、バブルソート、または選択ソート - - これまでの我々のアルゴリズムのいずれかとしかし、彼は前後に移動どのような種類のものには、この追加のスペースを活用した順序で物事を維持しながら。私たちは、ソートされたリストに着いたようにそれは感じているにもかかわらず、それはしばらく時間がかかったようにと、それは感じました。現実には、どのようなロブがやっていたことは、まさにこのアルゴリズムでした。彼は最初、サイズnの問題を取った左半分と右半分に分かれた。彼はカップを移動したときからだ。それから彼は、そのプロセスを繰り返す。彼はこっちとこっちに2の2セットに4分割した。それから彼は、そのプロセスを繰り返し、それらの様々なカップの各1の2組に2分割した。華麗な機会があれどこで、それはです。物語の中でその時点で、ロブは、サイズ1の8のリストを持っていたこれらのすべては、すでにソートされています。それでは、彼は何かに進みましたか？ペアワイズ彼はこのソートされたリストと、このソートされたリストを取り、それらをマージしました。それから彼は、この一つを取って、それらをマージして、このいずれかを、それらをマージ次に、この1と、それらをマージしました。そして彼は次は何をしたのか？彼はその後、大きなリストを再合併してから、大きなリストを再合併。あなたは今のところただ直感これを考えると、彼は実際に何をやったのですか？彼は半分に、半分に、半分に、半分に問題を分割したこれらの超小型リストを取得するためである。それから彼は、二重、二重、二重結合のようなものだった。そこで彼は、私たちがこれまで見てきたように多くの作業のように二回やっていた分割統治しますが、大したことを含むものである。二倍の仕事は、そのような大したことではありません。それだけで一定の係数です。とずっと前に私たちの算術式のように、私はちょうど定数因子を抹消するつもりです 2回のように。誰が気に？それはまだ多くのステップの倍の2,2億ましょう。だから、このマージのステップは、キーの洞察力であると思われる。ああ、それはまだ継続されているわけではありません - さんは単なる数値の前にこれを見てみましょう。ただ、実際にこれが外に再生する方法を参照するには、この数値を歩いてみましょう。これは主に、ほんの少しの貧乏人のアニメーションです。これを提案してみましょう。マージソートの実行時間 - 私達はちょうどこの話の方法を必要とします。これは数学ではなく、これは単に自分自身を表現する簡潔な方法の一種です。だから、tは時間を表し、nは何を表す？ >> [生徒]の大きさ - [マラン]問題の大きさ、人々の数。だから私は、n人をソートするための実行時間は、時間の量が0であることを行っていると主張していますあなたは1カップまたはnoコップを持っている場合は、ソートすることは何もないので、nは、2未満である場合。しかし、より一般的には、私は、実行時間がn個の要素をソートすることを提案するつもりだそれは左半分をソートするのにかかる時間に加えて、右半分になるだろうプラス - この追加+ nは何ですか？ >> [生徒]マージソート。 [マラン]ここでn / 2個の要素を持っている場合ので、それは実際に、マージだと、ここでn / 2個の要素を持って、それはそれらをマージするためにどのくらいの時間がかかりますか？ただロブのように、あなたがこっちにこれを摘み取る必要があり、多分、こっちに摘み取るこっちに摘み取る、こっち摘む、こっちに摘み取る。一度カップのそれぞれをタッチする必要があります。 4カップを加えた4個のコップがあるのなら、それは8カップだまたは、より一般的には、8 Nカップ。だからマージのステップは、我々は、nとして表現することができますそれは文字通り回数物理的に触れたロブを伴うそれらの発泡スチロール製のコーヒーカップの一つ。だから今、任意の例を実行してみましょう。 16カップがあれば、何がロブのアルゴリズムは、16個のコップを使用して、ソートの実行時間ですか？それは8カップを並べ替えるためにかかる時間の2倍の量だここで我々はここで8カップを持っているので、8カップ。私たちは一瞬Tとしてそれを一般化しているので、それはどれくらいかかるか分からない。誰がそれが何であるか知っている？しかし、今私は、再帰的にソートしたり、同じ質問を繰り返しすることができます。 8カップを並べ替えるにはそれがどのくらいの時間がかかりますか？私が言おうとしている8個のコップは、それが4杯プラス4カップを並べ替えるのに要する時間がかかる次に、それらを一つにまとめる。ファイン。我々はすでにサイクルに取得している。 4カップを並べ替えるには、どれくらいの期間がかかりますか？それは4個のコップを並べ替えるためにかかる時間は2カップ加えて2カッププラスソートマージ処理です。ファイン。 2カップを並べ替えるには、どれくらいの期間がかかりますか？ 2カップは1カップ加えて、それが別のカップを並べ替えるためにかかる時間をソートするのに要した時間ですそれに加えてマージするのにかかる時間は、それはちょうど2である。ファイン。最後の質問。 1カップを並べ替えるには、どれくらいの期間がかかりますか？ここで我々は以前のヒットだろうと予測ベースケースです。それが問題の最小値をソートするために、当社は一切の仕事を取らないという事実今ではその手段、小学校スタイルのソート、私達はちょうどピンを見るには、これらの数字を差し込む開始に行くことができ我々は現在、1のTは何かを知っているので、私は1のTは0にプラグインすることができます。それは私に私が次に上位にプラグインすることができます2のTに答えを与える。それは私に私が上位にプラグインすることができます4のTを与える。それは私に私が上位にプラグインすることができます8のTを与える。そして、私は実際にこれらの答えに接続することにより、その数学を行う場合、私はその後、16のTが64で取得します。と64は何を表すのでしょうか？ Tが16の場合、ええ、それは16の4倍だ。だから私は今、この事の実行時間は、マージソートと呼ばれると主張している - そして、これは私たちがこれまで見てきたのファンシーになるだろう - と呼ばれようとしてn個のログnさどのように多くの時間が半分にコップの全体の束を分割奪うことができるから？ n個のログを記録します。それは電話帳の例と同じだ、それは自己カウントの例と同じです。何回半分に何かを分けることができますか？しかし、このマージのステップがあります。あなたは、何度も何度も半分にコップを分割する必要があるかもしれませんマージする必要があるとしているが、毎回。そして、我々は、n個のコップをマージするnステップを取ることを以前に述べたあなたは、カップを引き抜く、カップを引き抜く必要があり、一度すべてのカップに手を触れなければならないので、ただロブがやったような。だから我々は何かのログをn回やっているし、我々はそれらの各イテレーションの上にn物事をやっている場合、それらhalvingsの各々は、我々は、n回ログnを持っています。我々は、この例では16に差し込むのであれば、16回は16の対数 - 私はベースを描かれていませんでしたので、これは今のところその理由を心配しないでください - しかし16の基部2のログには、4,16×4である64です。しかし、対照的に、我々は16の数字でバブルソートや選択ソートや挿入ソートを使用していた場合、 nが16の場合、実行時間は何だったでしょう？それはあなたが非常にすべての数学を続けていない場合でも、256で乗16、、、でしょう 256は64より大きいです。それがここでは本当に魔法の持ち帰りです。とPSETにあなたが意志として小さい例でこれを介して作業することを実現それすべてがはるかに直感的になります。しかし、実際にこのアルゴリズムの感触の点で何を意味するのかは、この次のとおりです。我々は実際にここマージソートを見れば - 私はここにこのウィンドウ上でプルアップしてみましょう - これは、我々はこれらのアルゴリズムのすべての3を持っているそれによって若干異なる例です - バブル、選択、およびマージ - 側でわずか側。彼らはすべてランダムバーで開始している、それは良いことだ。誰も他の上で基本的な利点を持っていません。、スタートスタート、スタート - - 私は、現時点でこれらのアニメーションのそれぞれをクリックするつもりですことを私は、大体、それらはすべて、同時に起動することができますできるだけ速くと時間を実行してバブルソートの最悪のケースとは何かというのを考えてみましょう？ >> [生徒] Nの2乗。 Nは二乗。選択ソートの最悪の場合の実行時間は何ですか？ Nは二乗。とマージソートは明らかです - あなたは非常にすぐにすべての数学に従わなかった場合でも、それは時間をかけてはるかに直感的になるでしょう - つまり、我々が主張する、n回ログn。そして、ためにログnは厳密未満であるn回、我々は大きな数字を持っている n回ログnはn倍より小さいnまたはn乗です。それでは、それは、実際に実行時間の面でより優れたアルゴリズムであることが感じられますか n回のログnとは対照的にNの2乗？ここに私達は行く。クリック、クリック、クリック。それはそれはマージソートのようなものを使用することの意味です。我々は瞬間を持っています。ここで何が起こるか見てみましょう。誰のお金バブルソートにある[笑い]を？むしろ、時々入力に依存します。見てみましょう。さあ。彼が追い上げているようにそれは感じている。 >> [生徒]、バブルソートを行く！ [学生がさらさら] [マラン]うん、うん。 [さらさら学生]行く、行く、行く！ [すべての応援] [拍手] だから今1最後の、最後のデモで、あれば、それは数学のまわりであなたの心をラップするために、少し注意が必要ですまたはそこに一種の可視化は、実際に速度を聞くことができます異なるアルゴリズムの異なる。これは実際には仲間が聞こえること作らアニメーション誰かですスワッピングのプロセスやバーの高さを持つ。我々がここで見ていくように、人々が考えていることをそこにさらにいくつかのソートアルゴリズムがあります。この最初のものは、挿入ソートになるだろう、これは通って飛ぶでしょうそしてあなたにこれらの様々なアルゴリズムがどのように働くかの音感覚を与える。ここで、挿入ソートです。 [電子ビープ音] [マラン]バブルソート。 [速い電子ビープ音] [マラン]セレクションソート。 [速い電子ビープ音] [マラン]マージソート。 [電子ビープ音] [笑い] [ビープ音が遅く]を [マラン] Gnomeのソート。 [電子ビープ音] これはCS50です。我々は、来週お会いしましょう。 [拍手と歓声] [CS50.TV]