[음악 재생] 

ANDI 펭 : 섹션의 주 3에 오신 것을 환영합니다. 모든 주셔서 감사합니다, 너희들, 이 이전 시작 시간 오늘. 우리는 좋은, 조금있어 친밀한 그룹 오늘. 그래서 잘하면 우리는에 도착합니다 마무리, 아마도 초기, 조금 일찍 오늘. 이렇게 빨리, 좀 의제 오늘 발표. 우리가 시작하기 전에, 우리는있어 그냥 갈 몇 가지 간단한 물류 문제, PSET 질문, 브리핑, 그런 것들. 그리고 우리는에 바로 뛰어들 것이다. 우리는에 GDB라는 디버거를 사용합니다 우리의 코드를, 정체를 폭로 시작하는 다윗 다른 날 강의에서 설명했다. 우리는 종류의 네 가지 유형을 통해 이동합니다. 우리는 꽤 빨리 그들을 갈거야 그들은 꽤 많이있어 때문이다. 하지만 알고있는 모든 슬라이드와 소스 코드는 항상 온라인 상태입니다. 그래서에, 당신의 열람에 주시기 돌아가서 그를보십시오. 

우리는 통과합니다 점근 표기법, 어떤 단지 멋진 방법입니다 말하는 "런타임을" 우리는 큰 O를,이 곳에있는 다윗은 강의에서 설명했다. 그리고 우리는 또한 오메가를 가지고있는 하한 런타임이다. 그리고 우리는 좀 더 얘기하자 심층 어떻게 그 일에. 그리고 마지막으로, 우리는 이진 검색을 통해 갈거야 때문에 이미 당신의 많은 당신의 psets를 흘끗 아마 알고 그게 당신의 PSET에서의 문제이다. 그래서 당신은 모든 행복 할 것 우리는이 오늘 다룰 것이다. 

그리고 마지막으로, 당 섹션 피드백, 나는 실제로 약 15 분 왼쪽 말은 그냥 이동 pset3의 물류, 질문, 아마 인도의 비트, 만약에 당신, 우리가 프로그래밍을 시작하기 전에. 그럼 통해 얻을 해보자 꽤 빨리 재료. 그리고 우리는 약간의 시간을 보낼 수 있습니다 PSET에 대한 더 많은 질문을 복용. 그래. 

신속, 그래서 몇 가지 우리는 이전에 발표 오늘 시작합니다. 첫째, 만들기에 오신 것을 환영합니다 당신의 Pset의 두 통해. 나는 your-- 그래,하자의에보고했다 그 하나 박수를 얻을. 사실, 난, 정말로 정말 감동. 나는 너희들의 첫 번째 PSET을 등급 지난 주와 너희들은 놀라운했다. 

스타일 포인트에 있었다 몇 가지 의견 외에. 당신이 항상있어 확인 코드를 주석. 그러나 당신의 Pset 점에 있었다. 그리고 그것을 유지. 그리고 그것은에 학년을위한 좋은 너희들두고있는 것을 볼 수 당신의 스타일에 많은 노력 코드 및 설계 당신이 볼 수 있도록 우리는하고 싶은 것을. 그래서 난 내 감사를 따라 전달 해요 조교의 나머지 부분에 대한. 

그러나이있다 몇 브리핑 질문 난 그냥 가서 할 모두 내 인생을 만들 것 다른 많은 조교는 '좀 더 쉽게 살고있다. 첫째, 내가 발견 한이 과거는 당신의 얼마나 많은 week-- 에 check50를 실행 한 당신 전에 코드를 제출? 그래. 그래서 모두가 check50 일을해야한다, 실제로 우리 secret--을 이유는 - 우리의 정확성의 일환으로 check50를 실행 코드를 테스트하기위한 스크립트. 코드가 실패한다면 check50, 모든 가능성에, 아마 것 뿐만 아니라 우리의 검사를 실패합니다. 때로는 사람 정답이있다. 의처럼, 욕심, 일부 당신은 바로 번호를 가지고, 당신은 몇 가지 여분의 물건을 인쇄 할 수 있습니다. 그리고 그 여분의 물건 실제로 검사를 실패 컴퓨터가 없기 때문에 정말이 찾고 있는지 알고있다. 그리고 그것은 단지를 통해 실행됩니다 당신의 출력을하지 않는 것을 볼 수 우리는 대답을 기대 일치 , 그리고 그것이 잘못 표시합니다. 

그리고 나는 일어난 것을 알고있다 귀하의 경우 몇몇이 주. 그래서 나는 다시 수동으로 갔다 모든 사람의 코드를 재 채점. 하지만 미래에는, 있는지 확인하시기 바랍니다하십시오 당신은 실행중인 것을 코드 50를 확인하십시오. 그것은 TA에 대한 고통 가지이기 때문에 regrade 수동으로 돌아가서해야 할 모든마다 하나의 PSET 하나의 작은 놓친 예. 그래서 나는 어떤 점을 고려하지 않았다. 나는 어쩌면 벗고 생각 하나 또는 디자인을위한 두 가지. 하지만 미래에는, 경우 당신은 check50 실패하고 포인트는 이동합니다 정확성에 대한 끕니다. 

또한,의 Pset은 정오에서 금요일 때문에. 나는 7 분 있다고 생각 우리는 당신을 줄 늦게 유예 기간. 하버드 시간당, 그들은 허용하고 칠분 늦은 모든 것에를합니다. 그래서 여기에 예일 대학에서, 우리는거야 뿐만 아니라 그 준수합니다. 그러나 꽤 많은, 12시 7분에서, 당신의 PSET가 아닌 경우 그것은 늦게 표시 될 것입니다. 반면 있도록 그리고 그것은 표시됩니다 늦게, TA-- 내가 해요 여전히 psets를 채점 할 것. 그래서 당신은 아직 등급이 표시가 나타납니다. 그러나,에 알고 학기말, 모든 말의 Pset는 것입니다 자동으로 컴퓨터에 의해 제로. 

우리는 두 가지 이유에 대해이 작업을 수행합니다. 하나, 때로는 우리가 얻을 학장의 변명처럼, 면제, 나중에에 아직 모르는. 그래서 우리는 우리가 채점하고 있는지 확인하려면 다만 경우에 모든 것을, 같은, 내가 해요 학장의 변명이 없습니다. 그리고 둘째로,에 계속 마음, 당신은 아직 할 수 하나 PSET 드롭 그 전체 범위의 점을 가지고있다. 그래서 우리는 학년에 좋아 당신의 Pset의 모든 단지 스코프의를 확인 것과 거기 당신은 그들을 시도하고있다. 이 늦었 그래서 경우에도, 당신은 여전히​​거야 범위 포인트를 신용을 얻을, 나는 생각한다. 

이야기가 너무 도덕적, 확인 반드시 당신의 Pset에 시간에 있습니다. 그들이 적시에 없으면 그것은 큰 아니라고 알고있다. 그래, 난에 이동하기 전에, 사람이 있는가 PSET 피드백에 관한 질문? 그래. 

청중 : 당신은 우리 말 하였습니까 psets를 중 하나를 드롭 할 수 있습니까? 

ANDI 펭 : 네. 그래서 아홉의 Pset 전반적인있다 학기의 과정을 통해. 그리고 당신은 범위가있는 경우 points-- 그래서 범위는, 그냥 꽤 많은, 당신이 시도 문제는, 당신은 시간에 가하고 있습니다 당신은 당신이되었음을 보여주고있다 증명 당신은 스펙을 읽었습니다. 즉 거의 범위입니다. 그리고 당신은 만족하는 경우 범위 포인트, 우리 가장 낮은 드롭 수 전체 범위 중 하나. 그래서에 당신의 이점에있어 완료하고 모든 PSET을 시도합니다. 

심지어 upload-- 없음의 경우 그들은 그들 모두를 업로드, 작동합니다. 그리고 우리가 희망 할 수있을 것이다 당신에게 그 포인트의 일부를 다시 제공합니다. 쿨. 다른 질문? 좋아요. 

둘째, 사무실은 몇 끝도 근무 시간에 대한 빠른 노트. 그래서 일단, 초기 주에서 온다. 아무도에서 이제까지 없다 월요일 근무 시간. Christabel는 온 근무 시간 지난 밤. 그래, Christabel. 그리고 우리는 사무실에서 무엇을했을까요 시간 지난 밤, Christabel? 

청중 : 우리는 아이스크림을했다. 

ANDI 펭이 : 그래서 그건 바로, 우리가했다 근무 시간에 아이스크림 지난 밤. 나는 것을 약속 할 수는 없지만 우리는 근무 시간에 아이스크림을해야합니다 매주, 난 당신을 약속 할 수있는 상당히있을 것입니다 TA 비율이 더 나은 학생. 합법적 마찬가지로 3-1 같아요. 와 그 대비 반면 목요일, 당신은 약 150있어 정말 아이들없이 아이스크림을 강조했다. 그리고 그것은 단지 사람을위한 생산하지 않습니다. 이야기의 교훈은 그래서 일찍 와서 근무 시간과 좋은 일에 발생합니다. 

또한, 질문을 할 준비가되어 있습니다. 당신은 알아? 에 관계없이 어떤 조교, 나는 말 한 생각, 우리는 몇 학생을지고있어 10시 50분 같은, 목요일에 와서 사람들 사양을 읽은하지 나에게 도움이되고 싶어, 내가 도움이됩니다. 불행하게도 그 시점에서, 거기에 별로 우리가 당신을 도와 줄 수 있습니다. 그래서 초기에 주에 오시기 바랍니다. 근무 시간에 일찍 가자. 질문을 할 준비가되어 있습니다. 로, 반드시 확인 학생, 어디 그렇게 그해야 조교는 함께 여러분을 안내 할 수 있습니다 무엇 근무 시간 인 해야에 할당 될 수있다. 

둘째, 그래서 나는 교수를 알고 시험으로 우리를 놀라게하고 싶다. 나는 교수들 있었다 요, 같은 방법에 의해, 그 중간을 기억 당신은 다음 주 월요일있다. 그래, 그 중간에 대해 알고하지 않았다. 그래서 나는 될거야 TA 그것은 당신에게 모든 퀴즈를 생각 나게한다 당신이 알고 있기 때문 0--, 우리는 CS이야. 이제 우리가 한 배열을했는지, 당신은 얻을 이 퀴즈 0 왜, 어, 1 퀴즈하지? 그래. 아, 그 하나에 약간의 싱그레 웃음을 얻었다. 그래. 

그래서 퀴즈 0 경우 10월 14일 될 것입니다 당신은 월요일 수요일 부분에있어 10 월 15 번째가에 있다면 화요일 - 목요일 섹션. 이 적용되지 않습니다 하버드에서 당신의 그 난 당신이 모든 일 거라 생각 who-- 14 일 당신의 퀴즈를 복용. 

그래서 그래, 다음 주, 경우 다윗은, 강의, 간다 그래, 그것에 대해 너무 퀴즈 다음 주에, 당신의 모든 때문에 충격을하지 않습니다 당신은 절에 와서 당신은 알고 당신의 퀴즈 0 2 주입니다. 그리고 우리는 검토를해야합니다 세션과 모든 것을. 대한 그래서 걱정 없다 그것을 위해 깜짝 놀라게된다. 질문은 질문 before-- 모든 관련 물류 문제에서, 등급, 근무 시간, 섹션? 그래. 

청중 : 퀴즈가 그래서 강연이 될 것? 

ANDI 펭 : 네. 퀴즈 그래서, 나는 생각한다, 60 그 시간 슬롯에 할당 분 당신은 걸릴거야 강당에서. 그래서 올 필요가 없습니다 임의 오후 7 등,에. 전부다 괜찮아. 그래. 쿨. 

괜찮아. 그래서 우리는 갈거야 당신에게 개념을 소개 다윗이 종류 이미이 이번 주 이 지난 주 강의에 감동. 그것은 GDB라고. 어떻게 당신의 많은에있는 동안 귀하의 Pset를 작성하는 과정, 라는 큰 버튼을 발견했습니다 당신의 IDE의 상단에 "디버그"? 그래. 그래서 지금 우리가 실제로 발굴하는거야 어떻게 그 버튼의 신비 실제로 않습니다. 그리고 나는, 당신을 보장 아름다운, 아름다운 것. 

지금까지 내가 생각까지 그래서 두 가지가있었습니다 학생들은 일반적으로왔다 psets를 디버깅 할 때 일. 하나, 그들 중 하나에 추가 의 printf () - 그래서 모든 몇 줄, 그들은의 printf ()에 추가 - 오,이 변수는 무엇인가? 아,이 변수는 무엇입니까들을 당장 당신은 종류의 진행을 참조 코드의 그것을 실행으로. 또는 아이가하는 두 번째 방법은 그들은 단지 전체를 작성하는 것이 다음 마지막에 다음과 같이 이동합니다. 희망이 작동합니다. 나는 당신을 보장, GDB는 더 낫다 그 방법 중보다. 그래. 그래서 이것은 당신의 새로운 가장 친한 친구가 될 것입니다. 그것은 아름다운 일이기 때문에 그 시각 모두 표시 어떤 코드가하고있다 특정 시점에서 뿐만 아니라 어떤 모두 같은 변수는 운반하는, 그 값이 무엇인지 등, 특정 시점에서. 그리고 이러한 방법으로, 당신은 정말 할 수 코드에서 중단 점을 설정합니다. 당신은 라인으로 라인을 통해 실행할 수 있습니다. 그리고 GDB는 단지에 대한 것 당신은, 당신을 위해 표시 무엇 모든 변수 그들은 무엇을하고 있습니다, 어떤 코드에서 일어나는. 이러한 방식으로,이야 너무 쉽게 볼 수 있습니다 무슨 일이 printf의-ING 대신에 무슨 일이 일어나고 또는 명령문을 작성합니다. 

그래서 우리는 이번의 예를 할 수 있습니다. 그래서이 조금 추상적 인 것 같습니다. 걱정, 우리는 예를하지 않는다 할 것이다. 그래서 본질적으로, 세 가지 가장 큰, 당신이 GDB에 필요 기능을 가장 많이 사용 다음으로, 이상 단계입니다, 버튼으로 단계. 나는 향하기거야 이 사실은, 지금. 

그래서 너희들 모두는 것을 알 수 있습니다 또는 나는 약간 확대해야합니까? 다시, 당신은 그것을 볼 수 있습니까? 나는 확대해야 하는가? 그냥 조금? 그래 좋아. 우리는 거기에 갈. 그래. 

그래서 나는 나의 여기,이 욕심에 대한 구현입니다. 그리고 너희들을 많이 썼다 그 form-- while 루프에 욕심 할 수있는 완벽하게 허용되는 방법입니다 단순히를하는 것입니다 수있는 또 다른 방법을 그건 ... 모듈에 분할. 당신이 가질 수 있기 때문에 당신의 값 다음은 나머지를 가지고있다. 그리고 당신은 할 수 있습니다 모두 함께 추가 할 수 있습니다. 내가 뭘하는지의 논리를합니까 여기에 모든 사람에게 이해, 우리가 시작하기 전에? 종류의? 쿨. 좋아요. 그것은 꽤 섹시한 조각입니다 코드, 나는 말할 것입니다. 마찬가지로 나는 다윗에 말했다, 잠시 후, 강의, 모든 코드를보고 시작합니다 아름다운 무언가로. 그리고 때때로 당신은 아름다운 볼 때 코드는, 그러한 훌륭한 느낌. 

그래서 그러나,이 코드는 매우 인 반면 아름다운, 제대로 작동하지 않습니다. 그럼이에 check50을 실행 할 수 있습니다. 50 20-- OOP를 확인합니다. 2? 그 pset2인가? 그래. 아, PSET1. 그래. 그래서 우리는 check50를 실행합니다. 

그리고 너희들은 여기에서 볼 수 있듯이, 이 경우의 몇 가지를 실패합니다. 그리고에서 당신의 일부에 대한 문제 세트를 수행하는 과정, 아, 왜 작동하지 않는처럼 당신이있어. 왜 일부 작동 값이 아닌 다른 사람을 위해? 음, GDB는 당신의 그림을 도움이 될 것입니다 왜 그 입력이 작동되지 않았다. 

그래. 그럼, 중 하나를 보자 내가 check50에 실패했다 확인 0.41의 입력 값이었다. 정답 있도록 당신이 점점되어야한다 4. 하지만 그 대신 나는 밖으로 인쇄하고 무엇을 부정확 3 N이다. 그래서 그냥, 그냥 수동으로 실행할 수 check50가 작동하는지 확인하십시오. 의는 ./greedy하자. 아차, 내가 욕심 확인해야합니다. 우리는 거기에 갈. 지금 ./greedy. 

얼마나 빚지고있다? 이제 0.41을하자. 그리고 네, 우리는 여기에서 볼 그것은 3 출력 있다고 때 정답, 사실, (4)를해야한다. 그럼 GDB를 입력 할 수 있도록 우리 방법을 참조 이 문제를 해결에 대한 갈 수 있습니다. 

첫 번째 단계 그래서 항상 코드를 디버깅 중단 점을 설정하는 것입니다, 또는 점하는 당신 컴퓨터 나 원하는 디버거는보고 시작합니다. 당신이 경우에 따라서 정말 문제가 무엇인지, 일반적으로, 전형적인 것은 우리가 원하는 이렇게 주에 우리의 중단 점을 설정하는 것입니다. 그래서 너희들이 볼 수있는 경우 바로 빨간 버튼, 네, 그 날이 설정되었다 주요 기능에 브레이크 포인트. 나는 그것을 클릭합니다. 

그리고 내 디버그 버튼까지 갈 수 있습니다. 그 버튼을 누르십시오. 내가 할 수있는 경우에 저 밖으로 다시 확대하자. 우리는 거기에 갈. 그래서 우리는 여기에, 오른쪽의 패널이 있습니다. 나는 뒤에, 사람을 미안 해요, 당신 정말 정말 잘 볼 수 없습니다. 그러나 본질적으로, 모든 이 오른쪽 패널하고있다 모두 강조의 트랙을 유지하고있다 코드의 라인 라인, 컴퓨터가 현재 실행되고 있는지, 뿐만 아니라 당신의 모든 변수로 여기로. 

그래서 당신은 센트, 동전, N있어, 모든 다른 일에 선언 이 지점에서. 걱정은, 때문에 우리는 실제로 없다 아직 변수로 초기화. 컴퓨터에 따라서 당신의 컴퓨터는 단지 보는 것, 오, 32767는 마지막으로 사용 된 기능이었다 내 컴퓨터에서 해당 메모리 공간. 센트가 현재 어디에 그리고 그입니다. 하지만 한번 당신은 코드를 실행하지 이 초기화 될 것이다. 

그럼으로, 선을 통해 가자 라인, 어떻게 여기에 것입니다. 그래. 여기되도록 아르 세 난 그냥 설명 버튼. 당신은, 재생 또는 실행 기능이 버튼을, 당신은 버튼을 통해 단계를 당신은 또한 버튼으로 단계가 있습니다. 그리고 본질적으로, 세 가지의 그들은 당신의 코드를 통해 이동 다른 일을. 

그래서 일반적으로 디버깅 할 때, 우리가 플레이를 치고 싶지 않아, 재생 그냥 실행으로 인해 그것의 끝 코드. 그리고 당신은 실제로하지 않습니다 알고있는 문제 여러 중단 점을 설정하지 않은 경우입니다. 여러 브레이크 포인트를 설정하면, 그냥 자동 것 한 중단 점에서 실행, 다음에, 다음에. 그러나이 경우 우리는했습니다 단지 하나, 우리 때문에 우리의 방식으로 작동 할 위에서 아래로 아래에서. 그래서 우리는 그 버튼을 무시하는거야 지금이 프로그램의 목적. 

기능을 통해 단계 그러니 모든 단일 회선을 통해 단계 당신을 알려줍니다 무엇을 컴퓨터가하고있다. 기능에 단계 간다 실제 기능에 그 코드의 당신의 라인에 있습니다. 그래서 예를 들어, printf와 같은 (), 맞아, 기능인가? 나는 육체적으로 단계 원한다면 의 printf () 함수로, 사실의 조각으로 갈 것 의 printf ()가 작성되고 참조 된 코드 무슨 일이 일어나고. 

그러나 일반적으로, 우리는 가정 우리는 당신을 줄 코드가 작동합니다. 우리는 ()가 작동 중이의 printf를 가정합니다. 우리의 getInt ()가 작동하고 있다고 가정합니다. 그래서 필요에가 없습니다 이러한 기능으로 단계. 하지만 기능이 있다면 당신은 자신을 작성하는 것이 당신은 확인하려는 무슨 일이 일어나고 있는지 알아, 당신은 단계로 할 것 그 기능에. 

그래서 지금 우리는 단지거야 이 코드 조각을 통해 진행한다. 그래서 보자. 아, 인쇄, "오 하이, 방법 많은 변화가 빚진? " 우리는 상관하지 않습니다. 우리는이 일 것을 알고, 그래서 우리는 그 위에 단계. 

그래서 N, 우리의 플로트 인 그 우리는 initialized--했습니다 또는 declared-- 상단까지, 우리는 지금이야 GetFloat에 그 같게 (). 그래서 그 이상의 단계 수 있습니다. 그리고 우리는에서 참조 바닥 여기서, 프로그램 값 입력에 나 메시지를 표시합니다. 그래서 입력을의 우리가 원하는 값을 보자 0.41이다, 여기에 테스트합니다. 좋아요. 

그래서 지금 N-- 너희들은 참조 할 여기에, bottom-- 그것을이다 stored-- 우리 때문에 아직 반올림하지 않은, 그건 이 같은 거대한에 저장 0.4099999996이다 플로트, 충분히 가까이있는 우리의 목적, ​​지금, 0.41. 그리고 우리는 나중에로 볼 수 있습니다 우리 프로그램을 통해 스테핑 계속 여기 후, N은이되었다 둥근 센트 (41)이되었다. 좋아요. 그래서 우리는 우리의 라운딩의 작업 것을 알고있다. 우리는 우리가있는 것을 알고있다 센트의 정확한 수, 그래서 우리는 그건 알고 정말 문제. 

그래서 우리는 스테핑 계속 이 프로그램에. 우리는 여기. 그리고이 코드 줄 후, 우리 우리가 얼마나 많은 분기 알고 있어야합니다. 우리는 이상의 단계. 그리고 당신은 우리가, 사실, 하나를해야합니까 참조 분기 우리가 25을 차감 한 때문에 (41) 우리의 초기 값에서. 그리고 우리는 우리의 센트 (16) 왼쪽 있습니다. 

모든 사람들이 어떻게 이해합니까 이 프로그램은 단계별된다 왜 센트는 지금 (16)이되었다 왜, 지금, 동전은 1되고있다? 모든 사람이 그 논리를 다음인가? 쿨. ,이 점의 수 있도록 프로그램의 작업, 오른쪽? 우리는 정확하고있어 알고 우리는 그것을 원하는 것을. 그리고 우리는 실제로하지 않았다 오, 인쇄 할 수 있고, 무엇을 이 시점에서 센트이며, 이 시점에서 동전 것입니다. 

우리는 프로그램을 통해 지속될. 이상의 단계. 쿨. 우리는 센트를 통해 이동합니다. 좋아요. 우리는 가지고 있다고 볼 한 푼에 대한 $ 0.10 끕니다. 그리고 지금 우리는 두 개의 동전을 가지고있다. 맞습니다. 

우리는 동전 가서 우리가 참조 우리는 센트 이상 남았으니. 흠, 그게 이상하다. 여기에 프로그램에서까지, 나는 생각했다 내 동전을 차감 한 것으로. 아마도 난 그냥이 아니었다 그 라인 오른쪽을하고. 그리고 슬프게도, 당신은 볼 수 있습니다 여기, 우리가 알고 있기 때문에 우리는 스테핑됩니다 라인 (32, 33)을 통해, 그 곳에 우리의 프로그램 잘못 변수를 실행했다. 그래서 우리는보고 오, 볼 수 있습니다, 여기 센트를 뺀거야, 하지만 사실이 아니에요 내 코인 값에 추가. 나는 센트에 추가 해요. 그리고 난에 추가하지 않으 센트, 나는 동전에 추가 할. 그래서 우리는 동전에 있음을 변경하는 경우, 우리는 작업 프로그램을 가지고있다. 나는 check50를 실행할 수 있습니다. 당신은 GDB 바로 나갈 수 있습니다 여기에 다시 check50를 실행합니다. 난 그냥이 작업을 수행 할 수 있습니다. 나는 욕심 확인해야합니다. 0.41. 그리고 여기, 그것은 인쇄의 정답 아웃. 

너희들이 볼 수 있도록, GDB 정말 강력한 도구입니다 우리가 너무 많은 코드가있을 때를위한 에 가서 많은 변수 그것으로, 우리를 위해 어려운 것을 인간의 트랙을 유지합니다. GDB에서 컴퓨터, 디버거는 능력을 갖는다 모든 것을 추적 할 수 있습니다. 아마 Visionaire에서, 너희들, 알고 일부 분할 오류를 칠 수도 당신이 실행중인 때문에 배열의 경계 밖으로. 시저의 예에서, 그건 정확히 내가 여기서 무엇을 구현했습니다. 

그래서 확인하는 것을 잊었다 무슨 일이 일어날 것이라고 나는 두 개의 명령 줄 인수를하지 않았다. 난 그냥 체크에 넣어하지 않았다. 내가 Debug--을 실행하면 그래서 나는 설정 내 브레이크 포인트가 오른쪽으로. 나는 디버그를 실행합니다. 

그래. 그래. 그래서 실제로, GDB는했는데 가 나에게 말했다 가지고 이 세그먼트 오류였다. 나는 무슨 일이 있었는지 모른다 바로 거기에,하지만 난 그것을 실행했을 때 그것은 작동했다. 당신은을 통해 코드 라인을 실행할 때와 GDB는 갑자기, 당신을 종료 할 수 가서 빨간색 오류가 무엇인지 봐. 그것은,이 봐, 당신을 말해주지 세그먼트 오류를​​했다, 이는 당신이 접근을 시도한다는 것을 의미 존재하지 않는 배열의 공간. 그래. 

다음 문제에 따라서 이번 주를 설정, 너희들 아마 많이있을 것이다 변수는 주위에 떠있는. 당신은 확실히 될 수 없습니다하는지 그들 모두는 특정 시점에서 의미한다. 그래서 GDB는 정말 파악에 도움이 될 것입니다 그들은 모두 같게하는지 알아 시각적 것을 볼 수있는. 사람이 방법에 혼란 그 중 하나가 작동했다? 쿨. 괜찮아. 그래서 그 후, 우리는 바로 다이빙 것 에 서로 다른 네 가지입니다 이번 주에 대한 종류의 유형. 어떻게 많은 먼저 모두, 우리가 시작하기 전에, pset3의 전체 사양을 읽고? 그래. 나는 너희들의 자랑 스럽습니다. 즉, 클래스의 절반처럼하는 지난 번보다 훨씬 더 많은입니다. 

그래서, 좋은 때 때문에 우리는 콘텐츠에 대해 이야기 lecture-- 또는 미안에, section--에서 내가 좋아하는 그 많은 관련합니다 다시 PSET가 무엇인지에 당신이 원하는 방법 당신의 PSET에 그를 구현한다. 당신이 가지고 온다면 사양을 읽고, 그것을거야 당신이 이해하기 훨씬 쉽게 할 수 내가 말할 때 무슨 말인지, 헤이 오, 정말이 될 수 있습니다 이런 종류를 구현하는 좋은 장소. 읽고있는 당신의 그것들을 따라서 당신의 PSET의 일환으로, 알고 SPEC, 당신이해야 할거야 종류의 유형을 작성합니다. 그래서 이것은 매우 도움이 될 수 있습니다 당신의 많은 오늘. 

그래서 우리는 함께 시작합니다, 본질적으로, 가장 간단한 유형 의 종류, 선택 정렬. 의 일반적인 알고리즘 우리는 이것에 대해 가고 싶어하는 방법 is-- 다윗은 모든 이들 겪었 강의, 그래서 나는 빨리 따라 이동합니다 here-- 당신은, 본질적으로 값의 배열을 갖는다. 그리고 당신은 찾을 수 작은 정렬되지 않은 값 당신은 그 값을 교환 첫 번째 정렬되지 않은 값입니다. 그리고 당신은 계속 반복 목록의 나머지. 

그리고 여기에 시각적 인 설명이다 그래도 문제가 해결하는 방법의. 우리가 있었던 경우에 따라서 예를 들어, 시작 다섯 가지 요소의 배열 인덱스 0 내지 4, 3, 5, 2, 6, 4 값 그래서 지금 array--에 배치, 우리는 단지 가정거야 그들은 모두 정렬되지 않은를 걸 우리가 다른 테스트하지 않았기 때문에. 

어떻게 선택 종류의 것 작업은 처음 것입니다 전체를 통해 실행 정렬되지 않은 배열의 형태가됩​​니다. 그것은 가장 작은 값을 선택합니다. 이 경우, 3에서 오른쪽 이제 작다. 그것은 5 가져옵니다. 아니, 5 than-- 크지 또는 죄송합니다, 3 than-- 이하이다. 그래서 최소 값은 여전히​​ 3입니다. 그리고 당신은 2에 도착. 아보고 컴퓨터 2는 3 미만이다. (2)는 지금의 최소 값이어야합니다. 그리고 그 첫 번째 값 2 스왑. 

그래서 하나의 패스를, 우리는 참으로 보는가 그 2, 3 스왑됩니다. 그리고 우리는 단지 일을 계속하는거야 이 다시 배열의 나머지. 그래서 우리는 단지를 통해 실행하는거야 어레이의 마지막 네 인덱스. 우리는 3 인 것을 확인할 수 있습니다 다음 최소값. 그래서 우리는 4 그것을 바꿀 것입니다. 그리고 우리는 단지 계속거야 결국, 때까지 실행을 통해, 당신 정렬 된 배열에 도착하는 2, 3, 4, 5, 6이 모두 정렬된다. 모든 사람이 논리를 이해 하는가 선택 정렬이 작동하는 방법? 

당신은 어떤 종류가 최소값. 당신은 그게 뭔지를 추적하고 있습니다. 당신이 그것을 찾을 때마다, 당신은 그것을 교환 array--의 첫 번째 값 OR, NOT 제 value-- 배열의 다음 값. 쿨. 

그래서 너희들과 같은 종류의 짧은 엿볼에서 보았다, 우리는이를 의사 것입니다. 그래서 다시 너희들이 원하는 경우 테이블에 그룹 모두를 형성 작은 파트너를 형성 할 수있는, 내가 갈거야 당신에게 삼분 같은 사람을주고 다만 통해 얘기 논리, 영어, 우리는 구현할 수 있습니다 얼마나 의사는 선택 정렬을 작성합니다. 그리고 사탕이있다. 와서 사탕을 보내 주시기 바랍니다. 당신은 뒤에이고 당신이 원하는 경우 사탕, 난 당신에 사탕을 던질 수 있습니다. 사실, 얘들 아 멋진을한다. 아, 죄송합니다. 그래. 

우리는, 좋아하면 그래서 클래스, 쓰기 의사 사람이 접근 할 수있는 방법에 대한 이 문제는 단지 주시기 바랍니다. 난 그냥 주위에 갈 것이다, 순서 기 물어 의 다음 라인 우리는 무슨 일을해야한다. 너희들이 시작 싶다면 오프, 제일 먼저 무엇을 당신이 시도 할 때해야 할 일 본 프로그램을 해결하는 방법을 구현 선택적으로 목록을 정렬하려면? 단지 우리 가정의하자 배열, 모든 권리가있다? 

청중 : 당신은 어떤을 만들려면 일종의 [들림] 당신은 걸 전체 배열을 통해 실행. 

ANDI 펭 : 오른쪽. 그래서 당신은 반복 할거야 모든 공간을 통해, 오른쪽? 그래서 큰. 너희들은 나에게주고 싶은 경우 다음 뒤쪽에, 그래 line--. 

청중 : 그들을 확인 모든 작은합니다. 

ANDI 펭 : 거기 우리는 간다. 그래서 우리는 통과하고 검사 할 최소 값, 오른쪽 뭐가 있는지? 나는 해당 축약거야 "분." 너희들은 이후에 무엇을 하시겠습니까? 당신은 최소 값을 발견했습니다? 

청중 : [들리지] ANDI 펭 : 그래서 당신이 원하는거야 그 배열의 첫 번째로 전환, 권리? 그게 내가 말할거야, 시작입니다. 괜찮아. 그래서 지금 당신이 첫 번째를 교환했다고 하나, 당신은 무엇을 그 후 수행 할 수 있습니까? 그래서 지금 우리가 알고 여기 하나 오른쪽 작은 값이어야합니다? 그럼 당신은 추가 휴식을 정렬되지 않은의 배열. 그래서 당신은 당신이 경우에, 여기에 수행 할 작업 사람들은 나에게 다음 라인을주고 싶어? 청중 : 그럼 당신은 반복 할 배열의 나머지 부분을 통해. ANDI 펭 : 네. 그리고를 반복하는 일 종류의 우리가 아마해야 의미? 어떤 종류의 동행입니다 

청중 : 아, 추가 변수? ANDI 펭 : 아마 루프에 대한 또 다른, 오른쪽? 그래서 우리는 아마 원하는거야 through-- 큰를 반복합니다. 그리고 당신이 돌아 갈거야 및 아마 다시 최소를 확인, 권리? 그리고 당신은 계속 반복거야 이, 루프 때문에 단지 것 오른쪽으로 계속 실행하는 방법? 

그래서 너희들은 우리를 볼 수 있습니다 그냥 일반 의사가 우리가 원하는 방법으로이 프로그램을 찾으십시오. 여기에이 반복 처리, 우리는 무엇을 일반적으로 우리의 코드를 작성해야 우리는 반복하려는 경우 구조의 배열, 어떤 유형? 나는 Christabel 생각 이미 이전에이 말했다. 

청중 : 루프. 

ANDI 펭 : 루프? 정확히. 그래서 이것은 아마 for 루프가 될 것. 암시하는 것 여기에 체크가 무엇입니까? 일반적으로 검사 할 경우 뭔가 뭔가 경우 else-- 

청중 :합니다. 

ANDI 펭 : 경우, 오른쪽? 여기에 스왑 그리고, 우리는거야 나중에 가서 다윗 때문에 뿐만 아니라 강의에서이 높아졌습니다. 그리고 두 번째 반복 처리 implies-- 

청중 : 루프에 대한 또 다른. 

ANDI 펭 : 정확히, 루프 --another. 우리가 찾는 경우에 따라서 올바르게에서, 우리 우리는 아마 걸 볼 수 있습니다 루프 중첩 필요할 것 거기 조건부 문 다음 코드의 실제 조각의 그 값을 바꿀 것. 그래서 난 그냥 일반적으로 작성했습니다 여기 의사 코드입니다. 그리고 우리가 실제로거야 물리적으로, 클래스와, 이 오늘을 구현하려고합니다. 의이 IDE로 돌아 가자. 

어 오. 왜 거기 하죠 그래는 것입니다. 그래. 죄송합니다, 저를 좀 더 확대하려고 할 수 있습니다. 우리는 거기에 갈. 내가 여기서하고있어 모든 내가 만든됩니다 라는 프로그램 "선택 / sort.c." 나는 아홉의 배열을 만들었습니다 값, 4, 8, 2, 1, 6, 9, 7, 5, 3. 현재, 당신은 할 수 있습니다 그들은 순서가, 참조하십시오. n은 숫자가 될 것입니다 그 만약 그 값의 양을 말한다 당신은 당신의 배열에있다. 이 경우, 우리는 아홉 값을 갖는다. 그리고 난 그냥 여기에 루프를 가지고 즉, 정렬되지 않은 배열을 출력합니다. 

그리고 마지막에, 나는 또한에 대한있어 그냥 다시를 출력 루프. 이론적으로,이 경우, 프로그램 마지막에, 제대로 작동, 당신은 루프에 대한 인쇄를 참조한다 된 1, 2, 3, 4, 5, 6, 7, 8, 9 위해 모든 올바르게 있습니다. 

그래서 우리는 여기에 우리의 의사를 가지고있다. 난 그냥 해요 이러시면 사람이 원합니까 volunteers-- 요청 갈 경우에 무엇을 입력 정확히 말해 우리는 먼저, 단지 반복 할 이 배열의 시작 부분을 통해? 난 코드의 라인은 무엇입니까 아마 여기에서 필요로하는 것? 

청중 : [들리지] 

ANDI 펭 : 그래, 기분 무료 이러시면 미안 해요, 당신을 up-- 느낌을 참을 필요가 없습니다 음성 비트 인상 무료. 

청중 : INT의 난에 해당 내용 0-- 

ANDI 펭 : 그래, 좋아. 

청중 : 내가 배열의 길이보다 작습니다. 

ANDI 펭 : 그래서에서 유지 여기에 마음을 우리 때문에 기능이 없어 우리는 어레이의 길이를 알려주 우리는 이미이 그 저장 값. 권리? 또 다른 것은 유지 배열 mind--에 아홉 값으로, 인덱스는 무엇인가? 그냥이 배열은 0 ~ 3이었다 가정 해 봅시다. 당신은 마지막으로 볼 지수는 실제로 3입니다. 그것은 거기에도 불구하고, 4 아니다 배열의 네 개의 값. 

여기에 그래서, 우리는 매우 신중해야 길이 무엇인지 우리의 조건 될 것입니다. 

청중 : 그것은 N 마이너스 1을하지 않을까요? ANDI 펭 : 그것은거야 정확히 N 마이너스 1. 그 말이, 왜 그것은 N 영하 1, 모두? 배열은 제로 인덱스이기 때문이다. 그들은 0에서 시작하고 1 N 마이너스까지 실행합니다. 네, 조금 까다로운. 그래. 그리고-- 청중 : Isnt'1 그 이미하지만 알아서, 다만보다 이하 "라고하지 않음으로써 동일 미만 "그냥 말"로? " 

ANDI 펭 : 그것은이다 정말 좋은 질문입니다. 그래서, 예. 뿐만 아니라, 우리는 길을 걸 검사 권한을 구현, 두 값을 비교해야합니다. 그래서 당신은 실제로 원하는 "을"빈 둡니다. 당신이 비교하는 경우 때문에 이 하나, 당신은하지 않을거야 그 후 아무것도 오른쪽에 비교? 그래. 그래서 ++. 이제 우리의 브라켓을 추가 할 수 있습니다. 으악. 좋아요. 그래서 우리는 시작이 우리의 외부 루프의. 그래서 지금 우리는 아마 원하는 유지하는 변수를 생성 가장 작은 값을 추적, 오른쪽? 사람이 나에게주고 싶어합니까 그렇게 할 것입니다 코드의 라인? 우리가려고하는 경우에 우리는 무엇을해야합니까 뭔가를 저장할 수 있습니다? 

권리. 그 어쩌면 더 나은 이름 "온도"를 이따가 것이다 완전히 works-- 어쩌면 더 적절하게 될 것이다라는, 우리는 작은 value--을 원하는 경우 

청중 : 최소. ANDI 펭 : 분, 거기 우리는 간다. 분은 좋은 것입니다. 그리고 여기, 우리가 무엇을 할 로 초기화 할? 이것은 조금 까다 롭습니다. 때문에 지금의 이 배열의 시작, 당신이 바로, 아무것도에 못 봤어? 자동 그래서 무엇, 경우 우리는 그냥 0 일에있어 우리는 초기화 원하는 작업 우리의 제 1 최소 값? 청중 : 나는. ANDI 펭 : I, 정확하게. Christabel, 왜 우리가 원하는 수행 나는 그것을 초기화? 

청중 : 잘, 때문에 우리는 0부터 시작하고 있습니다. 우리가 비교 아무 상관이 없기 때문에 그래서 그것은, 최소 0 인 끝날 것입니다. 

ANDI 펭 : 맞아요. 그래서 그녀는 정확히 맞아. 우리가 실제로 가지고 있기 때문에 , 아직 아무것도 보았다 우리는 우리의 최소한의 값이 무엇인지 모른다. 우리는 단지에 초기화 할 내가있는 현재, 바로 여기에있다. 그리고 우리는에 계속 이 배열을 아래로 이동, 우리는 각각, 그를 볼 수 있습니다 추가 패스, 내가 증가. 그리고 그 시점에서, 나는 아마 것입니다 최소되고 싶어합니다, 그것은 무엇을 될 것 때문에 정렬되지 않은 배열의 시작입니다. 쿨. 

그래서 지금 우리는 추가 할 여기에 루프 그건 을 반복하는 것 분류되지 않은, 또는이 배열의 나머지. 사람이 나에게주고 싶어합니까 그렇게 할 것입니다 코드의 라인? Hint-- 우리는 여기에서 무엇을해야합니까? 무엇 루프이 갈거야? 그래. 청중 : 그래서 우리가 원하는 것 다른 정수를 가지고, 우리는 나머지를 통해 실행하고 있기 때문에 대신 나는 배열, 그래서 아마의 J. 

ANDI 펭 : 그래, j는 나에게 좋은 소리. 같음? 

청중 : 그래서 때문에, 나는 수에 1을 더한 것 당신은 다음 값에서 시작하고있다. 그리고 그렇게 다시 end--에, J는 N 마이너스 1을 입력 한 다음 J ++보다. ANDI 펭 : 좋아요. 

그리고 여기, 우리가 원하는거야 우리의 조건이 충족되어 있는지 확인합니다, 권리? 당신이 원하기 때문에 최소값을 변경 그것보다 실제로 더 작은 있다면 무엇 당신은 오른쪽과 비교거야? 그래서 우리는 여기에서 원하는거야? 확인하십시오. 문 어떤 종류의 우리는 아마 가고있다 TI는 경우에 사용하려는 우리 뭔가를 확인하려면? 

청중 : if 문. 

ANDI 펭 : if 문. 그래서 혹시 ...하고있을거야 무슨 우리 안에 원하는 조건 우리의 경우 문의? 

청중 : 만약 J의 값 난 -의 값보다 작 

ANDI 펭 : 맞아요. 그래서 혹시 ... 그래서이 배열은 "배열"이라고합니다. 좋아요. 그 무엇이었다 array--은 경우에 따라서? 다시 말해. 

청중 : 배열 J보다 작 으면 배열 나는, 우리는 분을 변경합니다. 그래서 분 J 것이다. 

ANDI 펭 : 그 말이됩니까? 그래. 그리고 지금 여기의 아래에서, 우리는 실제로 오른쪽 스왑을 구현하고 싶어? 그래서, 강의, 기억 다윗 때 그는 짓이야 무엇 이었는가를 교환하기 위해 노력했다 그건 ... 오렌지 주스와 milk-- 

청중 : 그 총이었다. 

ANDI 펭 : 그래, 그 종류의 총이었다. 그러나 그것은 꽤 좋았다 개념 시간을 보여주는. 그래서 여기에 당신의 가치를 생각. 당신은 배열을 가지고있어 분, 난의 배열, 또는 우리는 여기에 교환하려고했던 뭐든간에. 그리고 당신은 아마로 부어 수 없습니다 동시에 서로 오른쪽? 그래서 우리가 가고있는 것을 여기에 작성해야합니다 제대로 값을 교환하기 위해? 

청중 : 임시 변수. 

ANDI 펭 : 임시 변수. 그럼 INT 온도를 할 수 있습니다. 이 더 나은 것, 참조 워 이러시면 시간, 그 게 무슨? 그래. 그래서이 더 좋았을 것 시간은 변수 "온도를."이름을 지정합니다 그럼 INT 온도를 할 수 있습니다. 우리는 무엇을하려고 여기에서 동일한 온도를 설정? 청중 : 최소? ANDI 펭 : 그것은 조금 까다로운. 사실은 결국 중요하지 않습니다. 그것은 무엇을 중요하지 않습니다 순서는 스왑을 선택 만큼 당신이 확인하고있는 당신이있어 당신이 교환을하는지 추적을 유지. 

청중 : 그것은 배열-I 수 있습니다. 

ANDI 펭 : 그래, 배열-I를 할 수 있습니다. 그리고 다음 줄거야 코드의 우리는 여기에 갖고 싶어? 청중 : 배열 난 배열-J 같습니다. ANDI 펭 : 그리고 마지막으로? 청중 : 배열-j는 배열-I 같습니다. 청중 : 또는 배열-J 같음 배열 temp-- 또는, 온도. 

ANDI 펭 : OK. 그래서이 작업을 실행할 수 있도록하고 참조 그것이 작동거야 경우. 그게 어디 일이? 아, 그건 문제입니다. 우리가있어, 라인 (40)에, 참조 배열-J를 사용하려고? 그러나 여기서 만에 J 존재 하는가? 

청중 : 루프에서. ANDI 펭 : 오른쪽. 그래서 우리가해야 할 건가요? 

청중 : 짓이야 밖에서 정의 청중 : 그래, 난 당신이 생각 문 오른쪽 경우 다른를 사용 하는가? 그래서 같은 경우 minimum-- 좋아, 내가 생각해 봅시다. 

ANDI 펭 : 얘들 아, 시도 살펴 보자을 촬영합니다 우리는 여기서 뭔가 무엇을 할 수있어 참조하십시오? 

청중 : OK. 최소가 동일하지 않는 경우에 따라서 최소 인 경우 j-- 그래서 여전히 난 - 우리는 교체 할 필요가 없습니다 것입니다. 

ANDI 펭 : 나는 그와 동일합니까? 당신은 여기 싶은 말은? 

청중 : 아니면 그래, 경우 최소 그래, 같지 나는 않습니다. ANDI 펭 : OK. 우물은 우리의 문제, 가지, 해결한다. 하지만 여전히 해결되지 않습니다 J 이후 j--하면 어떻게됩니까의 문제 그것의 외부에 존재하지 않는, 무엇을 당신은 우리가 함께 할 하시겠습니까? 외부 선언? 의이 실행 해보자. 어 오. 우리의 종류는 작동하지 않습니다. 

당신은 우리의 초기를 볼 수 있듯이 배열은 그 값을 가지고 있었다. 그리고 나중에는해야한다 1, 2, 3, 4, 5, 6, 7, 8, 9에 있었다. 그것은 작동하지 않습니다. 아. 우리는 무엇을해야합니까? 청중 : 디버그. ANDI 펭 : 좋아, 우리가 그것을 시도 할 수 있습니다. 우리는 디버깅 할 수 있습니다. 조금 축소. 이제 우리의 중단 점을 설정하자. 의는 그때 엔 확인을 가자. 

우리가 이미 알고 있기 때문에 그래서 이 라인, 15 (22)를 통해, 내가 뭘 모든이기 때문에 working--된다 다만 통해 printing-- 반복 내가 가서 그를 건너 뛸 수 있습니다. 의 라인 (25)에서 시작하자. OOP는, 내가 그 없애 보자. 

청중 : 그래서 중단 점의 디버깅 어디 시작? ANDI 펭 : 또는 정지. 청중 : 또는 정지. ANDI 펭 : 네. 여러 중단 점을 설정할 수 있습니다 그냥 다른 하나에서 이동할 수 있습니다. 그러나이 경우 우리는 모른다 여기서 오류가 일어나고있다. 그래서 우리는 단지 원하는 위에서 아래로 시작합니다. 네. 그래. 

그래서 여기에이 라인은 우리가 개입 할 수 있습니다. 당신은 여기로 볼 수 있습니다 우리는 배열을 가지고있다. 사람들은 값입니다 배열에있는 것이다. 당신은 볼 수 있습니까, 그 방법 인덱스 0, 그것은 오 value--에 해당 나는 확대하려고하는거야. 죄송합니다, 정말 어렵다 배열 인덱스 0에서 see--합니다, 우리는 4의 값을 가지며 다음 등 등. 우리는 우리의 지역 변수가 있습니다. 지금은 동일하다 우리가 원하는 0. 

그리고 이제 단계별로 유지 할 수 있습니다. 우리의 최소값은 0과 같다 저희는 또한이 원하는. 그리고 우리는 우리의 두 번째 입력 루프 배열 J 배열-I 미만이면, 어떤이 아니었다. 그래서 당신은 어떻게 보았는가 즉, 그 이상 건너 뛴? 

청중 : 그래서 만약해야 최소, 모든 that--해야하지 그 루프의 첫 번째 내부에? ANDI 펭 : 아니, 때문에 당신은 여전히​​ 테스트 할. 당신은 모든 비교를 수행 할 시간, 당신은 그것을 통해 실행 후에도. 당신은 그것을 할 싶지 않아 첫 번째 통과에. 당신은 그것을 수행 할 다시 각각의 추가 패스. 그래서 당신은 확인하려면 내부 당신의 상태. 그래서 우리는 그냥 갈거야 여기를 통해 실행 유지. 나는 사람들에게 당신에게 힌트를 줄 것이다. 그것은 사실과 관련이있다 때 당신은, 당신의 조건을 확인하고 당신은 확인하지 않을 올바른 인덱스. 그래서 지금 당신은 검사하고 J의 배열 인덱스 배열 미만인 나는의 인덱스입니다. 하지만 당신은에서까지 일을 루프의 시작? 당신은 내가 동일한 J를 설정하지 않는거야? 

그래, 그래서 우리는 실제로 수 여기에 디버거를 종료합니다. 그럼 우리의 의사 살펴 보자. For-- 우리가 갈거야 내가 0 일에서 시작합니다. 우리는 1 N 마이너스까지 갈 것입니다. 의 확인하자, 우리는 그 권리가 있었나요? 네, 맞아요했다. 

그래서 여기에 내부에, 우리는있어 최소값을 만들려고 그리고 난에 그와 동일하게 설정. 우리는 그렇게 했습니까? 그래, 그했다. 지금 우리의 내면에 대한 루프에서, 우리는있어 J 할 거하면 내가 n을 뺀 1과 같다. 우리는 그렇게 했습니까? 사실, 우리는 그것을했다. 

그래서 그러나, 우리는 여기에 무엇을 비교하는거야? 

청중 : J 플러스 1. ANDI 펭 : 맞아요. 그리고 당신은 설정하려는거야 J 플러스 1뿐만 아니라 동일한 최소. 그래서 정말 신속하게 높아졌습니다. 너희들은 이해합니까 왜 J 플러스 1입니까? 그래. 

당신의 배열에 따라서 를 통해 첫 번째 패스, 루프 용, 인터넷 용 내가 0에 해당,의를 바로 보자 이 아직 변경되지 않은 가정합니다. 우리는 완전히의 배열을 가지고, 다만 4 정렬되지 않은 요소, 오른쪽? 그래서 우리는 i가 0이 초기화 할 수 있습니다. 그리고 난 것입니다 만 이 루프를 통해 실행합니다. 그래서 첫 번째 패스에서, 우리는거야 "분"라는 변수를 초기화 그 또한 있기 때문에, 나는 동일 우리는 최소의 값을 가질 수 없다. 그래서뿐만 아니라 0으로 현재와 동일합니다. 그리고 우리는 통과 될 것입니다. 그리고 우리는 다시 반복합니다. 이제 우리는 발견 한 것이 무엇을 우리의 최소 우리는을 통해 반복 할이다 그것을 비교하는 거라면 다시 오른쪽 볼? 그래서 J, 여기, 것입니다 동일한 난에 0이다. 그리고 만약 배열 J 플러스 I, 어떤 이하로, 다음 끝났어 하나는 무엇 현재 최소값보다 값은 교환 할 것이다. 

그래서 그냥 우리가했습니다 말을하자 2, 5, 1, 8, 마찬가지로 얻었다. 지금, 난과 동일 0 j는 0과 동일하다. 그리고 그것은 우리의 최소값입니다. 배열-J의 경우 플러스 난 - 하나 그렇다면 그것은 우리가보고있는 한 후입니다 그것은 이전보다 크다 이 최소가 될 것입니다. 

그래서 여기에 우리가 5 볼 그 이상이다. 그래서 5를하지 않을거야. 우리는 1, 오른쪽 미만임을 알? 그래서 지금 우리는 우리의 최소 것을 알고 0, 1, 2의 인덱스 값이 될 것. 그래? 그리고 당신은 여기 내려 할 때 올바른 값을 바꿀 수 있습니다. 

그래서 너희들은 J를 가진 때 전에, 당신은 하나보고되지 않았다 그 후. 당신은보고 있었다 동일한 값, 어느 그냥 아무것도되지 않은 이유입니다. 즉 모든 사람에게 의미가 있는가, 왜 우리는 플러스가 1이 필요? 그래. 지금은 확인을 통해 그냥 실행하자 확인 코드의 나머지 부분은 올바른 것입니다. 그 이유는 일이? 아, 그것은 바로 여기 분입니다. 우리는 잘못된 값을 비교 하​​였다. 오. 

오, 그래, 여기까지 우리는 있었다 뿐만 아니라 잘못된 값을 교환. 우리는 i와 j보고 있었다 때문에. 사람들은 우리가 확인 된 것들입니다. 우리는 실제로 교체 할 최소한, 현재 최소 무엇 이건 하나 밖에이다. 그리고 너희들은 아래로 볼 수있다 여기에, 우리는 정렬 된 배열을 가지고있다. 그냥 함께 할 수 있었다 사실 때 우리를 검사했다 우리가 비교 한 값으로, 우리는 오른쪽 값을보고하지 않았다. 우리는 같은 일을보고 있었다 여기에, 실제로 그것을 교환하지. 당신은 다음 중 하나를보고있다 그와 당신은 교체 할 수 있습니다. 그래서 가지 뭔지 전에 우리의 코드를 도청. 그리고 제가 여기에 한 일은 모든입니다 디버거가 당신을 위해 할 수 있었다 난 그냥 그것을했다 보드, 그것은 쉽게 때문에 노력보다는 볼 디버거를 확대합니다. 그 모두에게 의미가 있습니까? 쿨. 

괜찮아. 우리는 이야기에 이동할 수 있습니다 점근 표기법, 어떤 말의 단지 멋진 방법입니다 이러한 종류의 모든 런타임. 그래서 강의에서 다윗을 알고, 런타임에 만졌다. 그리고 그는 전체 식을 통해 갔다 의 런타임을 계산하는 방법에 대해 설명합니다. 그것에 대해 걱정하지 않습니다. 당신이 정말로 궁금하다면 그 작동 방법에 대한, 섹션 후 나에게 이야기 주시기 바랍니다. 우리는을 통해 걸을 수 함께 공식. 그러나 모든 너희들은 정말로를해야 알고는 n이 2 이상 제곱이다 n은 제곱 같은 일이다. 가장 큰 수 있기 때문에, 지수는 가장 성장. 그래서 우리의 목적을 위해, 우리가 걱정하는 모든 성장하고 그 거대한 숫자입니다. 

그래서 가장 좋은 경우입니다 선택 정렬의 런타임? 당신은 할 거라면 목록을 반복합니다 다음을 통해 반복 이 목록의 나머지 부분, 얼마나 많은 시간이다 당신은 아마로 이동 최악의 case--에 경우 가장 통해 실행 sorry--? 어쩌면 더 나은 질문은 묻고, 최악의 경우 무엇 선택 정렬의 런타임. 청중 : N 제곱. ANDI 펭 : 그것은 N 오른쪽 제곱입니다. 이처럼 너무 쉽게 생각하는, 당신은 루프 중첩 된 두가 언제, 그것은 N 제곱 될 것입니다. 당신입니다뿐만 아니라 때문에 다시 한번 통해 실행, 당신은 돌아 가야 주위와 그것을 통해 실행 다시 한 번 모든 값에 대한 내부. 이 경우에 따라서, 당신은 N을 실행하는 배 N, 미안 is--하는 제곱 n 번 N, N- 제곱 같아지는. 

그리고 종류도 조금입니다 의미에서 독특한 이들 경우 문제가되지 않습니다 값은 순서대로 이미. 아직 어쨌든 통해 실행하는 것입니다. 그냥이 1, 2, 3, 4이었다 가정 해 봅시다. 관계없이으로되었는지 여부의 순서, 그것은 여전히​​ 통해 실행했을 것이다 여전히 최소 값을 조사했다. 그것은 만들었을 것입니다 수표 동일한 개수 매 시간, 심지어 경우 실제로 아무것도 만지지 않았다. 

이러한 경우에 따라서, 가장 최악 런타임은 실제로 동일합니다. 그래서 예상 런타임 선택 정렬, 이는 우리가 기호로 지정 세타, 쎄타,이 경우, 또한 N 제곱 될 것이다. 이 세 가지 모두는 N 제곱 될 것이다. 왜 모든 사람이 분명하다 런타임은 N 제곱? 

괜찮아. 그래서 난 그냥 빨리 실행하는거야 종류의 나머지 부분을 통해. 위한 알고리즘 거품, 기억 sort-- 이것은 제였다 다윗은 강의에 갔다. 기본적으로, 당신은 단계 전체 목록을 당신은 당신을 swap-- 한 번에 두 가지를 비교합니다. 그리고 하나 더 있다면 당신보다 그냥 교환합니다. 이러한 큰 경우에 따라서, 당신은 교환 것이다. 나는 바로 여기에 공식있어. 

그럼 당신이 8, 6, 4, 2를 가지고 가정 해 봅시다. 당신은 8과 6 비교 것입니다. 당신은 그 (것)를 교환 할 필요가 것입니다. 당신은 8, 4 비교 것이다. 당신은 그 (것)를 교환 할 필요가 것입니다. 당신이 (8)을 교체해야하는 경우와 2뿐만 아니라 변경합니다. 그런 의미에서 그래서, 당신은 볼 수 있습니다 장기간에 걸쳐 펼쳐, 어떻게 거품의 값의 종류 이다 끝, 우리는 그것을 왜 전화 거품 정렬. 

우리는 다시 통해 실행됩니다 우리의 두 번째 패스, 그리고 세 번째 패스, 우리의 네 번째. 기본적으로, 버블 정렬 바로 실행 당신은 더 이상 스왑을하지 않습니다 때까지. 그런 의미에서 그래서, 이것은 단지입니다 그것의 일반 의사. 걱정은,이 모든 온라인 수 없습니다. 우리는 실제로이 이상 갈 필요가 없습니다. 

우리는 단지 카운터를 초기화 0에서 시작 변수입니다. 그리고 우리는 전체 배열을 통해 반복. 그리고 하나의 값이있는 경우가 말한 데로라면 값은, 그 값보다 크면 당신이 그들을 바꿀 것입니다. 그리고 당신은있어 계속 것. 그리고 당신은 계산하는 것입니다. 그리고 당신은 일을 계속하는거야 이 카운터는 큰 반면 것을 의미한다 0보다 때마다 당신은 교체해야 당신은 당신이 가고 싶은 알고 다시 다시 확인합니다. 당신은 당신이 알고있을 때까지 검사를 계속하려면 것을 더 이상 교체 할 필요가 없습니다. 

그래서 최고와 최악의 무엇입니까 경우 거품 정렬을 위해 런타임은? 그리고 hint--이 실제로 다른 의미에서 선택 정렬에서 이 두 가지 답변은 동일하지 않습니다 것을. 에 무슨 일이 일어날 지 생각 해봐 경우 그것은 이미 정렬 된 경우. 그리고 어떻게 생각하는지 그것이 경우에 일어날 것 경우에 어떤에서 정렬되지 않았습니다. 그리고 당신은 가지 실행할 수 있습니다 이유를 통해 그 무슨 일이 일어나고. 나는, 30 등, 너희들을 줄 것이다 초 그것에 대해 생각합니다. 

그래. 사람이 무엇에 추측이 있습니까 버블 정렬의 최악의 경우 런타임은? 그래. 

청중 : 그것은, 같은, n 번 것 N 마이너스 같은 1 또는 뭔가? 마찬가지로,이 실행될 때마다, 그것은 하나의 스왑 이하, 같은 단지 무엇 이건 그것은이었다. 

ANDI 펭 : 네, 그래서 당신은 완전히 맞아. 그리고이있는 경우 귀하 대답은 실제로 더 복잡 하나보다 우리가 제공 할 필요가있다. 그래서 난 run-- 것 여기에 모든이를 지울 것. 모두가 좋은가요? 나는이를 지울 수 있습니까? 그래. 당신은 N을 통해 실행하는거야 시간이 처음으로, 오른쪽? 그리고 그들은을 통해 실행하는거야 N 마이너스 1 번째, 오른쪽? 그리고 당신은 유지하는거야 n 개의 광산 2, 등등, 가고. 다윗은 어디 강의에서 이런 짓을, 당신은 모든 값을 추가 한 경우, 당신이 뭔가를 얻을 그때 엔 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보다 작은가요? 그것은 아니다. 그래서 우리는 아래로 계속 찾고 있습니다. 그런 다음 3 떨어져 2를 확인합니다. 그것은 이하인가? 아니. 그래서 2가 삽입되어야한다 알고 전면에, 3 및 5 모두 밀어해야합니다. 6 4 다시이 작업을 수행합니다. 그리고 우리는, 본질적으로 계속 확인 우리가 확인하는 경우, 확인 확인합니다. 그리고 오른쪽에 때까지 위치, 우리 종류의 단지 올바른 위치에 삽입, 이는 그것의 이름이 어디​​에서 온 것입니다. 

그래서 그냥 알고리즘이다, 의사 자체, 가지, 우리가 구현하는 방법에 삽입 정렬. 의사 코드는 여기에있다. 그것은 모든 온라인입니다. 걱정하지 너희들이있는 경우 이 아래로 복사하려고합니다. 그래서 다시 한 번, 같은 question-- 무엇 최고와 최악의 런타임을 것 삽입 정렬을 검색 하시나요? 그것은 마지막 질문에 매우 유사하다. 나는, 30 등, 너희들을 줄 것이다 초뿐만 아니라 이것에 대해 생각합니다. 

사람이 원하는 않습니다 확인 나에게 최악의 런타임을 제공? 그래. 

청중 : N 제곱. 

ANDI 펭 : 그것은 N 제곱입니다. 그리고 왜 N 제곱? 

청중 :에 있기 때문에 역순으로, 당신은 is--하는 N 배 통과 n으로 ANDI 펭 : 네, 정확히. 거품 분류 그래서 같은 일. 이 목록에있는 경우 내림차순, 당신이있어 먼저 번을 확인해야 할 것. 그리고 그와 함께 모든 부가 가치, 당신이있어 가지고가는에 대해 그것을 확인 바로 모든 단일 값? 그리고 모두, 당신은 할거야 N 통과 시간은 또 다른 N, 통과하는 N 제곱된다. 무엇 최상의 경우는 어떻습니까? 그래. 

청중 : N 마이너스 1, 때문에 첫 번째는 이미 제곱된다. 

ANDI 펭 : 그래서, 부근에 있습니다. 대답은 실제로 N이다. 첫 번째 인 반면 때문에 분류, 그것을 ... 사실상하지 않을 수 있습니다 우리는 단지에, 밖으로 운도 그 예를 들어, 그 2 가장 작은 숫자로 일어났다. 그러나 항상 그런 것은 없습니다. (2)는 이미 시작으로 정렬되어있는 경우 하지만,보고 여기에 1 거기 1은 범프 것입니다. 그리고 그것은 끝 것 최대 어쨌든 충돌된다. 

최선의 시나리오에 따라서 실제로 단지 N 될 것. 아래와 같은 경우 1, 2, 3, 4, 5, 6, 7, 8에는있어 를 통해 실행하는 것 그 전체 목록을 한 번 모든 게 잘 있는지 확인합니다. 실행중인 모든 사람이 분명하다 뿐만 아니라 선택의 시간? 내가 통해 갈거야 알고 이 정말 빨리. 그러나 당신이 알고있는 경우 알고 일반적인 개념은, 당신이 잘되어야합니다. 그래. 그래서 난 그냥 같은, 어쩌면 너희들을 줄 것이다, 분은 이웃에게 이야기하기 무엇 단지 일부에 주요 차이점 종류의 이러한 종류의 사이. 우리는 곧 갈 거예요. 청중 : OK, 오. ANDI 펭 : 네. 그래. 쿨,의 클래스로 재 소집 할 수 있습니다. 그래. 그래서이이었다 종류의 의미에서 개방형 질문 그들에 대한 답변을 많이가있다. 그리고 우리는 잠시 그​​ 중 일부를 통해 이동합니다. 난 그냥 너희들을 얻고 싶었다 차별화 된 무엇에 대해 생각 세 종류의 타입. 그리고, 또한, 훌륭한 들었다 무엇을 일종의 병합 않습니다 question--? 좋은 질문, 그 때문에 우리는 다음 취재하고 있습니다. 

그래서 종류입니다 병합 그 기능을 하나의 종류 매우 다르게 다른 종류에서. 너희들은 see-- 수 있듯이 다윗은 그 데모를 짓 그는 모든 멋진 있었다 곳 병합 방법 보는 소리 일종의 무한 같은, 실행 다른 두 유형보다 빠르게? 그래. 그래서 병합 때문이다 일종의 그 격차를 구현 우리가했습니다 개념을 정복 강의에 많은 이야기. 우리가 일을하고 싶은 그런 의미에서 똑똑, 당신은 분할 할 때, 열심히 문제를 정복하고 휴식 다운 한 후, 이들을 함께 넣어 좋은 일이 항상 일어난다. 

병합하는 방식 그래서 종류 본질적으로 작동 이 분할이다 반에서 정렬되지 않은 배열입니다. 그리고 그것은 배열의 두 반쪽을 가지고있다. 그리고 그것은 단지 그 두 부분을 정렬합니다. 그것은 단지에서 반으로 나누어 유지 절반, 절반으로 모든 것이 분류 할 때까지 다음 재귀 모두 함께 넣습니다. 

그래서 정말 추상적이다. 그래서 이것은 의사의 조금이다. 그에서 의미가 있습니까 그것이 실행의 방법은? 그래서 당신이이 말을하자 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)는 거기에 가야한다. 그래서 당신이 아래로 풍덩, 당신은 그것을 떨어져 들어온다. 그럼 당신은 단지 3가 및 (4) 및 (6) (5). 그리고 당신은 그것을 떨어져 자르고 유지 당신은 배열에 넣어 때까지. 

청중 : 그래서 당신은 항상있어 [들리지]를 비교? 

ANDI 펭 : 맞아요. 그래서 그런 의미에서, 당신은있어 다만 비교 본질적 다른 번호에 대해 하나의 번호. 그리고 당신이 알고 있기 때문에 그것은 당신을 분류 있다고 를 통해 볼 필요가 없습니다 숫자의 모든. 당신은 첫 번째로보고있다. 그리고 당신은 그냥 풍덩 수 있습니다 그 아래로, 당신이 알고 있기 때문에 자신이 속한하기 위해 필요로하는 곳에 그들은 속한다. 그래. 좋은 질문. 

그리고 당신의있는 경우 조금 야심, 이 코드를 살펴 주시기 바랍니다. 이것은 사실이다 물리적 구현 우리가 병합 정렬을 작성하는 방법. 그리고 당신은 매우 짧다 볼 수 있습니다. 뒤에 그러나 아이디어 꽤 복잡하다. 그래서 당신은이를 그리기 같은 느낌 경우 숙제 오늘 밤에, 주시기 바랍니다. 

그래. 그래서 다윗은 또한 강의에서이 이상했다. 최상의 경우 무엇입니까 런타임, 최악의 경우 런타임, 및 병합 정렬의 예상 런타임? 몇 초 생각합니다. 이 꽤 어렵지만, 가지 당신은 그것에 대해 직관적으로 생각합니다. 괜찮아. 

청중 : 최악의 경우 N 로그 N인가? ANDI 펭 : 맞아요. 그리고 왜 N N를 기록한다. 

청중 : 그것은 아닌가요 그것 때문에 기하 급수적으로 빨라집니다 그래서 그 기능처럼 대신 간단하게 해당되는 제곱 또는 무엇인가? ANDI 펭 : 맞아요. 그래서 이유 이에 런타임은 N 로그입니다 당신이 무엇인가 이유는 - n은 모든 단계에서 무엇을? 당신은 바로, 반으로 자르고있어? 그래서 우리는 일을 할 때 그것을하고있어 모든 것을 기록 절반으로 분할되는 문제, 절반, 절반, 더 반쪽에. 그리고 그런 의미에서, 당신은 종류의 수 선형 모델의 제거 것을 우리는 사용하고있다. 당신이 들어온다 때 때문에 반에서 일,이 로그입니다. 그건 그냥 수학의 그것을 표현하는 방법. 

다음 마지막 끝 부분에서는있어 다만 마지막 패스를 통해 제작 오른쪽 순서대로 모두 넣어? 그래서 당신은 단지에있는 경우 한 가지를 확인, 그것은 N입니다. 그래서 당신은 종류의 것 두 개의 서로를 곱하여. 당신이 최종있어 같은 그건 N의 로그 여기 아래로 n 개의 확인 여기. 그리고 당신은 곱하면 그들, 즉 N N 로그입니다. 

그리고 최상의 경우와 최악 케이스 및 모든 N N를 기록하고 있습니다 기대했다. 그것은 다른 종류의 같은이기도합니다. 그것은 선택 정렬처럼 그 의미에서 무슨 상관하지 않는 목록은 그냥 무슨이다 같은 일을 매번해야 할 일. 그래. 비록, 너희들이 볼 수 그래서 우리는 N through-- 갔어요 종류 제곱, 그것은 매우 효율적이 아니다. 심지어이 N 로그 n은 가장 효율적인 없습니다. 너희들이 궁금하면, 정렬 메커니즘이있다 그들이있어 너무 효율적이 거의 본질적으로 평면 런타임. 

당신은 몇 가지 로그 N의를 가지고있다. 당신은 몇 가지 로그 로그 N의를 가지고있다. 우리는 그들에게 만지지 마세요 지금이 클래스. 하지만 너희들이 궁금하면, 무슨 일이야, 구글 주시기 가장 효율적인 정렬 메커니즘. 나는 거기 몰라 정말 재미있는 것, 그때 엔 정말이있다 사람들이 만드는 재미 것. 그리고 당신은 궁금해 그들이 지금까지 그 생각. 당신은 몇 가지 여분을 가지고 있다면, 구글 시간에, 몇 가지 재미있는 방법은 무엇인가 그뿐만 아니라 people-- 효율적인 ways-- 사람들 정렬을 구현할 수 있었다. 그래. 그리고 여기 그냥 쉽고 간단한 차트입니다. 나는, 그 퀴즈 0 전에, 여러분 모두를 알고있다 객실에서 아마 시도를 할 것이다 그 기억합니다. 그래서 너희들 거기에 좋다. 그냥 made-- 논리를 잊지 마세요 왜 그 숫자가 발생했다. 당신은 항상 분실하는 경우, 단지 확인 확실히 당신은 종류가 무엇인지 알고있다. 그리고 당신은을 통해 실행할 수 있습니다 당신의 마음에 그 왜 사람들을 알아낼 답변은 그 대답입니다. 

괜찮아. 그래서 우리는 이동하는거야 마지막으로, 검색,에. 때문에 당신의 것과 같은 누가 PSET을 읽고, 또한 검색의 일부 이번 주 문제는 설정합니다. 당신은 실행하라는 메시지가 표시됩니다 두 가지 유형의 검색. 하나는 선형 검색하며 하나는 이진 검색이다. 

그래서 선형 검색은 매우 간단합니다. 당신은 요소를 검색 할 당신이 그것을 얻을 경우 목록으로 볼 수 있습니다. 당신은을 통해 반복해야합니다. 그리고 뭔가를 동일한 경우, 당신이 바로, 그것을 반환 할 수 있습니까? 그러나 한 우리는 대부분의 걸 이야기에 관심 이진 검색은 인 권리이다 분할기구를 정복하는 다윗은 강의에서 입증되었다. 

전화 번호부 예 기억 그는 양육 유지하는 것이, 그는 종류의 고투 한 지난 해에 조금, 만약 반 문제를 분할하는 경우, 절반, 절반, 또 다시, 당신은 당신이 원하는 것을 찾을 때까지? 그리고 당신이있어 뿐만 아니라 그 실행. 그리고 당신이 볼 수있는, 그것은이다 훨씬 더 효율적 검색은 임의의 다른 타입보다. 

그래서 우리가 갈 것이다 방법 이진 검색을 구현 , 우리가 배열이 있다면, 인덱스 0-6, 일곱 요소, 우리는 right--, 중간에 볼 수 있습니다 죄송합니다, 우리의 질문 경우 first-- 우리가 질문을하려는 경우, 수행 배열은, (7)의 요소를 포함 분명히, 인간을 존재하고, 필요 작은 배열과 같은, 그것은 우리를 위해 쉽게 네 대답. 그러나이 방법을 구현하는 이진 검색 중간에보고 될 것이다. 

우리는 색인 3 것을 알고 중간, 우리 때문에 일곱 요소가 알고있다. 무엇 7은 2로 나눈? 당신은 추가 한 것을 잘라낼 수 있습니다. 당신은 중간에 3을 가지고있다. 그래서 7과 동일한 3의 배열입니다? 그것은 바로, 아니다? 그러나 우리는 검사의 몇 가지 작업을 수행 할 수 있습니다. 3 이하 7 이상 또는 배열 7보다 큰 3의 배열입니다? 

그리고 우리는 덜 7보다 있다는 것을 알고있다. 그래서 우리는 알고 오, 그것은해야합니다, 그 왼쪽 절반을지지 않습니다. 우리는해야합니다 알고 오른쪽 절반에, 오른쪽? 그래서 우리는 절반 배열을 절단 할 수 있습니다. 우리는 심지어 필요가 없습니다 더 이상 봐. 우리는 것을 알고 있기 때문에 우리의 problem--의 절반 우리는 대답에 있음을 알고있다 우리의 문제의 오른쪽 절반. 그래서 우리는 지금 막 봐. 

그래서 지금 우리가보고 남은 것의 중간. 즉, 인덱스 5. 우리는 다시 같은 검사를 할 우리는 작다 것을 알 수있다. 그래서 우리는 그 왼쪽에 보인다. 그리고 우리는 그 검사를 참조하십시오. 배열 값에서인가 7 동일한 인덱스 4? 그것은. 그래서 우리는, true를 돌려 때문에 수 우리는 우리의 목록에서 값을 발견했다. 내가 겪었 방법을합니까 모두에게 그 말이? 그래. 나는 같은, 어쩌면 너희들을 줄 것이다 셋, 넷 분 알아낼 방법이를 의사합니다. 

그래서 나는 쓰기를 요청 상상 반환 기능이라고 검색 () 값, 부울 값, 즉, 같은 사실 또는 false-- 당신이 발견하는 경우는 true 값, 당신은하지 않았다 경우는 false. 그리고 당신은 있었다 값을 전달하면 값으로 찾고 된 array-- 오, 나는 확실히 넣어 잘못된 위치에있다. 그래. 어쨌든, 그것은이 있어야합니다 값의 오른쪽에 있었다. 다음 INT N은 숫자이며 그 배열의 요소. 어떻게 노력에 대해 갈 것 에서 그 문제를 의사가? 난 당신 같은 사람을 줄 것이다 삼분 그렇게 할 수 있습니다. 아니, 난 only-- 있다고 생각 그래, 바로 여기에 하나가있다. 청중 : 나는 할 수 있습니까? ANDI 펭 : 그래, 난 당신을 얻었다. 그 작업인​​가? 그래 좋아. 

그래. 좋아 얘들 아, 우리는있어 그것을 억제 할 것. 그래. 그래서 우리는이 사랑스러운있어 가정 거기에 N 값이 작은 배열입니다. 나는 선을 그릴하지 않았다. 그러나 우리는에 대해 어떻게 갈 것 이 작성하려고? 사람이 원하는 않는다 나에게 첫 번째 라인을 제공? 당신은 나에게주고 싶은 경우 이 의사의 첫 번째 줄. 

청중 : [들리지] 청중 : 당신은 싶어 through-- 반복하는 청중 : 그냥 다른 루프? 청중 : --for. 

ANDI 펭 : 그래서이 사람은 조금 까다로운. 당신이 원하는 비슷해 생각 이 루프를 계속 실행하기 또 다시 언제까지? 

청중 : [들리지]까지 값은 그 값과 같습니다. ANDI 펭 : 맞아요. 그래서 당신은 실제로 단지 write-- 수 있습니다 우리는 더를 단순화 할 수 있습니다. 우리는 바로, while 루프를 할 수 있습니까? 그래서 당신은 loop-- 수 있습니다 우리는 잠시 있다는 것을 알고있다. 하지만 지금, 나는거야 무엇을 통해 - "루프"말을? 루프는 무엇 until-- 우리의 종료 조건? 내가 들었 생각합니다. 나는 누군가가 말을 들었다. 

청중 : 값은 중간 같습니다. ANDI 펭 : 다시 말해봐. 까지 또는 : 관객 값이 검색하는 위한 중간 값은 동일하다. 

ANDI 펭 : 거기에없는 경우는 어떻게? 어떤 경우에는 당신이 검색하는 값 이 배열에 실제로 아니다? 청중 : 당신은 1을 반환합니다. 

ANDI 펭 :하지만 우리는 무엇을 하시겠습니까? 우리는 조건이있는 경우까지 루프? 그래. 

청중 : 하나의 값이 될 때까지? ANDI 펭 : 당신이 할 수있는 루프 until--은 그래서 당신은 당신이 거 알아 바로, 최대 값을해야 할 것? 그리고 당신은 당신이 가고 있다는 것을 알고있다 오른쪽 분 값을 가지고 있습니까? 또한, 그 무언가 때문에 내가 전에 말을 잊었다 의 뭔가 이진 검색에 대한 중요 당신의 배열이 이미 정렬되어 있다는 것입니다. 수행의 방법이 없기 때문에 이 그들은 단지 임의의 값을하는 경우. 하나가 있다면 당신은 몰라 다른 것보다 더 큰, 오른쪽? 

그래서 당신이 알고있는 당신의 최대 및 당신의 분은 바로 여기에있다? 당신이 조정 될 거라면 당신의 분, mid--에서 최대 그냥 가정하자 당신의 중간 값은 바로 here--입니다 당신은 기본적으로거야 루프가 최소가 될 때까지 오른쪽, 당신의 최대와 동일, 또는 약 당신의 최대는 분으로 동일하지 않은 경우. 권리? 그렇게되면 있기 때문에, 당신은 알고 당신은 결국 동일한 값을 부딪혔을. 그래서 당신은 당신의 분까지 루프를 원하는 보다 작거나 죄송합니다 이러시면 동일 아니보다 작거나 같음, 최대 around-- 다른 방법입니다. 

그 의미를 했습니까? 나는 그 권리를 얻기 위해 몇 가지 시도를했다. 그러나 루프 당신의 최대 값까지 본질적으로 거의 이하 이상 또는 최소 동일, 오른쪽? 당신이 알고있는 때이다 당신은 수렴했다고. 청중 : 때 것 최대 값은 최소값보다 작? ANDI 펭 : 당신은 유지하는 경우 이를 조정하는 우리가가는 것입니다 이에서 일을합니다. 말이 돼? 최소 및 최대 단지이다 우리는 아마 정수 원하는가는 계속 만들 수 우리가 찾고있는 위치를 추적. 배열이 존재하기 때문에 에 관계없이 우리가 무슨 일을하는지의. 마찬가지로, 우리는 실제로 물리적 아니에요 오른쪽 배열 떨어져 자르고? 우리는 단지 조정하고 우리는 어디에서 찾고 있습니다. 말이 돼? 

청중 : 네. 

ANDI 펭 : OK. 즉 우리의 루프의 조건의 경우에 따라서, 우리는이 루프의 내부에 무엇을 원하는가? 우리는 무엇을하고자하는 건가요? 그래서 지금, 우리는있어 최대 및 최소, 오른쪽, 아마 여기 어딘가에 만들었습니다. 우리는 아마 원하는거야 오른쪽 중간을 찾는 방법은? 우리는 어떻게 할거야 중간을 찾을 수? mathematical--은 무엇인가 청중 : 맥스 플러스 2로 나눈 분. ANDI 펭 : 맞아요. 말이 돼? 그리고 너희들은 왜 우리를 볼 수 있습니까 우리가 이런 짓을 왜 그냥 use--하지 않았다 대신 일을 바로 N 2로 나눈? n은 값이 그것 때문에 즉 동일하게 유지하는 것입니다. 권리? 그러나 우리는 우리의 최소한을 조정하고 최대 값, 그들은 변경 될 것입니다. 결과적으로, 우리의 중간 너무 바꿀 것입니다. 우리가 원하는 이유 그래서입니다 여기에이 권리를 할 수 있습니다. 그래. 

그리고, 지금 우리는 그래 our-- 발견했습니다. 

청중 : 그냥 빨리 question-- 때 최소 및 최대 말, 우리는 가정된다 그것은 이미 정렬이야? 

ANDI 펭이 : 네, 사실입니다 이진 검색을위한 전제 조건, 당신이 가지고이 분류 것을 알고 있습니다. 왜 일종 인 당신은 쓸 당신의 문제는 이진 검색하기 전에 설정합니다. 그래. 그래서 지금 우리가 어디에서 우리의 중간 점을 알고 , 당신은 무엇을 여기에서하고 싶어한다? 

청중 : 우리는 비교하려는 다른 하나에있다. ANDI 펭 : 맞아요. 그래서 당신은 비교거야 값으로 중간, 오른쪽? 그리고 그 무엇을 말해 주는가 우리에게 우리가 비교할 때? 우리는 무엇을 나중에 수행 할 수 있습니까? 

청중 : 값이 큰 경우 중반보다, 우리는 그것을 차단합니다. ANDI 펭 : 맞아요. 값이 너무 크면 중반보다, 우리는있어 이러한 변경하려는 것 최소 maxes, 오른쪽? 우리는 무엇을 변경 하시겠습니까? 우리가 알고있는 경우에 따라서 값은 어딘가에 여기, 우리가 변경할 수 무엇? 우리는 우리를 변경하려면 최소 오른쪽, 중앙 수 있습니까? 그리고 또,이에 있다면 반, 우리는 무엇을 변경 하시겠습니까? 

청중 : 최대. ANDI 펭 : 네. 그리고 당신은거야 , 오른쪽 반복 유지? 지금 때문에, 하나의 반복 후 을 통해, 당신은 여기에 최대를 가지고있다. 그리고 당신은 중반을 다시 계산할 수 있습니다. 그리고 당신은 비교할 수 있습니다. 그리고 당신은 계속거야 분, maxes까지 기본적으로 통합했다. 당신이 알고 때 그건 당신은 그것의 끝을 공격했습니다. 그리고 어느 쪽이든 당신은 그것을 발견했습니다 또는 당신은 그 시점에서하지 않았습니다. 

이것은 모두에게 의미가 있습니까? 그래. 이것은 매우 중요하다 당신은 할 것이기 때문에 코드 오늘 밤에이를 작성합니다. 그러나 너희들은 꽤 좋은가 당신이 일을해야 무엇을 의미, 하는 것이 좋다. 그래. 그래서 우리는 일곱에 대해있어 분 섹션을 떠났다. 그래서 우리는에 대해 이야기하는거야 우리가 일을 할 것이다이 PSET. 그래서 PSET은 두 부분으로 나누어 져 있습니다. 상반기 포함 찾기를 구현 하는 당신은 선형 검색 쓰기, 이진 검색하고 정렬 알고리즘. 

그래서이 처음이다 PSET 곳에서 시간 라고 우리는 너희들을주고있을거야 분포 코드, 코드는 우리는 미리 작성된 것으로, 하지만 방금 일부 조각을 왼쪽으로 에 대한 당신은 글을 마칩니다. 이 봐 너희들, 그래서 코드, 당신은 정말 겁 있습니다. 당신은, 아, 내가 좋아하는 그냥하는 경우 그 무엇을하는지 모른다, 내가 좋아하는, 즉 것, 모르는 너무 복잡, 아, 휴식. 괜찮아요. 사양을 참조하십시오. 사양은 정확하게 당신에게 설명 할 것 이 모든 프로그램은 무엇을하고 있습니다. 

예를 들어, generate.c는 프로그램이다 그게 당신의 PSET 함께 올 것이다. 당신은 실제로 그것을 터치해야하지만하지 않습니다 당신은 무엇을하고 있는지 이해해야합니다. 그리고 generate.c, 그것은하고있어 모든입니다 중 임의의 숫자를 생성 또는 당신처럼, 그것을 씨앗을 제공 할 수 있습니다 걸리는 사전에 조정 번호, 그리고 이상의 숫자를 생성한다. 그래서 특정 방식이있다 generate.c을 구현하는 당신은 단지 숫자의 무리를 만들 수 있습니다 당신은 다른 방법에 테스트를 위해. 

그래서 당신이 원하는 경우에 대한 예를 들어, 당신의 발견을 테스트 당신이 generate.c을 실행하려는 것이다, 숫자의 무리를 생성 다음 헬퍼 함수를​​ 실행합니다. 당신이있어 어디 도우미 기능입니다 실제로 물리적으로 코드를 작성. 그리고 라이브러리 파일로 헬퍼 생각 당신은 찾기가 호출 쓰고있어. 그래서 helpers.c 내에서, 당신은거야 검색 및 정렬 할. 

그리고 당신은 본질적으로거야 그냥 모두 함께 넣어. 방법에 대한 사양은 당신을 말할 것이다 명령 행에 해당했습니다. 그리고 당신이 있는지 여부를 테스트 할 수 있습니다 또는 아닌 정렬 및 검색이 노력하고 있습니다. 쿨. 사람이 이미 시작하고 발생하는 문제 또는 질문 그들은이와 지금이? 그래. 

청중 : 기다립니다. 나는 질문이 있습니다. 

ANDI 펭 : 네. 

청중 : 그래서 나는 일을 시작 helpers.c의 선형 검색 그리고 그것은 정말로 작동되지 않았습니다. 그러나 나중에, 우리 단지를 발견 을 삭제하고 이진 검색을 할 수 있습니다. 그것이 작동하지 않는 경우에 따라서는 문제가 무엇입니까? 

ANDI 펭 : 짧은 대답은 no입니다. 하지만 이후 우리는 싫든있어 청중 :하지만 아무도 실제로 검사합니다. ANDI 펭 : 우리는 결코 것 없​​다 것을 볼 것. 하지만 당신은 아마 만들고 싶어 확인 검색이 노력하고 있습니다. 당신의 선형 경우 때문에 검색이 작동하지 않습니다, 다음 기회는 당신의 바이너리 검색이 잘 작동하지 않을. 당신은 비슷한 가지고 있기 때문에 그 양자의 논리. 그리고 아니, 정말 중요하지 않습니다. 그래서 유일한 사람은 당신이 설정합니다 에 정렬과 이진 검색입니다. 그래. 

또한, 아이들이 많이 있었다 helpers.c를 컴파일하려고합니다. 당신은 실제로 허용하지 않을 , 그렇게 helpers.c 때문에하기 주요 기능이 없습니다. 그래서 당신은해야 실제로 컴파일 할 수 전화를 찾을 수 있기 때문에, 생성하고 찾을 수 helpers.c과 그 안에 기능. 그 디버깅을하게 그래서 엉덩이에 통증이. 하지만 우리가해야 할 일이다. 청중 : 당신은 바로, 모든을? ANDI 펭 : 당신은 할 수 있습니다 네,뿐만 아니라 모든합니다. 그래. 그래서 어떤면에서 그것 뿐이다 PSET 여러분 모두가해야 할 요구하고있다. 당신은 질문이있는 경우에는, 느낌 섹션 후 나에게 물어 주시기. 나는 20 분, 같은, 여기있을거야. 

그리고 그래, PSET의의 정말 나쁘지 않다. 너희들은 확인해야합니다. 이, 그냥 지침을 따르십시오. 종류의 논리적의 감각을 가지고, 어떤 해야이 일어나고있는 당신은 괜찮을거야. 너무 무서워하지 마십시오. 많은 코드가있다 이미 작성. 그렇게하지 ​​않으면 너무 무서워하지 마라 그 모두가 무엇을 의미하는지 이해합니다. 이 많이 있다면, 그것은 완전히 괜찮아요. 그리고 근무 시간에 온다. 우리는 당신을 살펴 도움이됩니다. 

청중 : 추가로 기능, 우리는 사람들을 찾아 볼 수 있습니까? 

ANDI 펭 : 네, 그 코드에 있습니다. 15 게임, 절반의에서 이미 당신을 위해 작성합니다. 그래서 그 기능은 이미 코드. 네. 괜찮아. 그럼, 행운을 빈다. 그것은 역겨운 일이다. 그래서 희망 너희들은 너무 생각하지 않습니다 내부 체재 및 코딩에 대한 나쁜.