>> [音樂播放]
>> ANDI鵬：歡迎來到第3個星期
謝謝你們，所有的未來 到今天這個較早的開始時間。
我們已經有了一個很好的，小 今天的親密組。
所以希望我們會得到 說完，或許，早，
一點點今天一早。
那麼快，只是一些 今天議程公告。
在我們開始之前，我們 要只走了過來
一些簡單的後勤問題，PSET 題，匯報，這樣的事情。
然後，我們將深入權利英寸
我們將使用一個名為GDB來調試程序 啟動揭穿我們的代碼，大衛
有一天在課堂解釋。
我們就去了四種類型的排序。
我們會去超過他們很快 因為他們非常密集。
但是要知道，所有的幻燈片和 源代碼是永遠在線。
所以感到自由，在你細讀，以 回去看看那個。
>> 我們將通過 漸近符號，這
僅僅是一個奇特的方式 說“運行時間”
在這裡，我們有大O，從而 大衛在演講解釋。
而且我們也有歐米茄，這 是下界運行時。
我們將討論多一點 深入的關於如何將這些工作。
最後，我們就去了二進制搜索， 因為很多你誰已經
看了一眼你的pset便知 這是一個問題，在你的pset中。
所以，你都會很高興 我們管這個今天。
>> 最後，根據您的 部分反饋意見，其實我
在離開約15分鐘 年底剛剛走了過來
pset3物流，如有問題， 也許有點指導，如果你願意，
我們開始編程了。
因此，讓我們試著打通 該材料很快。
然後我們就可以花一些時間 同時為處理器集更多的問題。
確定。
>> 很快，所以只是少數 我們之前宣布從今天開始。
首先，歡迎來製作 它通過兩個你的pset中。
我看了看your--是啊，讓我們 獲得掌聲的那一個。
其實，我是真的， 真的很感動。
我分級的第一個PSET為你們 上週，你們做了令人難以置信的。
>> 風格是在點 除了一些意見。
請確保你總是 註釋你的代碼。
但是，你的pset中都點上。
並保持了起來。
而且它的良好的平地機到 看到你們是把
在你的風格盡可能多的努力 和你在你的代碼設計
我們想給你看。
所以我路過沿著我的謝意 為助教的其餘部分。
>> 然而，有一個 一些匯報的問題
我只是想說明一下 可使兩個我的生活
和許多其它的 助教的生活更容易一點。
首先，我注意到這個 過去week--你們有多少人
已經運行check50 在你的代碼提交？
確定。
所以每個人都應該做的check50， 因為 - 一個secret--我們實際上
運行check50作為我們的正確性的一部分 腳本測試代碼。
所以，如果你的代碼是失敗的 check50，在所有的可能性，
它可能會 失敗我們檢查為好。
有時候你們 有正確的答案。
像，在貪婪的，一些 你有正確的號碼，
你只需打印出一些額外的東西。
而這額外的東西 實際上未通過檢查，
因為電腦不 真的知道它在尋找。
因此，這將只運行通過， 看到你的輸出不
符合我們所期待的答​​案 要，並註明這是錯誤的。
>> 我知道，發生在 你的一些情況下，這個星期。
所以，我回去和手動 regraded每個人的代碼。
在未來雖然， 請，請確保
你正在運行 在你的代碼檢查50。
因為它是一種為TA疼痛 不得不回去手動再分類
每一個每一個PSET 單，很少錯過實例。
所以，我沒有脫任何積分。
我想，我脫下也許 的一個或兩個用於設計。
在未來雖然，如果 你失敗check50，
點將會採取 關閉正確性。
>> 此外，pset中是 由於週五中午。
我覺得有一個7分鐘 我們給你遲到寬限期。
每哈佛的時候，他們獲准 為7分鐘遲到的一切。
因此，這裡在耶魯，我們將 堅持這一點。
但相當多，在12:07， 如果你的PSET不在，
這將是為後期標記。
因此，雖然它被標記為 為末，TA--我
還是會被分級您的pset。
所以，你仍然會看到一個檔次的出現。
但是，要知道，在 學期結束時，
所有後期的pset將只是 由計算機自動歸零。
>> 我們這樣做有兩個原因。
其中，有時我們得到 原諒，就像院長的藉口，
後來，我不知道呢。
因此，我們希望確保我們分級 一切都為了以防萬一，比如，我
缺少院長的藉口。
其次，要 心中，你仍然可以
摔個PSET的 有完整的範圍點。
因此，我們要分級 所有的pset只是
以確保您的範圍的 那裡，你想他們。
因此，即使是晚了，你還是會 獲得信貸的範圍點，我想。
>> 因此，道德的故事，使 確保你的pset是導通時間。
並且如果它們不是在導通時間， 知道這是不是很大。
是啊，在我繼續前進，沒有任何人有 有關PSET反饋有任何疑問？
是啊。
>> 聽眾：你是說，我們 可以去掉的pset之一？
>> ANDI彭：是的。
因此，有九pset中整體 在這學期的課程。
如果你有範圍 points--因此範圍是正義的，
相當多，你嘗試了 問題是，你投入的時間，
你表明你已經 表明您已經閱讀了規範。
這是相當多的範圍。
如果你正在履行 範圍點，我們
可以降最低 一出的全部範圍。
所以這是你的優勢， 完成並想盡一切PSET。
>> 即使upload--如果沒有 他們的工作，快點上傳所有。
然後我們就希望能夠 給你一些這些點回來。
酷。
其他問題嗎？
太好了。
>> 其次，辦公hours--數 有關辦公時間快速筆記。
因此，首先，走在了本週初。
沒有人是曾經在 辦公時間週一休息。
Christabel來到 昨晚辦公時間。
是啊，Christabel。
和我們有在辦公室什麼 小時昨晚，Christabel？
>> 聽眾：我們有冰淇淋。
>> ANDI彭：所以這是正確的，我們有 冰淇淋辦公時間昨晚。
雖然我不能答應你， 我們將有冰淇淋辦公時間
每個星期，我可以向你保證 的是，將有顯著
更好的學生到TA的比例。
像合法的，就好像是三比一。
然而，對比，與 週四你有大約150
真正強調的孩子和沒有冰淇淋。
而且它只是沒有生產任何人。
所以這個故事的寓意是，來得早 在辦公時間，辦好事
會發生。
>> 此外，有備而來提問。
你知道嗎？
不管什麼助教，我 想，一直在說，
我們已經獲得一對學生情侶 誰在週四進來的一樣，10:50
不看了規範 是一樣幫助我，幫助我。
不幸的是，在這一點上，還有 沒有多少，我們可以做些什麼來幫助你。
所以，請進來本週初。
來得早在辦公時間。
有備而來的提問。
請確保您作為 一個學生，都在那裡
你必須使得 助教可以引導你前進，
這正是辦公時間 應分配的。
>> 其次，所以我知道教授 喜歡我們測試的驚喜。
我有一個教授的 像喲，順便說一下，
請記住，中期 你下週一。
是啊，我不知道是中期。
所以我將是那個TA 提醒大家，測驗
0--因為，你知道，我們是CS。
現在，我們已經做了數組，你會得到 為什麼它的測驗0，沒有測驗1，是嗎？
確定。
呵呵，我得到了一個有些笑。
確定。
>> 因此，測驗0將是10月14日，如果 你在週一至週三節
而10月15日，如果你在 週二至週四部分。
這不適用於 那些你在哈佛
who--我想你會都是 以14號的測驗。
>> 所以呀，在下週，如果 大衛在演講中，雲，
是啊，所以有關 競猜下週，大家
將不會因為震驚 您來第
你知道你的 測驗0是在兩個星期。
而且我們必須檢討 會議和一切。
所以不愁 被嚇到了點。
如有任何疑問before--任何疑問 在所有有關的後勤問題，
分級，辦公時間，部分？
是啊。
>> 聽眾：所以小測驗 將要演講期間？
>> ANDI彭：是的。
所以測驗，我想，是60 分配在時隙分鐘
你會只拿 在報告廳。
所以，你不必進來 上一樣，隨機下午7:00。
這一切都很好。
是啊。
酷。
>> 好的。
所以，我們要 介紹一個概念，你
本週大衛早已種 這個過去一周觸及的講座。
這就是所謂的GDB。
你們有多少人而且，當 寫你的pset的過程中，
已經注意到一個很大的按鈕，上面寫著 在您的IDE頂部的“調試”？
確定。
所以，現在，我們將真正得到挖掘 其實什麼按鈕的奧秘
確實。
我向你保證，這是一個 美麗的，美麗的東西。
>> 所以到現在為止，我覺得 還有的是兩件事情
學生已通常 調試的pset在做。
一，他們要么加入 printf（）的 - 所以每幾行字，
他們加入一個printf（） - 哦，這是什麼變量？
哦，這是什麼變量now-- 樣的，你會看到進展
你的代碼，因為它運行。
或者第二種方法孩子們做的是 他們只寫了整個事情
然後轉到這樣在末端。
希望它的工作原理。
我向你保證，GDB更好 比兩者的那些方法。
是啊。
因此，這將是你最好的朋友。
因為它是一個美麗的東西 在視覺上同時顯示
你的代碼做 在特定點
以及所有的你的 變量都在進行，
喜歡什麼他們的價值觀， 在該特定的點。
而這樣一來，你才能真正 設置在代碼中的斷點。
您可以通過一行一行地運行。
和GDB只會有 您，向您顯示，
什麼你所有的變量 是，他們在做什麼，
這是怎麼回事代碼。
並且在這樣的方式，它的 所以更容易看到
發生了什麼的printf的-ING代替 或寫下你的陳述。
>> 所以我們會做後面的一個例子。
因此，這似乎有點抽象。
不用擔心，我們會做的例子。
所以本質上，三個最大的， 最常用的功能，你需要在GDB
是接下來，步過， 而步入按鈕。
我將頭以上 在那裡，其實，就是現在。
>> 所以你們可以都看到， 或者我應該放大一點？
在後面，你能看到嗎？
我應該放大？
只是一點點？
OK，涼。
在那裡，我們走了。
確定。
>> 所以我在這裡，我 實現貪婪。
雖然很多你們的寫 貪婪form--，雖然環
是一種完全可以接受的方式做 它 - 另一種方式來做到這一點是根本
在分模。
因為那樣的話，你可以有你 值，然後讓你的其餘部分。
然後你可以只 加上它一起。
請問對我在做什麼邏輯 這裡是有意義的每一個人，
之前我們開始？
樣的？
酷。
太好了。
這是一個非常性感的一塊 的代碼，我會說。
就像我說的，大衛，在 講課，過了一段時間，
你們都開始看到的代碼 作為東西是美麗的。
有時，當你看到漂亮 代碼，它是這樣一個美妙的感覺。
>> 因此然而，儘管這個代碼是非常 美麗的，它不能正常工作。
因此，讓我們在這個運行check50。
檢查50 20--空中接力。
2？
那是pset2？
是啊。
哦，PSET1。
確定。
所以我們運行check50。
>> 正如你們所看到的， 它的失敗一對夫婦的案件。
而對於一些你，在 做你的問題集的過程中，
你喜歡啊，為什麼不工作。
為什麼工作一段 值，而不是為別人？
那麼，GDB是要幫助你的身影 為什麼這些投入並沒有工作。
>> 確定。
所以，讓我們來看看，之一 檢查我是失敗的check50
為0.41的輸入值。
所以正確答案 你應該得到一個4。
而是我所打印出 是3-n中，這是不正確。
因此，讓我們只是手動運行它，只是 確保check50正常工作。
讓我們做./greedy。
哎呀，我一定要貪婪。
在那裡，我們走了。
現在./greedy。
>> 多少錢是欠？
讓我們做0.41。
而且是的，我們在這裡看到 ，它的輸出3
當正確的答案， 事實上，應為4。
因此，讓我們進入GDB，看看我們如何 可以去解決這個問題。
>> 因此在第一步驟中 一直調試代碼
是設置一個斷點， 或在這一點，你
希望計算機或 調試器開始尋找。
所以，如果你真的不 知道你的問題是什麼，
通常情況下，一般的事情，我們要 做的是設置了斷點為主。
所以，如果你們可以看到這 紅色按鈕就在那裡，
是的，這是我的設置 斷點的主要功能。
我點擊了。
>> 然後我就可以去了我的Debug按鈕。
我打那個按鈕。
讓我放大了，如果我能。
在那裡，我們走了。
因此，我們有，在這裡，在面板上的權利。
我很抱歉，伙計們在後面，你 實在看不出真的很好。
但本質上，所有的 該右側面板做
被跟踪的兩個突出 線，這是代碼行
計算機正在運行， 以及所有的變量
到這裡。
>> 所以，你有美分，硬幣，N， 所有申報不同的東西
在這一點上。
不用擔心，因為我們沒有真正 它們初始化的變量呢。
因此，在你的電腦，你 電腦只是看到，
哦，32767是最後使用的功能 在我的電腦的內存空間。
所以這就是美分是目前。
但是，沒有，一旦運行該代碼， 它應該成為初始化。
>> 因此，讓我們通過，一行 行，這是怎麼回事的。
確定。
所以，在這裡是三個 按鈕，我剛才解釋。
你有玩，或者運行功能， 按鈕，你有步驟結束按鈕，
你也有步驟為按鈕。
並且基本上，所有三個 他們只是通過你的代碼
而做不同的事情。
>> 所以通常情況下，當你正在調試， 我們不希望只是打遊戲，
因為比賽將只運行 你的代碼，它的結束。
然後，你不會真的 知道你的問題
除非你設置多個斷點。
如果設置了多個斷點， 它只是自動
從一個斷點運行， 到下一個，到下一個。
但是，在這種情況下，我們已經 只是那一個，因為我們
希望我們的工作方式 從頂部向下至底部。
所以，我們要忽略按鈕 現在為了這個計劃。
>> 因此，在步函數只是 在每一行的步驟
並告訴您 計算機在做什麼。
該步驟為函數去 到實際的功能
這是對你的代碼行。
因此，例如，如printf（）， 這是一個函數，對不對？
如果我想在物理上一步 到printf（）函數，
我真的進入片 其中，printf（）的寫，看看代碼
這是怎麼回事那裡。
>> 但通常，我們假設 我們為您提供的代碼工作。
我們假設printf（）的正常工作。
我們假設調用getInt（）的工作。
因此，有沒有必要 走進這些功能。
但是，如果有功能 你寫你自己
要檢查 發生了什麼事情，
你會想一步 入該功能。
>> 所以現在我們只是 跨過這段代碼。
所以，讓我們來看看。
哦，打印，“哦，海，怎麼樣 多大的改變是欠？“
我們不關心。
我們知道的工作， 所以我們跳過它。
>> 因此n，這是我們的浮動是 我們已經initialized--或declared--
在頂部，我們現在是 等於說，以GetFloat（）。
因此，讓我們跨過這道。
而我們在看 底部這裡，程序
這促使我輸入一個值。
因此，讓我們輸入我們想要的值 在這裡測試，這是0.41。
太好了。
>> 所以，現在N--做你們看 這裡，在bottom--它的
stored--因為我們 還沒有四捨五入的是，它
存儲在這個像巨大 浮動是0.4099999996，
這是足夠接近我們的 目的，現在，到0.41。
然後，我們將在後​​面看到，因為我們 繼續加強在該程序，
後這裡，正變得 圓潤和分成為41。
太好了。
因此，我們知道，我們的舍入的工作。
我們知道，我們有 正確的數量美分，
所以我們知道，這是 沒有真正的問題。
>> 因此，我們將繼續加強 在此計劃。
我們去這裡。
而這行代碼之後的話，我們 要知道我們有多少個季度有。
我們跳過。
而且你看我們做什麼，其實，有一個 季度，因為我們已經減去25
從41我們的初始值。
我們有16個左右為我們美分。
>> 大家是否明白如何 該程序是通過步進
為什麼美分現已成為16 為什麼，現在，硬幣已經成為1？
是每個人以下的邏輯是什麼？
酷。
因此，作為這一點的，在 計劃的工作，對不對？
我們知道這是做完全 我們希望它。
而我們實際上並沒有 要打印出來，哦，
是仙在這一點上， 什麼是硬幣在此點。
>> 我們將繼續經歷的程序。
步過。
酷。
我們去了助攻。
太好了。
我們看到，它採取 關閉$ 0.10一角錢。
而現在我們有兩個硬幣。
這是正確的。
>> 我們去了幾個便士而我們看到的 我們已經得到了遺留美分。
嗯，這很奇怪。
在這裡，在該程序中，我應該 已減去我便士。
也許我只是沒有 這樣做行權。
唉，你可以看到 在這裡，因為我們知道
我們正在加緊 通過線32和33，
這就是我們的計劃 不當有變量運行。
因此，我們可以看看，看看，哦， 我在這裡減去美分，
但我沒有實際 添加到我的幣值。
我加入到美分。
我不希望添加到 分錢，我要添加到硬幣。
因此，如果我們改變，要硬幣， 我們已經有了一個工作程序。
我可以運行check50。
你可以只退出的GDB右出 這裡，然後再次運行check50。
我可以做到這一點。
我一定要貪婪。
0.41。
而在這裡，它的印刷 出正確的答案。
>> 所以當你們可以看到，GDB 是一個非常強大的工具
當我們有這麼多的代碼 怎麼回事，這麼多的變數
它很難對我們來說，作為 一個人，來跟踪。
計算機，在GDB 調試器，有能力
多事的。
我知道，在VISIONAIRE，你們可能 可能擊中了一些段故障
因為你正在運行 從你的陣列的界限。
在凱撒的例子，這是 正是我在這裡實現。
>> 所以，我忘了檢查 如果會發生什麼，我
沒有兩個命令行參數。
我只是沒有擺在那檢查。
所以，如果我跑Debug--我設置 我的斷點就在這裡。
我運行調試。
>> 確定。
是啊。
所以實際上，GDB應該 已經告訴我，
是分割故障出現。
我不知道發生了什麼事情 在那裡，但是當我運行它，
這是工作。
當您運行通過行代碼 GDB可能只是突然退出你，
上去看看紅色的錯誤是什麼。
它會告訴你的，嘿嘿，你 有段錯誤，
這意味著您嘗試訪問 以陣列的空間不存在的。
是啊。
>> 因此，在接下來的問題 本週集，你們
可能有很多 變量左右浮動。
你不會是知道 它們都是指在某一點。
因此，廣發行將真正幫助你在盤算 它們是什麼都等於
並能夠看到直觀。
有沒有人困惑於如何 任何被工作？
酷。
好的。
所以在這之後，我們 去潛水權
成四種不同的 排序類型本週。
你們有多少人，第一次 所有的人，在我們開始之前，
讀完整個規範的pset3？
確定。
我是你們的驕傲。
這就像半個班，這 是顯著超過上一次。
>> 所以，這是偉大的，因為當 我們談論的內容
在lecture--還是遺憾， 在section--我喜歡
以涉及了很多的 回PSET是什麼
你想如何 實現在你的pset中。
所以，如果你來有 讀取規格，它會
是一個更容易讓你明白 我說的是，當我說，
嘿，這可能是一個真正的 實現這種好地方。
所以，你們誰讀了 SPEC知道，作為你的PSET的一部分，
你將不得不 寫一個排序的類型。
所以，這可能是非常有幫助 今天很多你。
>> 因此，我們將剛開始時， 本質上，最簡單類型
排序，選擇排序。
典型的算法 我們怎麼會去這
is--大衛通過這些全都走了進去 講座，所以我會很快待著
這裡 - 本質上，你 有值的數組。
然後你找到 最小的未分類的價值
和你交換與價值 第一個未排序的值。
然後你只是不斷重複 以列表的其餘部分。
>> 而且這裡有一個直觀的解釋 如何將工作。
因此，例如，如果我們開始 與五個元件的陣列，索引
0至4，用3,5，2,6，和4個值 所以，現在擺在array--，
我們只是假設 他們都是未分類
因為我們還沒有測試過，否則。
>> 因此，如何選擇排序會 工作是，那就先
通過整體運行 未排序的數組。
這將挑選出的最小值。
在這種情況下，如圖3所示，右 現在，是最小的。
它得到5。
不，5不大於than-- 或不好意思，不低於than-- 3。
所以最小值仍然3。
然後你到2。
電腦看，哦，2小於3。
2現在必須的最小值。
所以2掉期與第一個值。
>> 因此，人們通過後，我們確實看到 該2和3被交換。
而我們只是要繼續做 這再次與陣列的其餘部分。
因此，我們將只運行通過 最後四個指標的數組。
我們會看到，3 下一最小值。
所以，我們要交換與4。
然後，我們只是要繼續 貫​​穿直到最後，你
得到一個排序的數組中 2，3，4，5，和6被所有排序。
大家是否明白邏輯 如何選擇排序工作？
>> 你只要有某種 的最小值。
你跟踪的那是什麼。
每當你找到它，你將其交換 與在array--第一值
或者，不是第一value-- 陣列中的下一個值。
酷。
>> 所以當你們那種 從短暫的一瞥看到，
我們要偽代碼這一點。
所以，如果你們在後面要 組成一個小組，每個人都在一張桌子
可以形成一個小夥伴，我要去 給你們喜歡3分鐘
剛才講通過 邏輯，英語，
對我們如何能夠實現 偽代碼寫一個選擇排序。
還有的糖果。
請上來，並得到糖果。
如果你在後面，你想 糖果，我會向你扔糖果。
其實，做你 - 爽。
哦，對不起。
確定。
>> 所以，如果我們想，作為 一類，寫偽代碼
如何人們可能接近 這個問題，只是覺得自由。
我就到處去和， 為了，問群體
對於下一行 我們應該做的。
所以，如果你們想開始 關，什麼是第一件事情
當你試圖做 實現的方式來解決這個方案
有選擇地排序列表？
讓我們只是假設我們 有一個數組，沒事吧？
>> 聽眾：你想創造一些 排序[聽不清]你是
通過你的整個陣列的運行。
>> ANDI彭：對。
所以，你會想迭代 通過每一個空間，對不對？
所以，偉大的。
如果你們想給我 接下來line--是啊，在後面。
>> 聽眾：檢查他們 全部為最小。
>> ANDI彭：我們去那裡。
因此，我們希望通過和檢查 看到最小值是什麼，對不對？
我要縮寫，為“最小”。
你們有什麼想後做 你已經找到了最小值？
>> 聽眾：[聽不清]
ANDI彭：所以你會想 與第一個數組中打開它，
對不對？
這是開始的時候，我會說。
好的。
所以，現在你已經換第一 一，什麼你想以後做什麼？
所以，現在我們知道，這一個在這裡 必須是最小的值，對不對？
然後，你有一個額外的休息 該陣列是無序的。
所以，你想在這裡做的，如果你有什麼 人想給我的下一行？
聽眾：那麼接下來你要遍歷 通過該陣列的剩餘部分。
ANDI彭：是的。
還等什麼，通過它遍歷 那種暗示我們可能會需要什麼？
什麼類型的of--
>> 聽眾：哦，一個額外的變量？
ANDI彭：可能 另一個循環，對不對？
因此，我們可能會想 迭代through--很大。
然後，你要回去 可能再次檢查最低，
對不對？
而你要不斷重複 這一點，因為環正要
繼續運行，對吧？
>> 所以當你們可以看到，我們 只是有一個大致的偽代碼
我們如何希望這個節目的樣子。
這裡這個迭代，我們怎麼 通常需要在我們的代碼編寫
如果我們要遍歷一個 陣列，什麼類型的結構？
我想Christabel 之前已經說過這​​一點。
>> 聽眾：for循環。
>> ANDI彭：一種循環？
沒錯。
因此，這可能是 將是一個for循環。
什麼是這裡的檢查會意味著什麼呢？
通常情況下，如果你想查詢 如果有什麼東西else--
>> 聽眾：如果。
>> ANDI彭：如果一個，對不對？
然後在這裡交換，我們將 去了以後，因為大衛·
通過講座去為好。
然後第二個迭代implies--
>> 聽眾：另一個循環。
>> ANDI彭：--another for循環，沒錯。
因此，如果我們正在尋找 在這個正確的，我們
可以看到，我們可能 將需要一個嵌套的循環
在有一個條件語句 然後代碼的一個實際的一塊是
要交換值。
所以，我只是一般寫 這裡一個偽代碼。
然後，我們實際上會 到身體上，作為一類，
試試這個今天實現。
讓我們回到這個IDE。
>> 嗯，哦。
這是為什麼不是 - 它就在那裡。
確定。
對不起，讓我盡量放大一點。
在那裡，我們走了。
我做的是在這裡我創建 一個名為“選擇/ sort.c。”
我創建了九個數組 值，4，8 2，1，6,9，7,5，3。
目前，你可以 看，他們是無序的。
n為將成為數 告訴你值量
你在你的陣列。
在這種情況下，我們有九個值。
我剛剛得到了一個for循環在這裡 打印出的排序的數組。
>> 而在最後，我也得到了一個為 循環，只是打印出來了。
因此從理論上說，如果此程序 工作正常，到了最後，
你應該看到一個打印的循環 其中，1，2，3，4，5，6，7，8，
9都是正確的順序。
>> 所以，我們在這裡得到了我們的偽代碼。
有誰想用於：我只是 要去問volunteers--
確切地告訴我，如果什麼類型 我們希望，第一，只是想迭代
通過這個數組的開始？
什麼是代碼行我 可能要在這裡需要什麼？
>> 聽眾：[聽不清]
>> ANDI彭：是啊，感覺 免費用於：對不起，你
不必忍受up--手感 自由地提高你的聲音有點。
>> 顧客：INT I等於0--
>> ANDI彭：是的，不錯。
>> 觀眾：我是小於數組的長度。
>> ANDI彭：因此，保持在 介意在這裡，因為我們
不具有功能 告訴我們的陣列的長度，
我們已經有一個 值，其存儲。
對嗎？
另一件讓 在mind--以陣列
九價值觀，有什麼指標？
遠的不說這個數組是0至3。
你看，最後 指數實際上是3。
這不是4，即使有 陣列中的四個值。
>> 所以在這裡，我們必須非常小心， 什麼我們條件的長度
將是。
>> 聽眾：那豈不是為n減去1？
ANDI彭：這是怎麼回事 Ñ​​減去1，正好。
這是否有意義，為什麼 它n值減1，每個人？
這是因為數組是零索引。
他們從0開始並運行最多n個減1。
是的，這是一個有點棘手。
確定。
而then--
聽眾：Isnt'1那 已經採取的雖然照顧，
通過剛才不是說“小於或 等於“，只是說：”不到？“
>> ANDI彭：這是一個 非常好的問題。
所以，是的。
而且，我們的方式是說 實施檢查權，
你需要比較兩個值。
所以，你真的想 離開“到”空。
因為如果你比較 這一次，你不會
有後什麼 要比較的，對不對？
是啊。
所以我++。
讓我們添加括號研究。
哎呦。
太好了。
因此，我們有初 我們的外環。
所以，現在我們可能要 建立保持一個變量
軌道的最小值，對不對？
沒有人想給我 行代碼，將做到這一點？
我們需要什麼，如果我們打算 想儲存什麼？
>> 右。
對於也許一個更好的名字 將be--“臨時”完全works--
也許更恰當地命名會是這樣， 如果我們希望最小value--
>> 聽眾：最小。
ANDI彭：分鐘，我們走吧。
分將是一件好事。
所以在這裡，我們怎麼 要初始化為？
這是一個有點棘手。
因為現在在 開始本陣，
你有沒有看什麼，對不對？
還等什麼，自動，如果 我們只是i等於0，
我們怎麼想初始化 我們的第一個最小值？
觀眾：我。
ANDI彭：我，沒錯。
Christabel，那我們為什麼還要 它初始化到我？
>> 聽眾：因為， 我們從0開始。
所以，因為我們沒有什麼可比較 它，最小最終會被0。
>> ANDI鵬：沒錯。
所以她完全正確。
因為我們還沒有真正 看著任何東西，
我們不知道我們的最低值。
我們希望只是將其初始化為 我，這，目前，就在這裡。
而且，我們將繼續 向下移動，這陣，
我們將看到，每個 額外的傳球，我遞增。
因此，在這一點上， 我很可能會
想為最小， 因為這將是什麼
是未排序數組的開始。
酷。
>> 所以，現在我們要添加 一個for循環，這裡的
要遍歷 未分類，或該陣列的其餘部分。
沒有人想給我一個 行代碼，將做到這一點？
Hint--我們需要什麼到這裡？
這是怎麼回事往這個循環？
是啊。
聽眾：所以我們會想 有一個不同的整數，
因為我們通過休息運行 數組，而不是我，所以也許對
學家
>> ANDI彭：是啊，J聽起來不錯。
等於？
>> 聽眾：那將是我加1，因為 你開始的下一個值。
然後到end--如此反复，j為 小於n減去1，然後J ++以下。
ANDI彭：太好了。
>> 然後在這裡，我們將要 檢查，看看是否符合我們的條件，
對不對？
因為你想 改變的最小值
如果它實際上是小於什麼 你對比的話，對不對？
那麼，我們將要在這裡？
請檢查。
聲明什麼類型 我們有可能將
TI想，如果用我們 要檢查些什麼呢？
>> 聽眾：if語句。
>> ANDI彭：if語句。
所以if--，什麼將是 我們希望裡面的狀況
我們的if語句？
>> 聽眾：如果j值 小於I--值
>> ANDI鵬：沒錯。
所以if--所以這個數組被稱為“數組”。
太好了。
因此，如果array--那是什麼？
再說了。
>> 聽眾：如果array-j是小於 數組我的話，就要改變最小。
所以分鐘就學家
>> ANDI彭：這是否有意義嗎？
確定。
而現在到這裡，我們其實 要實現交換，對不對？
所以記得，在演講中，大衛，當 他是想換the--是什麼
它 - 橙汁和milk--
>> 聽眾：這是毛。
>> ANDI彭：是啊，這是種毛。
但它是一個相當不錯的 概念展示時間。
因此，認為你的價值在這裡。
你有一個數組 的分，i的陣列，
或不管我們想在這裡交換。
而且你可能無法將其倒入 對方在同一時間，對吧？
那麼究竟是為了什麼 需要創建在這裡
為了正確交換價值？
>> 聽眾：一個臨時變量。
>> ANDI彭：一個臨時變量。
因此，讓我們做INT溫度。
你看，這將是一個更好的 時間用於：哇，那是什麼？
確定。
因此，這將是一個更好的 時間命名變量“溫度”。
因此，讓我們做INT溫度。
什麼是我們要 SET TEMP等於在這裡？
聽眾：最小？
ANDI彭：這是一個有點棘手。
它實際上無所謂到底。
它什麼都無所謂 為了您選擇交換
只要你確保你 跟踪你交換什麼。
>> 聽眾：這可能是數組我。
>> ANDI彭：是的，讓我們做陣列我。
然後什麼是下一行 的代碼，我們要在這裡？
聽眾：陣列-i等於陣列-J。
ANDI彭：最後一點？
聽眾：陣列-J等於陣列我。
聽眾：或數組，j為 陣列temp--或溫度。
>> ANDI彭：OK。
因此，讓我們運行這個，看看 如果它去上班。
哪裡是怎麼回事？
哦，這是一個問題。
見，第40行，我們 嘗試使用數組-J？
但是，在沒有Ĵ只存在嗎？
>> 聽眾：在for循環。
ANDI彭：對。
那麼，我們將需要做什麼？
>> 聽眾：外the--將其定義
聽眾：是的，我想你 if語句，使用權的另一個？
所以像，如果minimum-- 好吧，讓我想想。
>> ANDI彭：伙計們，試試 看看咱們的
看看，什麼的東西，我們可以在這裡做什麼？
>> 聽眾：OK。
因此，如果最低不等於 j--所以如果最小仍然I--
那麼我們就不會掉。
>> ANDI彭：這是否等於我？
你怎麼在這裡想說的？
>> 聽眾：或者是啊，如果 最低不等於我，是的。
ANDI彭：OK。
好了，解決了，那種，我們的問題。
但是，這仍然沒有解決 如果j--發生，因為Ĵ哪些問題
外面它不存在，什麼 你，我們想用它做？
外部聲明呢？
讓我們嘗試運行此。
嗯，哦。
我們的排序不工作。
>> 正如你所看到的，我們最初的 數組有這些值。
事後它應該有 一直在1，2，3，4，5，6，7，8，9。
它不工作。
啊。
我們該怎麼辦？
聽眾：調試。
ANDI鵬：好的，我們可以試試。
我們可以調試。
縮小了一點。
讓我們設置的斷點。
讓我們去like--確定。
>> 所以，因為我們已經知道， 這些線路，15至22，
在working--因為我做的是 通過與printing--只是迭代
我可以繼續跳過。
讓我們從第25行。
空中接力，讓我擺脫這一點。
>> 聽眾：所以斷點的 其中，調試開始？
ANDI彭：或停止。
聽眾：或停止。
ANDI彭：是的。
您可以設置多個斷點和 它可以只從一個到另一個跳。
但是，在這種情況下，我們不知道 那裡的錯誤發生。
所以，我們只是想 從上向下展開。
是的。
確定。
>> 因此，這條線在這裡，我們可以介入。
你可以看到這兒， 我們已經有了一個數組。
這些都是價值 是陣列中。
你看到了，怎麼指數為0， 對應於value--哦，
我要去嘗試進行放大。
對不起，這真的很難 以see--數組索引0，
我們有4的值， 然後依此類推等等。
我們有自己的局部變量。
現在我等於 0，這是我們希望它是。
>> 因此，讓我們繼續單步調​​試。
我們的最低等於0， 我們也希望它是。
然後，我們進入我們的第二個用於 環，如果陣列-j是小於陣列-i的，
它不是。
所以，你怎麼看 即跳過了嗎？
>> 聽眾：所以要把如果 最低，所有that--不應該的
在裡面的第一個for循環？
ANDI彭：沒有，因為 你還是想測試。
你想要做一個比較每 時間，即使你通過它運行。
你不只是想這樣做 在第一通過。
你想做到這一點的 再每增加一個通行證。
所以，你要檢查 你的病情裡面。
所以，我們只是要 讓經過這裡運行。
我給你們一個提示。
它必須做的事實是，當 你檢查你的條件，
你不檢查 正確的索引。
所以現在你檢查 殲數組索引小於陣列
我索引。
但是，你在做什麼了，在 for循環的開始？
難道你不設置Ĵ等於我？
>> 是啊，所以我們實際上可以 退出調試器在這裡。
因此，讓我們來看看我們的偽代碼。
For--我們要 開始我等於0。
我們要上浮到n減去1。
讓我們來看看，沒我們有這個權利？
是的，這是正確的。
>> 因此，然後在裡面在這裡，我們 要創建一個最小值
並設置等於i。
難道我們這樣做嗎？
是的，這樣做。
現在，在我們內心的for循環中，我們 要做到j為我到n減去1。
難道我們這樣做嗎？
事實上，我們做到了。
>> 所以，不管，什麼是我們比較嗎？
>> 聽眾：J-加1。
ANDI鵬：沒錯。
然後你會想設置 您的最低等於到j加1為好。
所以，我通過真的很快去了。
難道你們明白 為什麼它的殲加1？
確定。
>> 因此，在你的陣列，在 你的第一個闖關，
你的for循環，對於int i等於0，我們只
假設這並沒有改變呢。
我們的陣列，完全， 短短四年未排序的元素，對不對？
因此，我們要初始化i等於0。
而我是要只 通過這個循環運行。
因此在第一輪，我們要 初始化一個名為“分”變
這也等於我，因為 我們沒有一個最小值。
所以這是當前等於0為好。
然後，我們將經歷。
我們想再次重複。
現在我們已經找到了我們的最低 是，我們要遍歷
再看看它的比較，對不對？
所以Ĵ，在這裡，是怎麼回事 等於I，這是0。
然後，如果陣列Ĵ再加上我，這 就是一個​​是下完了，一樣都不能少
比你目前的最低 值，要交換。
>> 所以，讓我們只說我們已經 有，像，2，5，1，8。
現在，我等於 0和j是等於0。
這就是我們的最低值。
如果陣列-j的加I--因此如果所述一個 這就是我們正在尋找在一前一後
大於前一， 這將成為最低。
>> 所以在這裡我們可以看到，5 是不遜色。
因此，這將不會是5。
我們看到，1小於2，對不對？
所以，現在我們知道，我們的最低是 將是0，1，2的指數值。
是嗎？
然後當你到這裡， 你可以交換正確的價值觀。
>> 所以，當你們剛剛有第j 之前，你是不是在看一
後。
你在看 相同的值，這
就是為什麼它只是沒有做任何事情。
這是否有意義給大家， 為什麼我們需要一個加1呢？
確定。
現在，讓我們只運行通過它來作 確認代碼的其餘部分是正確的。
這是為什麼發生？
啊，這是分就在這裡。
我們比較了錯誤的值。
哦，不。
>> 哦，是的，在這兒我們 交換了錯誤的值也是如此。
因為我們在看i和j。
這些都是那些我們被檢查。
事實上，我們希望交換的 至少，目前最低，
與任何一個外面。
正如你們所看到下跌 在這裡，我們有一個排序的數組。
這只是不得不做 事實，當
我們被檢查 值的我們相比，
我們不看正確的價值觀。
我們在看的同一個 在這裡，沒有實際交換它。
你要看看一個接一個 它，然後你可以交換。
所以，這是什麼樣的 前纏著我們的代碼。
而我在這裡所做的一切 調試器可以為你做
我只是做了它的 板，因為它更容易
看而不是試圖 可放大的調試器。
這是否有意義給大家？
酷。
>> 好的。
我們可以繼續談 漸近符號，這
是說的只是一種奇特的方式 所有這些各種各樣的運行時間。
所以我知道大衛在演講中， 在運行時感動。
他走遍了整個公式 如何計算的運行時。
關於無後顧之憂。
如果你真的很好奇 其工作原理，
隨時節後跟我說話。
我們可以穿行 公式在一起。
但是，所有你們要真 知道是n的平方超過2
是同樣的事情為N的平方。
因為最大數目， 該指數增長最。
所以我們的目的， 我們關心的
是巨大的數量也在不斷增長。
>> 那麼，什麼是最好的情況下， 選擇排序的運行時間？
如果你想有 遍歷列表
然後遍歷 該列表的其餘部分，
多少次都 你要大概，
在最壞的case--在 最好的情況下，sorry--跑過來嗎？
也許更好的問題是 要問，什麼是最壞的情況下
運行時選擇排序的。
聽眾：N的平方。
ANDI彭：這n值的平方，正確的。
因此，一個簡單的方法來認為這是喜歡， 任何時候你有兩個嵌套的for循環，
它會為n的平方。
因為不僅是你 通過再次運行，
你要回去 周圍，並通過它運行
裡面的每一個值一次。
因此，在這種情況下，你在行駛中N n次平方，這is--抱歉，
n次N，這等於N的平方。
>> 和排序也有點 在這個意義上獨特
它不如果這些關係 值已經在秩序。
它仍然會通過反正運行。
遠的不說，這是1，2，3，4。
不管它是否是在 命令，它仍然會通過跑
並且仍然檢查的最小值。
它會作出 檢查相同數量的
每一次，即使它 實際上並沒有碰任何東西。
>> 因此，在這樣的情況下，最好和最差 運行時實際上是等價的。
因此，預計運行時間 選擇排序的，
這是我們指定的符號 的θ，θ-，在這種情況下，
還將為n的平方。
所有這三個為N的平方。
是為什麼每個人都清楚 運行時間為n的平方？
>> 好的。
所以我只是要快速運行 通過對各種休息。
該算法 泡泡類別 - 記住，
這是第一個 大衛走過去的講座。
從本質上講，你一步 整個列表
你剛才swap--你 同時比較兩個。
而如果一個人的更大， 比你只是換他們。
因此，如果這些是更大的，你就掉。
我已經得到了官方的就在這裡。
>> 因此，讓我們只說你有8個，6個，4個，2。
你會比較8和6。
你需要交換它們。
您會比較8和4。
你需要交換它們。
如果您有交換8 2，改變他們。
因此，在這樣的意義上，你可以看到， 發揮出了相當長的時間週期，
怎麼樣值泡沫來 兩端，這就是為什麼我們叫它
冒泡排序。
>> 我們只想上運行再次通過 我們的二傳，而我們的第三關，
而我們的第四個階段。
從本質上講，冒泡排序只是運行 直到你不作任何更多的互換。
因此，在這個意義上，這僅僅是 一般偽它。
不用擔心，這些都將在網上。
我們沒有真正去了這一點。
>> 我們只是初始化一個計數器 從0開始的變量。
而我們通過整個數組迭代。
如果一個值is--如果這 值大於該值，
你要交換它們。
然後，你只是 要繼續下去。
而你要算。
而你只是要繼續做 這同時計數器的值大
大於0，這意味著 每次你要交換，
你知道你想要去 回去檢查一次。
你要繼續檢查，直到你知道 你不必換了。
>> 那麼，什麼是最好的和最差 情況下的運行時間冒泡排序？
這hint--實際上是不同的 從某種意義上選擇排序
這兩個答案是不一樣的。
想想會發生什麼 的情況下，如果它已經被排序。
想想什麼 如果它是會發生
在的情況下在它被排序。
你可以種運行 通過為什麼會發生的事情。
我給你們一樣，30 秒，想想。
>> 確定。
是否有人在猜測什麼 冒泡排序的最壞情況下的運行時間是？
是啊。
>> 聽眾：會是一樣，n次 ñ減1或類似的東西？
像，每次運行時， 它只是一樣，一個交換少
這不管是什麼。
>> ANDI彭：是啊，所以 你是完全正確的。
這是在這種情況下你 答案竟是更複雜
比我們需要給。
因此，這將run--我 要刪除這一切都在這裡。
是每個人都好？
我能抹去嗎？
確定。
你會到n運行 第一次時間，對吧？
他們正在經歷的運行 Ñ​​減去1秒的時間，對吧？
然後，你要保持 去，N礦2，等等。
大衛這樣做的講座，其中， 如果你加起來所有的值，
你得到的東西，是like-- yeah-- 超過2，這本質上只是減少
下降到n的平方。
你會得到一個 怪異的部分在裡面。
所以只要知道 第n總是平方
優先於分數。
因此在這種情況下，最壞的 運行時間為N的平方。
如果它是在降 順序，想想，你
不得不做出交換每一次。
>> 什麼是潛在的， 最好的情況下運行？
這麼說吧，如果列表已經 為了，你會在運行時？
>> 聽眾：N。
ANDI彭：這是N，正好。
為什麼是這N +
聽眾：因為你剛才 必須檢查每一次。
ANDI鵬：沒錯。
因此，在可能的最佳運行時， 如果此列表中已經
sorted--比方說，1，2，3，4--您 只想去實現它，你會檢查，
你會看到，哦，他們都做成。
我沒得換。
我完成了。
因此，在這種情況下，它僅僅局限於N 或步數，你只是
不得不檢查的第一個列表。
>> 及後，我們現在打 插入排序，其中，
該算法本質上是鴻溝 它變成一個排序和未排序的部分。
然後一個接一個， 未排序值
在其相應插 在列表的開頭位置。
>> 因此，例如，我們有一個 的3名單，5,2，6,4試。
我們知道，這是目前 未分類的，因為我們剛剛
開始尋找它。
我們來看看，我們知道， 第一個值進行排序，對吧？
如果你只關注一個數組 尺寸之一，你知道它的排序。
>> 於是我們知道， 其他四個都是無序。
我們通過和我們看到的價值。
讓我們回去。
見5的價值？
我們來看看它。
我們把它比作3。
我們知道，它是大於 3，讓我們知道，多數民眾贊成排序。
所以，現在我們知道，前兩個 進行排序和最後三個不是。
>> 我們來看看2。
我們首先檢查一下與5。
是小於5？
事實並非如此。
因此，我們必須繼續找下去。
然後檢查2關閉3。
是小於？
第
所以，你知道2必須插入 入前和3和5
都必須被推出。
6和4再次做到這一點。
我們只是保持檢查從本質上講， 在這裡我們只是檢查，檢查，檢查。
而直到它在正確的 樣的位置，我們只是
將其插入合適的位置， 這就是它的名字是從哪裡來的。
>> 所以，這僅僅是算法， 那種偽代碼本身，
關於我們如何實現 插入排序。
偽代碼是在這裡。
這一切都在網上。
不，如果你們有隱憂 試圖複製下來。
所以再次，相同的問題 - 是什麼 將是最好的和最差的運行時間
插入排序？
這是非常相似的最後一個問題。
我給你們一樣，30 秒想想這一點。
>> 確定有沒有人要 給我最糟糕的運行？
是啊。
>> 聽眾：N的平方。
>> ANDI彭：這n值的平方。
為什麼它Ñ平方？
>> 聽眾：因為在 相反的順序，你有
要經過n次N，其中is--
ANDI彭：是的，沒錯。
所以，同樣的事情在冒泡排序。
如果此列表中 降序排列，你
不得不先檢查一次。
然後每 額外的價值，你
將不得不對檢查 每一個值，對不對？
所以乾脆，你會做 正通時代另外N通，這
為n的平方。
那麼最好的情況？
是啊。
>> 聽眾：N減1，因為 第一個是已經平方。
>> ANDI彭：那麼，關閉。
其實答案ñ。
因為當第一個是 排序，也可以不actually--它
我們只是走運了，在 即例如，2
正好是最小的數目。
但是，這不會總是這種情況。
如果2已經排序的開始 但是你看，有一個1在這裡，
1將要碰撞。
而這將結束 最多被撞毀反正。
>> 因此，在最好的情況下， 它實際上只是要為n。
如果有1個，2個，3個， 4，5，6，7，8，你
經過運行 這整個列表一次
檢查，如果一切都很好看。
在其上運行大家清楚 選擇的時候呢？
我知道我經歷 這些真快。
但是，僅僅知道，如果你知道 一般概念，您應該不錯。
確定。
所以，我只是給你們也許一樣， 一分鐘談談你的鄰居
什麼都只是一些 的主要區別
與這些類型的排序。
我們一起去了很快。
聽眾：哦，好。
ANDI彭：是的。
確定。
酷，讓我們重新召集的一類。
確定。
所以，這是一種一 在這個意義上開放式的問題
這有很多他​​們的答案的。
我們將介紹一些他們的簡要介紹。
我只想讓你們 思考什麼區別
這三種類型的排序。
而且我聽說，也有很大 的問題 - 是什麼歸併排序呢？
大的問題，因為這是 我們正在覆蓋下一個。
>> 所以，歸併排序是 一個分類的功能
非常不同於其他種類。
正如你們可以see-- David是不是做演示
在那裡，他把所有的酷 看到如何合併的聲音
排序跑了一樣，無限 比其他兩種類型的快？
確定。
所以，這是因為合併 排序實現了鴻溝
而治之的概念，我們已經 談到了很多在課堂上。
在這個意義上，我們喜歡的工作 更聰明，而不是更辛苦，當你把
而治之的問題，並打破他們 下來，然後把它們放在一起，
美好的事物總是發生。
>> 這樣合併的方式 排序基本工作原理
是，它把一個 無序陣列中的一半。
然後它有陣列的兩半。
它只是排序那些兩半。
它只是保持在半分，在 一半，一半，直到萬事俱備
然後遞歸 把他們放在一起。
>> 這就是真正的抽象。
所以，這只是一個有點偽的。
這是否有意義的 它的運行方式？
因此，讓我們只說你有一個 n個元素的數組，對不對？
如果n小於2，可以退貨。
因為你知道，如果有 只有一件事，它必須被排序。
否則，你排序左前衛， 然後排序的右半​​部分，
然後合併。
>> 因此，雖然看起來很容易， 在現實中，思考它的
樣的困難。因為你喜歡， 嗯，這是運行的一種自身。
對嗎？
它本身運行。
因此，在這個意義上，大衛·感動 在遞歸類。
這是一個概念 我們將談論更多。
那就是這一點，這兩條線 在這裡，其實只是節目
告訴它運行本身 與不同的輸入。
因此，而不是與運行本身 n個元素的全部，
你可以把它分解成的 左半部和右半
然後再運行它。
>> 然後我們來看看它在視覺上， 因為我是一個視覺學習者。
它為我好。
所以，我們來看看一個可視化的例子在這裡。
>> 比方說，我們有一個數組，六 元素，3，5，2,6，4,1，不進行排序。
好吧，有很多這個頁面上。
所以，如果你們可以看看 這裡第一步驟中，3，5，2,6，4,1，
您可以在一半分裂它。
您有3個，5個，2，6,4，1。
你知道這些aren't--您 不知道他們正在排序或沒有，
所以你把它們分解，在上半年， 成兩半，一半，直至最後，
你只有一個元素。
而一個元素總是排序，對吧？
>> 因此，我們知道，3，5，2，4，6， 1，由本身，進行排序。
現在，我們可以把他們重新走到一起。
因此，我們知道的3,5。
我們把這些在一起。
我們知道這是排序。
2.仍然存在。
我們可以把4和6一起。
我們知道，多數民眾贊成排序， 所以我們這身打扮。
而1是存在的。
>> 然後你只要看看 這兩個半就在這裡。
你有3,5，2，2，3，5。
你可以只比較 開始的一切。
因為你知道，這是排序 你知道，多數民眾贊成排序。
所以，那麼你甚至沒有給 對比5，你只要比較一下3。
和2小於3，所以 你知道2必須走到底。
>> 同樣的事情在那邊。
1.必須在這裡。
然後，當你去把 這兩個值加在一起，
你知道，這是分類和 你知道這是排序。
於是在1和 圖2中，1是小於2。
這告訴你，1 應該在本月底
看也不看3或5。
然後是4，你可以 檢查，它會就在這裡。
你不必看5。
同樣的事情在6。
你知道6--它只是 並不需要研究。
>> 所以這樣一來，你是 只是拯救自己
很多步驟，當你比較。
你不必比較每 元素與其他元素。
你只是比較反對的人 你需要將它與比較。
所以這是一種抽象的概念。
不用擔心，如果它不是 相當擊中你的權利呢。
但是總體來說，這是 如何合併排序工作。
問題，簡單的問題， 之前，我繼續前進？
是啊。
>> 聽眾：所以你說，你拿 1，然後在4和6
並把他們進來。
所以不those--不 你看他們
作為單獨的元素，而不是整？
ANDI彭：是的。
所以發生了什麼 是，你基本上
正在創造一個全新的陣列。
所以，你知道，在這裡，我有 尺寸3的兩個數組，對不對？
所以，你知道，我的排序的數組 需要有六個要素。
所以，你只要創建一個 新的內存量。
所以，你是那種喜​​歡 被浪費的存儲器，
但是，這並不重要 因為它是如此之小。
所以，你看1 你看2。
而你知道，1小於2。
所以，你知道，1應該在 所有這些的開始。
>> 你甚至都不需要 看3和5。
所以，你知道1去那裡。
然後，你基本上砍掉1。
這是一樣，死了我們。
然後，我們只是有2個， 3，5，然後4和6。
然後你知道，你 比較4和2，
呵呵，2應該在那裡。
所以，你撲通2下來，你砍了下來。
所以，那麼你只需要3 和5中的4個和6個。
而你只是不斷砍它關閉 直到你把他們到數組中。
>> 聽眾：所以，你只是總是 比較[聽不清]？
>> ANDI鵬：沒錯。
因此，在這個意義上說，你是 只是相比較，從本質上講，
一個號碼對另一個號碼。
而且因為你知道 ，它的排序，
不必翻閱 所有的數值。
你只需要看看第一個。
然後你可以撲通 下來，因為你知道
他們屬於他們需要屬於。
是啊。
好問題。
>> 然後，如果哪 有點雄心勃勃，
隨意看看這段代碼。
這實際上是 物理實現
我們如何會寫歸併排序。
你可以看到，這是非常短的。
但背後的想法 這是相當複雜的。
所以，如果你覺得自己畫了這一點 在你的功課今晚，隨意。
>> 確定。
大衛也去了這個講座。
什麼是最好的情況下， 運行時，最壞的情況下運行時，
和合併排序的預計運行時間？
幾秒鐘思考。
這是相當困難的，但那種 直觀的，如果你仔細想想。
好的。
>> 聽眾：是最壞的情況的n log N +
ANDI鵬：沒錯。
為什麼說它是N日誌ñ。
>> 聽眾：是不是因為它 成為指數更快，
因此它就像一個函數 而不只是單純的為N
平方什麼？
ANDI鵬：沒錯。
這樣之所以 運行時在此為n日誌
n是因為 - 你是什麼人 在做所有這些步驟？
你只是砍了一半，對不對？
所以，當我們正在做的 日誌，所有它做
被分割的問題在一半， 成兩半，一半，在更半部。
而在這個意義上，可以種 對消除線性模型
我們一直在使用。
因為當你砍 事情的一半，這是一個記錄。
這只是數學 代表它的方式。
>> 然後終於，到了最後，你 只是讓通過一個最後一關
把所有的人都在秩序，對不對？
所以，如果你只需要 查一件事，那n值。
所以你是那種 乘兩者結合起來。
因此，這就像你已經得到了最終的 檢驗N-下來日誌的n這裡
在這裡。
如果你乘 他們，那是N日誌ñ。
>> 所以，最好的和最壞 情況和預期是所有N日誌N。
它也像另一個排序。
這就像選擇排序 在某種意義上說，它
不要緊，你的 列表，它只是會
做同樣的事情，每一次。
確定。
所以當你們可以看到，即使 我們已經走了through-- n中的種種
平方，這不是很有效。
而即使是這樣的n log n是 不是最有效的。
如果你們是好奇， 有某種機制
這是如此有效，以至於他們 幾乎是基本持平的運行時間。
>> 你有一些日誌ñ的。
你有一些loglogN個的。
我們不觸及他們 在這個類現在。
但是，如果你們是好奇， 隨意谷歌，什麼是
最有效的分類機制。
我不知道，有 一些很搞笑的人，
like--有一些真的 有趣的那些人做。
你想知道他們是如何 沒有想過這一點。
因此谷歌，如果你有一些空閒 時間上，都有些什麼有趣的方式
該people--以及 高效ways--人
之所以能夠實現排序。
確定。
而這裡只是一個方便的小圖。
我知道在座的各位，是競猜0之前， 會在你的房間可能是試圖
記住這一點。
所以這是很好的在那裡為你們。
但不要忘記，made--邏輯 為什麼這些數字正在發生。
如果你總是輸了，只是讓 確保你知道什麼是排序是。
你可以貫穿 它們在你的心中
弄清楚為什麼那些 答案是這些問題的答案。
>> 好的。
所以，我們要動 在最後，在搜索。
因為那些對你 誰看過處理器集，
搜索也是部分 這個星期的習題集。
你會被要求執行 兩種類型的搜索。
一個是線性搜索和 一個是一個二進制搜索。
>> 所以線性搜索是相當容易的。
你只是想搜索的元素 列表，看看你得到它。
你只需要遍歷。
如果它等於什麼， 你可以返回它，對嗎？
但是，一個我們最 興趣談論
是二進制搜索，右，這是 分而治之的機制，
大衛被證明在講座。
>> 還記得電話簿的例子 他不斷拉扯大，
一個那種他掙扎 有點過去的一年，
在那裡你把這個問題了一半， 一半，一半，一遍又一遍，
直到你找到你想要的？
而你已經得到了 那運行時也是如此。
你可以看到，它的 顯著更高效
比任何其他類型的搜索。
>> 所以我們會去的方式 實現的二進制搜索
是，如果我們有一個數組， 索引為0到6，7的元素，
我們可以看看在中間，right-- 很抱歉，如果我們的問題first--
如果我們要問的問題，請問 該陣列含有的7的元件，
顯然，是人類，並且具有 這樣一小陣，很容易讓我們
說是。
但方式來實現二進制 搜索將是尋找在中間。
>> 我們知道，指數3 中間，因為我們
知道有七個要素。
什麼7除以2？
你可以額外1砍掉。
你在中間得到了3。
所以為3數組等於7？
它是不是，對不對？
但是，我們可以做一對夫婦的檢查。
是3小於7或陣列 是3陣列大於7？
>> 我們知道，這是不到7。
因此，我們知道，哦，就必須 不會在左半部。
我們知道，它必須是 在右前衛，對不對？
因此，我們可以只砍掉一半的陣列。
我們甚至不有 看它了。
因為我們知道， 一半的problem--的
我們知道答案是 我們的問題的右半部分。
因此，我們只看現在。
>> 所以，現在我們來看看 中間還剩下些什麼。
該指數5。
我們再次做同樣的檢查 而且我們看到，它的體積更小。
因此，我們期待的是左邊。
然後我們看到檢查。
是在陣列值 索引4等於7？
是的。
因此，我們可以返回true，因為 我們發現在我們的列表中選擇值。
我是否通過去的方式 是否有意義給大家？
確定。
我給你們也許一樣， 三，四分鐘，以搞清楚
如何在偽代碼本。
>> 所以，想像一下，我問你寫 函數調用搜索（）的返回
一個值，布爾值， 這是真的還是false--類似，
如果你找到了真正的 值，如果你沒有假的。
然後你 在值傳遞你
在尋找到值， 是array--哦，我一定會把
在錯誤的地方。
確定。
不管怎樣，應該有 到過的值的右側。
然後INT n是數 在該數組元素。
你會如何去努力 偽代碼在這個問題？
我給你們喜歡 三分鐘的時間做到這一點。
不，我認為有only-- 是啊，有一個正確的在這裡。
聽眾：可以嗎？
ANDI彭：是啊，我給你。
是不是工作？
OK，涼。
>> 確定。
好球員，我們 要收服入。
確定。
因此，假設我們已經有了這個可愛的 小數組在它的n值。
我沒有畫線。
但是我們怎麼能去 嘗試寫這個？
有沒有人要 給我的第一行？
如果你想給我 第一行該偽代碼。
>> 聽眾：[聽不清]
聽眾：你想要 遍歷through--
聽眾：只為循環的另一個？
聽眾：──。
>> ANDI彭：所以這一塊是有點棘手。
想想about--你想 要繼續運行這個循環
一遍又一遍，直到什麼時候呢？
>> 聽眾：直到[聽不清] 值等於該值。
ANDI鵬：沒錯。
所以，你可以真正地寫 - 我們甚至可以把它簡化了。
我們可以寫一個while循環，對不對？
所以，你可以有loop-- 我們知道，這是一段時間。
但現在，我要去 說“循環” - 通過什麼？
環until--是什麼 我們結束條件？
我想我聽到了。
我聽到有人說了吧。
>> 聽眾：值等於中間。
ANDI彭：再說一遍。
聽眾：或者，直到 值要搜索
為等於中間值。
>> ANDI彭：如果有什麼是不是在那裡？
如果你正在尋找的價值 對於實際上不是在這陣？
聽眾：你返回1。
>> ANDI鵬：但是我們要 循環，直到如果我們有一個條件？
是啊。
>> 聽眾：直到有只有一個值？
ANDI彭：你可以循環 until--讓你知道，你是
將有一個最大值，對不對？
而你知道，你會 有一個最小值，對不對？
也因為，這東西 我忘了之前的說法，
這東西是 約二分查找關鍵
是你的數組已經排序。
因為沒有辦法做 這一點，如果他們只是隨機值。
你不知道，如果一個人的 比另一個大，對吧？
>> 所以，你知道你的最大和 您分鐘都在這裡，對不對？
如果你將要調整 你最大的您分鐘和mid--
就讓我們假設你的 中間值右這裡 -
你要基本 循環，直到你的最小值是
大致相同的最大，右，或 如果你的max是不一樣的分。
對嗎？
因為當發生這種情況，你知道， 你最終擊中了相同的值。
所以，你要循環，直到你分鐘 小於或等於用於：哎呀，
不小於或等於 around--最大的另一種方法是。
>> 這是否有意義？
我花了一些嘗試，以獲得這一權利。
但循環，直到你的最大值 基本上是差不多少
大於或等於您的最低，對不對？
當你知道這是 你已經收斂。
聽眾：當你將最大 值是小於最小？
ANDI彭：如果你保持 調整它，這
就是我們要 在做這個。
這是否有意義？
最小和最大只是 整數，我們可能
將要創建的保留 賽道上，我們正​​在尋找的。
因為數組存在 無論我們在做什麼的。
就像，我們沒有實際的物理 斬去陣列，對不對？
我們只是調整 我們正在尋找。
這是否有意義？
>> 聽眾：是的。
>> ANDI彭：OK。
所以，如果這對我們的循環中的條件， 我們需要什麼這個循環裡面？
什麼是我們將要想要做什麼？
所以，現在，我們已經有了 一個最大和最小，權，
可能產生在這裡的某個地方。
我們將可能希望 找一個中間的，對不對？
我們該如何為 能找到中間？
什麼是mathematical--
聽眾：最大加分除以2。
ANDI鵬：沒錯。
這是否有意義？
做你們明白為什麼我們 不只是use--為什麼我們這樣做
而不是做了2只除以n？
這是因為n是一個值 那將保持不變。
對嗎？
但是，當我們調整我們的最低和 最大值，他們將改變。
其結果，我們的中間 都不會改變太多。
所以這就是為什麼我們要 在這裡做的權利。
確定。
>> 然後，現在 我們發現our--耶。
>> 聽眾：只是一個快速的問題 - 當你說最大和最小，
在我們假設 它已經排序？
>> ANDI彭：是啊，這實際上是一個 先決條件二進制搜索，
你必須知道它​​的排序。
這就是為什麼排序，你寫你的 您的二進制搜索之前，習題集。
確定。
所以，現在我們知道我們的中點 是，你要什麼做的嗎？
>> 聽眾：我們想比較 即到另一個。
ANDI鵬：沒錯。
所以，你要比較 月中的價值，對不對？
而這是什麼告訴 我們，當我們比較？
什麼是我們想要做的之後？
>> 聽眾：如果該值越大 比中期，我們希望把它割下來。
ANDI鵬：沒錯。
因此，如果該值大 比中旬，我們
會想改變這些 最小和馬克塞斯，對不對？
我們需要什麼改變？
因此，如果我們知道價值的地方 在這裡，你有什麼，我們要改變？
我們要改變我們的 最小的是中端，對不對？
然後否則，如果它在這個 上半年，有什麼事我們要改變？
>> 聽眾：你最大的。
ANDI彭：是的。
然後，你只是去 保持循環，對不對？
因為現在，一次迭代後， 通過，你已經有了一個最大這裡。
然後你就可以重新計算中間。
然後你就可以比較。
而你要堅持下去 直到分鐘和馬克塞斯
已經基本收斂。
而且，當你知道這是 你打它的結束。
而無論你已經找到了 或者你有沒有在這一點上。
>> 這是否有意義給大家？
確定。
這是非常重要的， 因為你有
在您的代碼今晚這樣寫。
但是你們有一個相當不錯的 什麼，你應該做的意義，
這是很好的。
確定。
所以，我們已經得到了大約七 離開分鐘一節。
所以，我們要談談 這pset的，我們會做。
因此的pset分為兩半。
上半年涉及 實施發現
在你寫一個線性搜索，一 二進制搜索，和一個排序算法。
>> 因此，這是第一個 一次在PSET哪裡
我們會給予你們什麼所謂 分配代碼，這是代碼
我們已經預先寫好， 只是留下了一些棋子落
為你完成寫作。
所以你們這些傢伙，當你看這個 代碼中，你可能會真是嚇壞了。
如果你只是想，啊，我 不知道這是什麼在做，
我不知道一樣，這似乎 這麼複雜，啊，放鬆。
這是確定的。
閱讀規格。
該規範將解釋你到底 什麼所有這些方案都在做。
>> 例如，generate.c是一個程序 這會是你的pset中。
你實際上並沒有去觸摸它，但 你應該明白它在做什麼。
而generate.c，所有它做的是 或者產生隨機數
或者你可以給它一個種子，像 預先安排的號碼，它需要，
它產生更多的數字。
因此，有一種特定的方式來 實施generate.c其中
你可以做一串數字 為您測試您的其他方法上。
>> 所以，如果你想為 例如，測試你的發現，
你想運行generate.c， 生成一串數字，
然後運行你的助手功能。
你的助手功能就是你 實際的物理寫代碼。
並認為傭工作為庫文件 你寫的那些發現正在呼叫。
所以在helpers.c，你會 做搜索和排序。
>> 然後，你要基本上 只是把它們放在一起。
該規範將告訴你如何 把在命令行上。
你就可以測試是否 不是你的排序和搜索工作。
酷。
有沒有人已經開始， 遇到問題或疑問
他們現在所擁有的這個嗎？
確定。
>> 聽眾：等待。
我有一個問題。
>> ANDI彭：是的。
>> 聽眾：所以我就開始做 在helpers.c線性搜索
它並沒有真正的工作。
但後​​來，我發現我們只是 要刪除它，做二進制搜索。
因此，它的問題，如果它不能正常工作？
>> ANDI彭：簡短的答案是否定的。
但由於我們是不是 -
聽眾：但是，沒有一個人的 其實檢查。
ANDI彭：我們從來沒有 要看到這一點。
但是，你可能想使 確保你的搜索工作。
因為如果你的線性 搜索無法正常工作，
那麼機會是你的二進制 搜索是不會正常工作。
因為你也有類似的 邏輯在兩人面前。
不，這其實並不重要。
所以唯一的，你轉 在有排序和二進制搜索。
是啊。
>> 而且，很多孩子們 嘗試編譯helpers.c。
你沒有真正允許 要做到這一點，因為helpers.c
不具有的主要功能。
所以，你只應該 是實際編制
產生和發現，因為找不到電話 helpers.c並在它的職能。
這樣就使得調試 一個痛苦的對接。
但是，這就是我們要做的。
聽眾：你剛才做的所有，對不對？
ANDI彭：你可以 讓所有的嗯，是的。
確定。
所以這是它在什麼條件 pset的要求你都做。
如果您有任何問題，請隨時 免費區之後問我。
我會在這裡一樣，20分鐘。
>> 和是的，處理器集的 真的沒有那麼糟糕。
你們應該沒問題。
這些，只是遵循的指導方針。
一種有意識，從邏輯上講，是什麼 應該發生，你會沒事的。
不要太害怕。
有很多的代碼 已經寫在那裡。
不要太害怕，如果你不 明白了這一切手段。
如果這是一個很大，這是完全罰款。
而來到辦公時間。
我們會幫你看看。
>> 聽眾：用多餘的 功能，我們看這些嗎？
>> ANDI彭：是的，這些都是在代碼中。
在遊戲中的15，一半的 它已經為你寫的。
因此，這些功能 已經在代碼中。
是的。
好的。
那麼，最好的運氣。
這是一個噁心的一天。
所以希望你們不要覺得太 不好呆在裡面和編碼。