스피커 1 : 안녕하세요 여러분! 섹션에 다시 오신 것을 환영합니다. 여기에 둘 다 너무 많은 볼 됐군 온라인 지켜보고 모든 사람. 그래서 평소 환영 거슬러. 여러분 모두 사랑스러운 있었다 희망 나머지의 전체 주말, 휴식. 그것은 어제 아름다웠다. 그래서, 난 당신이 야외 활동을 즐길 바랍니다. 발표 몇 그래서 처음. 등급. 그래서, 당신의 대부분이 입수했습니다해야 스크래치 Pset에 대해 나에게 이메일을 보내, 뿐만 아니라 Pset에 1 등급. 따라서, 단지 몇 가지. style50에 check50을 사용하십시오. 이러한 것으로 의미 너희들을위한 자원, 당신이 얻고 있는지 확인합니다 당신이 할 수있는 한 많은 포인트 불필요하게 그들을 잃지 않고. 그래서, 스타일 같은 것들을 매우 중요하다. 우리는 그것을 벗으려고하고있다. 여러분 중 일부는 이미 수 있습니다 귀하의 경우 Pset에서 해당났습니다. 그리고 check50 단지이다 확인하려면 정말 쉬운 방법 우리는 실제로 반환하고 있다는 것을 사용자에게 리턴 될 필요 그 모든 것이 제대로 작동합니다. 두 번째 메모에서 확인하여 올바른 폴더에 물건을 업로드. 내 인생 단지를 만든다 조금 더 어려운 당신은 Pset에 1에 Pset에 2를 업로드하면 내가 일을 다운로드 할 때 때문에, 그들은 제대로 다운로드되지 않습니다. 그리고 나는 조금 남았습니다 알고 시스템에 익숙해, 그러나 다만 슈퍼 영웅이 될 주의, 나만 경우, 그래서 당신은 이메일을 때 추천 시부 나는 등급 해요. 그렇지 않으면 것은 내가 볼 필요가 원인 모든 주위에 당신의 Pset에 대한. 쿨. 나는 일찍 알고,하지만 난 완전히 가드를 당했어요 이 금요일까지의 에세이, 그하여 제 교수는 오, 그래, 좋아 만했다. 기억, 당신은이 금요일에 의한 에세이. 그래서, 난 아무도 좋아하지 않는다 알고 중간 고사에 대해 생각하는, 하지만 첫 번째 퀴즈는 10 월 15 일에 10 월에 이번 주에 시작합니다. 그래서, 그것은 빨리 될 수 있습니다 예상보다 전부입니다. 있도록 가드 때를 던져하지 않을 나는, 오, 그 다음 주 부분을 언급 퀴즈 다음 주, 나는 생각했다 나는 더 당신에게 조금 줄 것 지금 머리. 그래서, 문제 설정, 세 번째. 사람들이 읽고 어떻게 호기심 스펙? 확인을 클릭합니다. 우리는 몇 가지를 얻었다. 종류의 아래 마지막에서 그 그러나 주 괜찮아요. 나는 그것이 아름다운 밖으로이었다 알고있다. 그래서 브레이크 아웃. 확실히 완수 후 오늘은 적어도 당신의 스펙을 읽어 다운로드 같은 시도 분배 코드 및 실행 첫 번째 초기와 같은 그들이 당신을 물어 것. 우리가 사용하고 있기 때문에 분배 코드 및 라이브러리 우리는 괜찬 만의 using--했습니다 있음 우리는이 Pset에 짓을했는지 두 번째, 미친 일들이 일어날 수있다 어플라이언스와, 당신은 것을 발견 할 밖으로 지금 이후 대. 이 목요일 밤 또는 경우이기 때문에 수요일 밤과 몇 가지 이유 어플라이언스는하지 않습니다 라이브러리와 실행하려면 또는 분포 코드 수단이 당신은 코딩을하고 시작할 수 없습니다. 당신이 확인할 수 없습니다 때문에 작동하는지 확인합니다. 귀하의하지거야 수 컴파일이 있는지 확인합니다. 당신은 초기에 사람들의주의를 기울여야 할 주, 당신은 아직도 나에게 이메일을 보내 수있을 때 또는 다른 TF들 중 하나, 우리는 고정 된 사람들을 얻을 수 있습니다. 그 때문에 문제는 그 당신을 막을거야 실제 진전에서. 그것은 것으로, 하나의 버그처럼하지 그냥 가지 이상 건너 뛸 수 있습니다. 당신은 문제가 발생하는 경우 기기 또는 배포 코드, 당신은 정말 촬영하고 싶지 조만간 케어입니다. 그래서 심지어 당신이 실제로 원하지하지 않는 경우 코딩을 시작, 배포를 다운로드 코드, 스펙을 읽을 수 있는지 확인 모두가 일하고있다. OK? 당신은 단지 그렇게 할 수 있다면, 쉬울 것입니다 당신의 삶을 약속합니다. 그리고 당신은 아마거야 지금 바로 그것을 할까? 확인을 클릭합니다. 그래서,이 질문? 모든 물류 것들? 모두가 좋아? 확인을 클릭합니다. 들에 대한 면책​​ 조항 당신 방에 온라인. 나는 전환하려고 시도 할거야 기기에서 파워 포인트 사이 우리가 가고 있기 때문에 일부 코딩 일을 할 익명의 호평 오늘 제안 설문 조사는 지난 주에 발송. 그래서, 우리는 몇 가지 코딩을하고있을 것입니다. 그래서 너희들은 원하는 경우 가전​​ 제품을 발사, 당신은 이메일을 가지고 있어야합니다 샘플 파일로, 나에게서. 그렇게 주시기 바랍니다. 그래서, 우리는에 대해 이야기하는거야 디버거 인 GDB. 그것은 당신을 도울 것 종류의 위치를​​ 알아낼 상황이 코드에서 잘못된 것입니다. 정말 당신이 단계를위한 단지 방법 코드를 통해이 일어나고으로, 변수를 인쇄 할 수 또는 실제로 무슨 일이 일어나고 있는지 볼 후드는 프로그램 구절에서 바로 실행, 그것은 오류있는처럼, 당신은, 아니 생각 같아 어떻게 여기 일어났다. 나는에 실패 무엇을 줄 모른다. 잘못 어디로 갔는지 모르겠어요. 그래서, GDB는 그와 함께 당신을 도울 것입니다. 또한,하기로 결정하는 경우 예 계속 61을, 정말, 정말하게 될 수 가장 친한 친구, 나는 당신을 말할 수있는 원인 내가 그 클래스를 통해 갈거야 때문이다. 우리는 바이너리 보는거야 검색, 너희들이 기억한다면 큰 전화 번호부 예 클래스의 광경. 우리는 그것을 구현 될 것이다 조금 더 그 통해 걷고, 그리고 우리는 네 겪고있어 버블 서로 다른 종류의, 선택, 삽입, 그리고 병합합니다. 쿨. 그래서, 내가 언급 GD​​B 같은 디버거이다. 그리고이 큰 종류입니다 일, 큰 기능 또는 명령 당신은 GDB 내에서 사용하고, 나는 걸을 것 당신은 두 번째에서의 데모를 통해. 그래서,이는 아니다 초록 머무를 예정. 나는 시도하고 콘크리트로 만들어 줄게 너희들을 위해 가능한 한. 그래서, 휴식. 이 중 휴식있을거야 같은 일부 수있는 , 당신의 프로그램에서 선을 나타냅니다 또는 당신은 함수 이름을 지정할 수 있습니다. 그래서, 당신은 주 휴식 말한다면, 그것은, 메인에 중단됩니다 당신이 그 기능을 통해 걸어 보자. 마찬가지로, 당신은 어떤 외부가있는 경우 스왑 또는 큐브와 같은 기능을, 우리는 지난 주에에서 본. 당신이 그 중 하나를 깰 말한다면, 프로그램이 명중 할 때마다, 그 그것은에 당신을 기다릴 것이다 무엇을할지 알려준다. 그것은 단지 당신에게 그렇게 실행하기 전에 실제로 함수 내에서 단계 수 그리고 무슨 일이 일어나고 있는지를 참조하십시오. 그래서, 다음, 그냥 건너 뜁니다 다음 라인은 기능을 통해 이동합니다. 단계. 이들은 모두 조금 추상적이다. 그래서, 난 그냥 그들을 통해 실행하는거야, 하지만 당신은 두 번째의 사용을 볼 수 있습니다. 함수로 단계. 같은 그래서 내가 말했듯이, 스왑, 그것은 같은 것 당신은 실제로 당신이있어하는 것처럼 수 같은 물리적 내부 스테핑, 그 변수 당신이 할 수있는 혼란, 인쇄 그들이 무엇인지, 무슨 일이 일어나고 있는지를 참조하십시오. 목록은 말 그대로 그냥 인쇄됩니다 주변의 코드가 부족합니다. 그래서, 당신은 종류의 잊어 버린 경우 당신이 당신의 프로그램에있는 경우, 또는 당신이 궁금해 무슨 일이, 그 주위에 무슨 이 단지 세그먼트를 인쇄합니다 의 주위 대여섯 라인을 좋아합니다. 그래서, 당신이 지향 얻을 수 있습니다 당신이 어디에 있는지에 대해. 일부 변수를 인쇄합니다. 그래서, 당신은 키 등이있는 경우 시저, 우리는 볼 것이다 그. 당신은 어떤 지점에서 인쇄 키를 말할 수 있습니다. 값이 너무 무엇인지는 말해주지 즉, 어쩌면 어딘가에 길을 따라, 당신은 당신의 키를 덮어. 당신은 실제로 때문 말할 수 당신은 실제로 그 값을 관찰 할 수 있습니다. 지역 주민, 바로 인쇄에서 지역 변수가 부족합니다. 그래서, 언제 당신이 루프 내에있어, 당신은 단지 오, 같은보고 싶어요. 내 나는 무엇인가? 이 키 값은 무엇입니까 여기 초기화인가요? 이 시점에서 메시지는 무엇입니까? 그냥 모든 인쇄됩니다 그 중, 그래서 그 개별적으로 필요가 없습니다 인쇄 I. 인쇄 메시지, 말한다. 인쇄 키. 그리고 표시합니다. 무엇 그 일은 당신과 같다 프로그램을 통해 단계, 그것은 단지 그것의 있는지 확인합니다 일부 특정 변수를 표시 모든 점에서. 있도록 괜찬이야 also-- 바로 가기 어디 가지 당신은 오처럼 계속 할 필요가 없습니다. 인쇄 키 또는 인쇄 I. 그것은 단지 당신을 위해 그것을 자동으로됩니다. 그래서, 그와 함께, 우리는거야 이 어떻게되는지 확인합니다. 나는 시도하고 스위치거야 내 기기에 이상. 나는이 작업을 수행 할 수 있는지. 모든. 우리는 그것을 반영하는 것입니다. 미친 아무것도 없어 내 노트북​​에 어쨌든. 확인을 클릭합니다. 이것은이 하나가 될 필요가있다. 너무 작은입니다. 우리는이 작업을 수행 할 수 있는지 보자. 확인을 클릭합니다. 앨리스는 분명 어려움을 겪고 여기 조금, 그러나 우리는 추억 일에를 얻을 수 있습니다. 확인을 클릭합니다. 우리는 단지이 증가 할 것입니다. 확인을 클릭합니다. 모든 종류의를 볼 수 있습니까? 어쩌면 조금? 나는 그것이 조금 작은 알고. 당신은 확실히 알아낼 수 없습니다 이 큰 만드는 방법. 누구나 알고있는 경우. 사람은 더 크게 만들 방법을 알고 있나요? 확인을 클릭합니다. 우리는 롤 것입니다. 그냥 있기 때문에 어쨌든 상관 없어 그는 너희들이해야하는 코드의 가. 무슨 일이 더 중요 여기서 단말기이다. 그리고 우리는 왜 이렇게 작은 여기가? 설정. 오. 진정한 아이크. 이 어때요? 거기에서. 그 모두를위한 더 나은가요? OK ,. 쿨. 당신이 CS에있을 때 당신은 알고있다 클래스 기술적 인 문제 엥 종류의 일부입니다 그래서,이 선택을 취소 할 수 있습니다. 확인을 클릭합니다. 그래서, 여기 섹션에서 이는 우리가 여기에 있었다. 시저는 실행 파일입니다. 그래서 나는 그것을했다. 그래서, GDB와 함께 실현하기 위해 한 가지입니다 그것이는 실행 파일에서 작동합니다. 그래서, 당신은 dotsy에서 실행할 수 없습니다. 당신은 실제로 확인해야 코드를 컴파일해야, 및 실제로 실행될 수있다. 그렇지 않은 경우에 따라서, 확인이 있는지 확인 컴파일은 컴파일에 도착, 그래서 당신은 종류의 그것을 통해 실행할 수 있습니다. 그래서, GDB를 시작, 모든 당신이, 글로리아 유형 GDB 한 다음 바로 당신이 원하는 그 파일. 나는 항상 시저를 잘못 입력. 하지만 당신이 있는지 확인하려면 이 실행 파일이기 때문에, TI의 도트 플래시 있도록 당신이 거란 뜻 CSI는 당신이 실행하는거야 실행 이 디버거를 파일. 확인을 클릭합니다. 그래서, 그에게, 당신은 어떻게해야합니까 횡설수설의이 종류. 이 디버거에 대한 그냥 모든 일을합니다. 당신은 정말 필요가 없습니다 지금 걱정. 보시다시피, 우리는이가 열린 괄호, GDP, 가까운 괄호, 그냥 가지처럼 보이는 우리의 명령 줄, 오른쪽? 그래서, 우리는하더라도 - 무엇을 할 --So, 먼저 우리가 선택 할 것입니다 장소는 그것을 깰 수 있습니다. 따라서, 하나의 버그가 있습니다 이 시저 프로그램 나는 그를 소개하는 것이 우리는 알 것입니다. 그것은 입력을 걸립니다은 무엇입니까 모두 대문자로 Barfoo, 일부 이유 그것은 단지 잎 A. 변경되지 않습니다 혼자서는 올바른 모든 것들인가 하지만 두 번째 편지 은 변경되지 않습니다. 그래서, 우리가 시도하는거야와 그 이유를 알아. 그래서, 제일 먼저 당신이 일반적으로 당신이 GDB를 시작할 때마다하고 싶은 그것을 깰 위치를 알아낼 수 있습니다. 그래서 카이사르는 꽤 짧은 프로그램입니다. 우리는 바로, 하나의 기능이? 시저에 우리의 기능은 무엇입니까? 하나의 기능, 홈페이지 바로이있다? 주요 기능입니다 모든 프로그램. 당신이 주를 가지고 있지 않은 경우, 나는 수도 걱정 조금 지금 수, 하지만 난 당신이 모두 거기에 홈페이지를 가지고 있기를 바랍니다. 그래서, 우리가 할 수있는 것은 우리는 할 수있다 그냥 그렇게, 홈페이지를 휴식. 그래서, 그것은 확인을 말한다. 우리가 우리의 브레이크 포인트를 설정합니다. 그래서 기억하는 지금 것은 시저입니다 한 줄에 하나의 명령 인수 권리를합니다 우리는 어디 아직 수행하지 않은. 그래서, 당신이 무엇을 할 때입니다 당신은 실제로 실행으로 이동 프로그램, 당신이있어 모든 프로그램 GDB에서 실행하는 명령 줄 필요 인수는, 당신은 입력에 갈거야 때 먼저 실행을 시작. 그래서,이 경우에, 우리가 할 세 가지의 키를 실행합니다. 그리고 실제로 시작됩니다. 당신이 여기에서 보는 경우에 따라서, 우리는이 RC는이 동일하지 않은 경우. 그래서 너희들이 모두있는 경우 나는까지 보내 해당 파일 당신은이처럼 것을 볼 수 있습니다 첫 번째 줄 우리의 주요 기능, 오른쪽? 그것은 우리가되어 있는지 확인하는 것 올바른 수의 인수. 그래서, 당신이 궁금해하는 경우 RC가 맞으면 당신은 인쇄 RC과 같은 작업을 수행 할 수 있습니다. RC는 인 2 개인 우리는 권리를 기대했던? 그래서, 우리는 다음을 갈 수 있습니다, 과를 통해 계속합니다. 그래서, 우리는 몇 가지 키가 있습니다. 그리고 우리는 우리의 키를 인쇄 할 수 있습니다 맞습니다 확인합니다. 흥미 롭군요. 그렇진 우리가 기대했던 것. 그래서, 한 가지 실현 또한 GDB와,입니다 당신이 실제로 나오기 전까지는 아니라고 다음, 당신이 방금 본 라인 실제로 실행됩니다. 그래서,이 경우 키에 아직 할당되지 않았습니다. 그래서, 키는 일부 쓰레기 값이다 당신은이 바닥에서 볼 수있다. 마이너스 $ 120-- 괜찬의 억 뭔가 이상한 것 맞죠? 우리가 예상 키 아니다. 그러나 우리는 다음을 명중하고, 만약 우리 시도 및 인쇄 키, 그것은 세 가지입니다. 모두가 그 볼? 그래서, 당신이 뭔가를 얻을 경우 당신은 같은 걸 기다립니다. 이것은 완전히 잘못된, 그리고 나도 몰라 나는 모두가 원하기 때문에 이런 일이 발생하는 방법 번호를 할당 할 일은, 변수, 인쇄를 시도, 다음을 타격하려고 그것이 작동하는 경우는 다시 볼. 그것은 단지 실행할 것 때문에 실제로 한 후 뭔가를 할당 다음을 누르십시오. 모두 이해가? 어 어? 스피커 2 : 때 임의 숫자 그게 무슨 뜻 이죠? 스피커 1 : 그것은 무작위입니다. 그냥 쓰레기입니다. 그냥 뭔가 귀하를 컴퓨터가 무작위로 할당합니다. 쿨. 지금 우리는을 통해 이동하고, 그렇게 할 수 있습니다 지금 우리는이 일반 텍스트하여 GetString 있습니다. 그래서, 내가 그냥 소개하겠습니다 무엇 우리가 여기에서 다음을 명중 할 때 발생합니다. 우리 GDB는 종류의 권리, 사라? 즉하여 GetString 때문이다 지금 실행, 권리? 우리가 본 때, 일반 텍스트 같음 하여 GetString, 열린 괄호 및 괄호, 우리는 다음을 명중, 그이 실제로 지금 실행. 그래서, 기다리고 입력 뭔가 우리. 그래서, 우리는 입력에 우리 음식을려고하고있는 내가 말했듯이 실패 무슨이다 그리고 그냥 있다고 말한다 폐쇄 것으로, 실행을 종료 브래킷은 뜻 그 루프에서 종료. 난 그래서, 우리는 이제 다음을 명중 할 수 있습니다 당신이 시저에서 익숙한 모든 것, 이것은 할 예정이 줄을 무엇이다. Int 인 I가 0에 해당위한 그것의, N은 동일 STRLEN, 일반 텍스트, 다음 나는 N, I, 플러스, 플러스보다 작습니다. 할 예정이 루프는 무엇입니까? 당신의 메시지를 엽니 다. 쿨. 그래서, 그 일을 시작하자. 그래서,이 조건은해야 우리의 첫 번째에 대한 일치? 이 B가 있다면, 그것은 일반 텍스트 I.의 우리의 우리의 지역 주민에 대한 정보를 얻을 수 있습니다. 그래서, 제로, 그리고, 여섯 경우 어떤 우리는 기대하고, 우리의 핵심은 세 가지입니다. 이해가 그 모든, 맞죠? 그 숫자는 모두 정확하게 숫자. 그래서, 콧노래? 스피커 3 : 내가 가지고있는 광산 임의의 숫자. 스피커 1 : 글쎄, 우리가 --we을 check-- 수 있습니다 두 번째에서 그것에 대해 대화를 나눌 수 있습니다. 그러나이 점점해야합니다. 그래서, 우리는 자본이있는 경우 우리의 첫 번째에 대한 B, 이 조건은 바로, 그것을 잡을해야합니까? 우리는 다음을 공격한다면, 우리는 참조 이 경우 실제로 실행하는. 당신은 다음과 같은하면 ... 코드에 따라, 여기이 선 여기서 일반 텍스트 I 이 연산으로 대체됩니다, 만하면 경우에 실행 가 정확한 권리인가? GDB는 당신을 보여줄 것입니다 실제로 실행되고있는 것. 이 경우 조건이 충족되지 않은 경우 그래서, 그것은이다 바로 다음 행으로 건너 것. OK? 그래서, 우리는 그것을 가지고있다. 이 브래킷은 그것의 의미 지금 루프에서 마감했다. 그래서, 다시 시작하는 것입니다. 그냥 그렇게. 그래서, 우리는 정보를 얻을 수 있습니다 여기에 우리의 지역 주민에 대한, 우리는 우리의 첫 번째 볼 편지는 바로 바뀌 었습니까? 그것이 있어야하는 것처럼, 지금은 E이다. 그래서, 우리는 계속 할 수 있습니다. 그리고 우리는이 검사를해야합니다. 그리고이 검사는 바로 작동해야합니까? 그것이 변경되어야 A.있어 앞으로 세 글자. 하지만, 우리가 나는 경우 다른 무언가를 얻을. 여기에이 경우 최대의 그래서, 발견 그것은, 그래서이 라인은 실행 우리의 B를 수정하는 그러나, 여기서이 경우, 우리는 그냥 건너 뛴 것을 가지고, 그리고 [갔다? 패 시프. ?] 그래서 뭔가가 일어나고. 무슨 그게 당신을 말하고있다, 우리는 여기에 잡을 것을 알고 하지만, 그렇지는 않습니다. 사람이 무엇을 볼 수있는 우리의 문제는 그 라인에? 그것은 매우 분 일입니다. 그리고 당신은 또한 당신의 코드를 볼 수 있었다. 또한 그것이 무엇인지 라인 잊지 한테 들었 냐 것 저기에 있지만 [들림]에 있습니다. 네? 스피커 4 : 그것은보다 큰에의 페이지 당신은 책을 읽을 경우. 스피커 1 : 맞아요. 그래서, 디버거는 말할​​ 수 없습니다 당신,하지만 디버거 라인에 당신을 얻을 수 당신이 작동하지 않는 것을 알고. 그리고 가끔, 경우에 특히 나중에 학기에 당신은 백, 상대하고 몇 백 줄의 코드, 그리고 이 실패 어디에 모른다, 이 그것을 할 수있는 좋은 방법입니다. 그래서, 우리는 우리의 버그를 발견. 당신은, 당신의 파일에 문제를 해결할 수 다음은, 다시 실행할 수 있습니다 모든 것이 완벽하게 작동합니다. 그리고 가장 큰 것입니다 이 확인을, 같은 보일 수있다. 그래. 쿨. 당신은 당신이 찾고있는 것을 알고 있었다. 그래서, 당신은 무엇을 알고 있었다. GDB는 당신 때문에 매우 도움이 될 수 있습니다 이 모든 일을 인쇄 할 수 있습니다 당신 하지 않을 것이다. 그것은 훨씬 더 유용 printf의 이상입니다. 얼마나 많은 사용의 PRINTF 문 등 버그가 오른쪽 어디에 알아낼? 그래서,이, 당신은하지 않습니다 다시 계속해야, 과에 주석처럼 PRINTF는, 또는, 주석 밖으로 무슨 생각하는지 당신은 인쇄를해야합니다. 이것은 실제로 단지을 수행 할 수 있습니다 , 단계별 물건을 인쇄 당신이 겪고로, 그래서, 당신은 할 수 그들이 실시간으로 변경하는 방법을 관찰, 당신의 프로그램으로 실행됩니다. 그리고 그것은 조금 걸리나요 익숙해의 비트. 내가보기 엔 그냥 종류 추천 의 그것과 조금 짜증나는 지금 당장. 당신은 이상 시간을 보내는 경우 다음 주 방법 GDB를 사용하는 학습, 당신은 자신을 절약 할 수 나중에 너무 많은 시간. 그리고 말 그대로. 우리는 이야기 이 사람들에게 매년, 내가했다 때 기억 클래스, 내가 잘 될 것 같았다. 아니오. PSET 6에 와서 내가했다 같이, 나는 거 배우고 있어요 내가하지 않기 때문에 GDB를 사용하는 방법 여기에 무슨 일이 일어나고 있는지. 그렇게 시간이 걸릴 경우에 따라서 작은 프로그램에서 사용할 당신은 할 거라고 작업과 같은 작업 같은 통해 이 같은 Visionare. 당신은 여분의 연습을 원하신다면, 나는 확신 나는, 버그 프로그램을 마련 할 수 당신이 원하는 경우에 당신은 디버깅하는 방법. 하지만 시간이 좀 걸릴하다면 얻을 수 그것을 사용, 그냥 놀러, 정말 당신을 잘 될 것입니다. 그리고 정말 중 하나 그런 것들을 당신 단지 시도해야하고, 손이 더러워 당신이 정말로 그것을 이해하기 전에,와. 정말 한 번만 이해 나는 그것으로 디버그 것에했다 그것은의 아이디어가 훨씬 좋네요 방법 조만간 디버깅하는 방법. 확인을 클릭합니다. 쿨. 난 그 가지처럼 알고 GDB의 충돌 과정, 나는 확실히 얻기에 작동합니다 이들은 더 큰 다음에 찾을 것이다. 쿨. 그래서, 우리는 우리 파워 포인트로 이동합니다. 이 작동하는거야? AWH. 예. 확인을 클릭합니다. 그래서, 당신은 중 하나를 필요로하는 경우 그 다시 목록이있다. 그래서 이진 검색, 어떤 사람 다윗의 위대한 광경을 기억 반 전화 번호부를 리핑. 정말 얻​​을하지 않습니다 더 이상 전화 번호부, 당신을 어디에 좋아하기 때문에 요즘 전화 번호부를 얻을 수? 난 정말 모르겠어요. 이진 검색. 기억하는 사람이 어떻게 이진 검색 작품? 누구나 모든? 그래? 스피커 5 : 당신은 때를 알기 당신은 절반보고 그것은 그 바탕으로,에있을 것입니다, 나머지 절반 없애. 스피커 1 정확히. 그래서, 이진 검색, 그것의 치아는 종류의 --we는 분할과 정복 전화를 좋아한다. 그래서, 당신은 무엇을 할 거 야입니다 당신은 중간에 볼 것이다 일치하는 경우 당신은 볼 것이다 당신은 무엇을 찾고 있습니다. 그렇지 않은 경우에, 당신은에 시도 알아, 그것은 남아있을 것입니다 반 또는 오른쪽 절반. 당신이 찾고 있다면 그래서,이 될 수 있습니다 알파벳순으로 뭔가에, 당신은 오, 참조하십시오. 앨리슨 M 앞에 와야합니까? 예. 그래서, 우리는에 갈거야 상반기 봐. 아니면 숫자와 같은 수 있습니다. 아무것도 당신이 할 수 비교, 그것은 정렬 할 수 있습니다. 당신은 이진 검색을 사용할 수 있습니다. 그래서, 사람이 기억 그래프 나이 무엇인지? 그것은 점근 복잡성이다. 그래서,이 그래프 단지 얼마나 설명 그것 같은 문제를 해결하기 위해 소요 당신은 사물의 수를 늘릴 것을 당신이 사용하고 있습니다. 그래서, 우리는 선형 시간 N을 보유하고 있습니다. 약간 명 이상의 N, 만약 더 나은 여전히​​ 슈퍼 빠른 성장한다. 그리고 우리는 인, 로그인 한 우리는 이진 검색을 고려하십시오. 우리는 통지하는 경우, 문제로 훨씬 훨씬 커질수록 당신 걸리는 시간은 그것을 해결하기 위해 정말 많이 증가하지 않습니다. 그것은 비교처럼 여기에 처음에. 당신은 OK, 같은거야. 아무것도 여기 정말하지 않습니다 문제있는 우리가 사용 하나, 하지만 당신은, 백만 억 나가. 당신이 알아서 이겨낼을 찾기 위해 노력하고 건초 더미에서 바늘을 찾기 위해 노력. 나는 당신이이 문제를하려는 생각합니다. 이 복잡​​성,하지를 원하는 선형 때문에 모두를위한 당신 당신 거를 통해 검색 할 수 알고 각각의 바늘, 건초의 것, 당신의 바늘을 찾기 위해 노력. 그리고 내 생각에 너무 재미 아니다. 나는 빨리 좋아합니다. 나는 효율적인 좋아한다. 하고 근면 한 학생에게 얘들 아, 당신이 효율적으로 작업 알고 있습니다 더 단단한 유형 것, 방법을 이러한 알고리즘을 만들 수 있습니다. 그래서, 우리는 걷는거야 그냥 빨리 예를 통해. 나는 너희들이해야한다고 생각 이진 검색에 손, 하지만 경우에 사람이 조금이다 퍼지, 그것은을 강화하려면, 우리는 그냥 갈거야 다음 예를 통해. 경우에 대한 그래서, 우리는 찾고 배열은 일곱이 포함되어 있습니다. 그래서, 우리가 먼저입니다 오른쪽 중간에 보여? 또한 당신은 코딩 할거야 잠깐의 이진 검색. 그래서, 재미있을거야. 그래서 우리는 봐 중간 작은 배열 3. 3 7과 동일합니까? 하지 않습니다. 그것은 여섯입니다. 그래서보다 덜입니다 , 7보다 큰? 이하. 예. 멋진 작업들. 나는 내가해야 같은 느낌 사탕을하기 때문에이 I 야드로 던져 싶어요. 내가 다음 주에 할 예정이다거야. 그것은 날카로운 너희들을 유지합니다. 그래서, 우리는 멀리 던져 상반기, 맞죠? 그것보다 작습니다. 우리는 모든 것을 알고있다 그 좌측 이하로 무슨 일이 일어나고 있는지 우리가 실제로 찾고 있습니다. 그래서, 필요에가 없습니다 여기에주의를 기울이십시오. 그냥 잊어 버려요. 지금 우리는 우리의 오른쪽에 보면, 우리는, 거기 중간보고 지금은 아홉이다. 그래서, 9는 ... --Everyone? 우리가있어 무엇보다 큼 오른쪽을 찾고? 그래서, 우리는 던질거야 오른쪽으로 멀리 모든 것을. 그처럼. 이제 우리 모두는 하나입니다 남습니다. 그래서 우리는 확인,이 무슨 우리는을 찾고? 그 것이다. 우리는 우리가 원하는 것을 발견했다. 그래서 우리는 완료. 이중 선형 검색합니다. 그리고 당신은, 우리가 나는 경우 이 일곱 입력을했다. 그것은 단지, 세 번처럼 우리를 데려 갔다 하지만 10 억과 같은 일을하는 경우, 너희들은 얼마나 많은 단계는 것 알고 우리가 사십억 일이 있다면 걸릴? 모든 추측? 그것은 32입니다. 무언가를 찾기 위해 32 단계 40 억 (4 billion) 때문에 두 힘의 요소는 배열입니다. 그래서 두 사람은 32에 4 개의 억입니다. 그래서 아주 미친 어떻게 당신은 여전히​​ 내거야 단계 상당히 적은 수의 추천 뭔가를 찾을 수 사십억 요소. 그 메모 그래서, 우리는있어 이 코딩 것 그래서 너희들은 실제로 수 종류의이 작업을 수행하는 방법을 참조하십시오. 좋아, 너희들은 코딩 할 수 있습니다. 나는 너희들에게 할거야 조금에 대한 이야기​​. 인, 당신의 주위에 사람들을 알아 어떤 사람은 마지막 부분에서 원. 그래서 주변 사람들을 알고. 조금에 대한 이야기​​. 그리고 모든 당신에서 원하는 사람들은 지금은 그냥 의사의 개요를 만들어보십시오. OK? 우와. 나는 당신들 원하는 건 당신이있어입니다 그냥이 동안 케이스를 기입 것. 그래서 나는이 상을 설정 한 낮은 경계하는 시작을 나타냅니다 우리의 배열과 끝. 그리고 당신은 실제로 건가요 루프를 통해 파악 우리는이 while 루프 내에서 일을하고 있습니다. 당신이 병원을 나온 파악할 수 그래서 만약 내가 가진 경우이 무엇인지 저기 힌트 것을 우리는 여기에있다? 당신이 알아낼 싶다면 경우, 우리는 사람들을 의사됩니다 그리고 우리는 실제로 코딩합니다. 그리고 그것은있을거야, 나는 희망이거야, 생각 예상보다 좀 더 쉽게합니다. 그것은 그 많은 코드 아니기 때문에 실제로, 이는 정말 멋지다. 으흠? 학생 : [들리지? 강사 : 네. 뭔가가 있었다 중간에 찾을 수 있습니다. 학생 : 그래서 우리가 그것을 사용할 수 있습니다. 확인을 클릭합니다. 강사 : 완벽한. 그래서 우리가해야 할 첫 번째 일입니다. 그래서 중간을 찾을 수 있습니다. 그레이트. 그래서 당신의 아이디어가 어떻게 우리는 수도 실제로 코드로 중간을 찾기? 학생 : 네. 2 이상 N? 강사 : 그래서 n은 2 이상. 그래서 기억해야 할 한 가지가 있다는 것입니다 당신의 상한과 하한이 변경됩니다. 우리는 부분을 죄기 계속 배열의 우리에 찾고 있습니다. 그래서 n은 2 이상에만 작동합니다 가장 먼저하는 일을 위해 우리가 할. 그래서 고려 상하 복용 우리는 어떻게 그 중간 요소를 얻을 수 있는가? 우리는 중간을 원하기 때문에 상단과 하단, 우측 사이? 으흠? 학생 : [들림]. 강사 : 그래서 우리는 몇 가지 중간이있다. 그리고 상단 플러스 2 이상 낮은 것이다. 신난다. 우리가 이동합니다. 한 줄 아래로. 당신들은 당신의 방법에 있습니다. 그래서 지금 우리가 가지고 중간, 우리는 무엇을 하시겠습니까? 그냥 일반적으로. 당신은 그것을 코딩 할 필요가 없습니다. 예. 학생 : [들리지? 강사 : 그래서 그건 당신 플러스이기 때문에 둘 사이의 평균을 찾는 그들 중. 그래서 당신은 같은 종류의 그들을 생각한다면 측면에서의 증가, 당신이 접근 할 때 그것에 대해 생각 중간, 당신은 그렇게 할 수 있습니다. 그래서 만약 당신이 양쪽에 있었다 중, 우리는 5, 7과 같이 있습니다. 당신은 당신을 함께 추가 할 때 (12)을 얻을, 당신은 2 분할, 6입니다. 때로는 어렵다 그 작동 이유를 설명, 하지만 당신은을 통해 작업하는 경우 예를 들어 때때로, 당신이 있는지 알아내는 데 도움이됩니다 그것은 플러스 또는 마이너스해야한다. 예. 학생 : [들리지] 정확히 중간에 그들은 어디에 경우가 있다면 작은 숫자가 많이있다 한 많은 수의 같은? 강사 : 그래서 모든 당신이 필요로하는 어레이의 중간이다. 그래서 만약 당신이 소수의 무리가 있었다 다음 하나 정말 많은 수의 끝에서, 그것은 중요하지 않습니다. 모든 문제가 있다는 것입니다 그들은 방금 분류하고 중간보고 싶지 배열 여전히이기 때문에 반 문제를 슬라​​이스. 쿨. 그래서 지금 우리가이 것을 중간, 우리는 다음에 무엇을해야합니까? 학생 : 비교. 강사 : 비교. value_wanted에 따라서 중간을 비교합니다. 쿨. 그래서 우리가 여기에 참조 우리가 여기에 원하는이 값. 이 배열입니다 기억하십시오. 그래서 중간 인덱스를 의미한다. 그래서 우리는 중간의 값을 싶어요. 당신이 원한다면 잊지 마세요 두 번 같음을 비교. 당신은 하나의 당신이있어 동일 할 그냥 재 할당 할 것, 하고, 물론, 이건 원하는 값이 될 것이다. 그래서 그렇게하지 ​​않습니다. 그래서 우리는 있는지거야 중간에있는 값 우리가 원하는 값과 같습니다. 교정기를 잊지 마십시오. 드롭 박스는 멀리 가야한다. 그래서 우리는이 경우 어떻게해야합니까? 우리가 반환 원하는 작업이라면? 우리가 말하고자하는 것입니다. 학생 : 떨어져 인쇄. 강사 : 글쎄, 우리 오프 인쇄하지 않습니다. 그래서 여기에 부울이며, 우리 때문에 true 또는 false를 반환하고 싶습니다. 우리는이 숫자가, 말을하는지 [? RRA? ?] 그것이 그렇다면, 우리는 단지 사실 반환합니다. 나는 사실 철자 수 있습니다. 학생 : 왜 당신은 0을 반환하지 않을까요? 강사 : 당신이 수 있도록 당신이 원하는 경우 0을 반환. 그러나이 경우 때문에에 우리의 함수는 BOOL을 반환 우리는 참 또는 거짓 반환해야합니다. 학생 : 때 당신이있어 부울 식을 말 당신은 거짓과 동일하게 설정 할 수 있습니까? 내가 말하고 싶은 경우에, 만약이 조건처럼 상단 거짓 같다처럼, 충족되지. 그냥 경우는 이해할 수 다른 측면에서 거짓 넣어? 강사 : 네. 그래서 실제로 당신이 있다면 지금까지 일을 같은 상부 또는 낮은, 즉 true 또는 false를 반환 그리고 실제로 나쁜 스타일이다 말은 동일 true 또는 등호와 동일 거짓과 같습니다. 당신은 그 결과를 사용하려면 수표로 자체. 내가 원하지 않는 것을. 그게 내가 원하는거야. 요구하고 당신의 경우에 따라서 뭔가에 대해 같은 C이 저장합니다. 그래서 우리는 INT 주 (무효)가있는 경우 이 같은. 위 경우 그리고 당신은 당신이있어 일부 입력의 당신이 할 수있는 여부를 묻는 이런 식으로 뭔가? 오른쪽? 학생 : 제가 노력했다 그것은 [들림] 할 수 있습니다. 그건 ... 만약 때문에 강사 : 오른쪽. 그래서 당신이 바로 거짓되고 싶어? 학생 : 네. 강사 :이 경우에 따라서 그것은 사실이 아니에요 경우 실행하고자. 그래서 당신이 할 좋은 점은 이것이다. 그래서 느낌표 기억 포인트는 물건을 부정? 그것은 [들림]하지 의미 말한다. 우리가 보면 그래서 여기이 부분, 단축형 즉 평가라고 거짓 당신이 원하는대로. 거짓 없음은 사실이다 이 실행할 것을 의미한다. 그 의미가 있습니까? 학생 : 네. 강사 : 신난다. 확인을 클릭합니다. 그래서 우리는 반환 할 수 이 경우 사실. 그래서 지금 우리는 다른 두가 이 경우 경우. 우리의 두 개의 다른 경우는 무엇인가? 그냥 이런 방식을 보자. 그래서 다른 시작하자 만약 중간에 값 우리가 원하는 값보다 작습니다. 그래서 중간에 우리의 값이 작 우리가 찾고있는 값보다. 그래서 결합하는 당신을 우리가 업데이트 할 생각? 상부 또는 하부? 위? 배열의 그래서 어느 쪽 우리가보고 될 것입니까? 학생 : 내립니다. 강사 : 우리는 우리가 가고있다 왼쪽을보고합니다. 작은 값이 작은 경우, 그래서 다른. 여기 중간 값 그래서 우리가 원하는 것보다 작습니다. 그래서 우리는 먹고 싶어 우리의 배열의 오른쪽. 그래서 우리는에 갈거야 우리의 하한을 업데이트합니다. 그래서 우리는 우리의 낮은 재 할당 할 수 있습니다. 그리고 당신은 낮은이 있어야한다 어떻게 생각하세요? 학생 : 중간 값? 강사 : 그래서 중간 value-- 학생 : 플러스 1. 강사 : --plus 1. 아무도 이유를 말해 줄 수 우리는에 1을 더한 있나요? 학생 : [? 값 없다?] 그것은 더 같다. 강사 : 오른쪽. 우리는 이미 알고 있기 때문에 우리의 중앙값이 동일하지 그것을 우리는 그것을 제외 할 이후의 모든 검색에서. 당신은 플러스 1,이를 잊어 버린 경우 무한 루프 같은 것입니다. 그리고 당신은 단지에 잡힐 것 무한 루프 다음​​은 세그 폴트합니다 사물이 나쁜 이동합니다. 그래서 항상 당신이 아니라는 걸 확인 값을 포함 당신 단지 바라 보았다. 그래서 우리는 플러스 1로 그주의하십시오. 그래서 지금 우리는 우리의 마지막 조건이 안전을 위해하는 항상 I 당신은 값의 경우 다른, 여기에서 확인할 수 있습니다 중간 값보다 큰 우리는 할 수 있습니다. 즉 우리가 원하는 것을 의미한다 왼쪽 절반. 그래서 어느 것은 우리가 업데이트하는 건가요? 어퍼. 평등 한 것이 하나는 무엇인가? 중학교 1을 뺀 때문에 물론, 우리는 원하는 우리가 아니라는 걸 확인합니다 다시 그 중간 값을 찾고. 그리고 우리는 그것을 가지고있다. 이게 다예요. 즉 모든 이진 검색이 있습니다. 그것은 바로, 그 나쁘지 않아? 그것은 10 선처럼 공백 코드. 그래서 매우 강력하고 매우 유용합니다, 당신은 것입니다 당신의 이상 psets를 중 하나를 사용합니다. 아마이 하나,하지만 나중에. 그래서 알아. 그것을 사랑 해요. 그것은 당신을 잘 처리합니다. 그래서 사람이 어떤이 있는가 이진 검색에 대한 질문? 예. 학생 : 그것은 중요합니까 당신의 n은 짝수 또는 홀수 여부? 강사 : 호 우리는 다음과 같이 중간에 캐스팅 때문에 INT, 그냥 그것을 자릅니다. 이 정수를 유지하고 있도록 그것은 것 결국 모든 것을 통해 정렬 할 수 있습니다. 그래서 당신은 그것에 대해 걱정할 필요가 없습니다. 모두 좋은? 신난다. 쿨. 그래서, 너희들이있어. 슬라이드 쇼. 우리는에 대해 얘기했다 그래서, 나도 알아 다윗은 복잡성 런타임을 언급했다. 따라서 최상의 경우에는, 단지 우리는 일정 시간에 전화 하나. 그는 될 수있는 사람이 왜 나를 알 수 있습니까? 그 시나리오의 어떤 종류를 수반 할 것인가? 그래 그래. 학생 : [들리지] first-- 강사 : 중간이되고 그래서 우리는에 와서 첫 번째 요소, 맞죠? 그래서 하나의 어레이 있거나 무엇이든 우리가 찾고있는 중간에 헤로인 소량으로 발생합니다. 그래서 우리의 가장 좋은 경우입니다. 당신은 아마, 실제 문제가되지 얻을 그 종종 [들림]에 도달하는 것이다. 무엇 우리의 최악의 경우는 어떻습니까? 우리의 최악의 경우는 로그 N입니다. 그리고 그 전체를 함께 할 수있다 내가 이야기 두 가지의 힘. 그래서 최악의 경우는 뜻 우리는 아래로 배열을 절단해야했다 그것은 하나의 요소가 될 때까지. 그래서 우리는 반으로 자르게했다 우리가 가능성이있을만큼. 이 로그 N 때문에 이유입니다 당신은 두 가지로 나누어 보관합니다. 그래서 가정, 이것은 당신에게 혹시 있다면 알 필요가 이진 검색을 사용하려고합니다. 귀하의 요소를 정렬해야합니다. 그들은 때문에 정렬 할 수있다 그 유일한 방법이다 만약 수 있는지 알 수 그것의 절반을 던져. 이 뒤죽박죽 가방이 있다면 숫자의 당신은, 말을하는지 좋아, 내가 중간을 확인하는거야 수와 내가 찾고 수 보다 작은, 난 그냥 갈거야 임의의 절반을 던져. 당신이 알고하지 않을 당신의 다른 반 번호. 귀하의 목록에 정렬​​ 할 수 있습니다. 뿐만 아니라,이있을 수 있습니다 앞서 조금 것, 하지만 당신은 랜덤 액세스가 필요합니다. 당신은 할 수 있어야합니다 단지 그 중간 요소로 이동합니다. 당신이 통과해야하는 경우 뭔가를 통해 또는 당신 추가 단계를 수행 그 중간 요소에 도착, 이 로그 N 때문에 더 이상 아니에요 당신은 그것으로 더 많은 작업을 추가하는 것입니다. 그리고 이것은 조금 것 2 주 더 의미, 하지만 난 그냥 가지, 서문 싶어 너희들에게 무엇의 아이디어를 제공 올. 그러나 그것들은 두 가지 중요한 가정 당신은 이진 목록 필요. 이 분류하는지 확인하기. 즉에 대한 큰 하나 당신이 지금 사람. 그리고에 우리는에 갈 수 있습니다 우리의 종류의 나머지. 그래서 네 sorts-- 거품, 삽입, 선택 및 병합. 그들은 멋진 모든 종류의 것입니다. 너희들이 CS 124 걸릴하기로 결정하는 경우, 당신은 종류의 모든 종류에 대해 알아 보겠습니다. 그리고 당신은 XKCD 팬이라면,이 정말 멋진 만화 약이다 정말 효과 종류, 좋아하는 어떤 I 보기 엔 당신이 보는 것 좋습니다. 그 중 하나는 공황 종류, 같은 거 같은, 오 아니, 임의의 배열을 반환합니다. 종료 시스템. 둡니다. 그래서 엽기 유머는 항상 좋다. 그래서 사람이 종류의 기억 않습니다 그냥 일반적인 생각처럼 버블 정렬이 작동하는 방법. 당신은 기억? 학생 : 네. 강사 : 그것을 위해 이동합니다. 학생 : 당신이 겪고 있도록 그것이 더 큰 경우에, 당신은 두 가지를 교환합니다. 강사 : 그래 그래. 정확히. 그래서 그냥 통해 반복. 두 번호를 확인. 하나 전에 크면 이후보다, 당신은 단지에 있도록 그들을 교환 이 방법으로 더 높은 숫자의 모든 목록의 끝으로 거품까지 모든 번호가 낮은 거품 아래로. 그는 멋진 너희들을 보여 주 었는가 비디오를 정렬 효과를 소리? 그것은 멋진 가지입니다. 로버트가 말한대로, 알고리즘 그래서 당신이 목록을 단계 것을, 인접한 값을 교환 그들은 순서대로하지 않으면. 그리고 그냥 계속 반복 때까지 당신은 어떤 스왑을하지 않습니다. 그래서 나쁜, 맞죠? 그래서 우리는 여기에 간단한 예제가있다. 그래서이 정렬하는 것입니다 오름차순으로 그들. 그래서 우리는 첫 번째 통과 할 때 시간, 우리는 팔을 통해 보면 여섯 분명하지 않습니다 위해, 우리는 그들을 교환합니다. 그래서 다음 하나 봐. 여덟 위해 네 없습니다. 그들을 교환합니다. 그리고 팔과 두 그들을 교환합니다. 우리가 이동합니다. 그래서 첫 번째 패스 후, 당신 알고있는 가장 큰 수 모든 방법이 될 것입니다 그냥 있기 때문에 상단에 계속 될 것 다른 모든 것들보다 더 큰 그리고 그것은 단지 거품에 무슨 이 말에 모든 방법까지. 즉 모든 사람에게 의미가 있습니까? 쿨. 그래서 우리는 우리의 두 번째 패스를 봐주세요. 식스 네, 스위치. 여섯 개의 스위치. 그리고 지금 우리는 순서대로 몇 가지가있다. 모든 패스 그래서 우리 우리의 전체 목록을 확인, 우리가 알고있는 그 많은 숫자 같은 마지막에 분류 된 것입니다. 그래서 우리는 세 번째 패스를 수행 어느 스왑입니다. 그리고 우리의 네 번째에 우리는 제로 슬롯이, 전달합니다. 그래서 우리는 알고 우리의 배열 정렬되었습니다. 그리고 그 큰 거품 정렬과 일. 우리는 알고있을 때 우리를 그 그 제로 스왑이 모든 것이 의미 완전한 순서입니다. 우리가 확인하는 방법 가지입니다. 그래서 우리는 또한 거품을 코딩 할 예정 정렬하는 또한 나쁘지 않다. 이들 중 어느 것도 나쁘지 않습니다. 나는 그들이 조금 무서운 보일 수있다 알고있다. 내가 갔을 때 나는 알고있다 클래스, 심지어 때 의 클래스를 가르치고 있었다 처음으로 작년에, 내가 좋아하는, 어떻게해야합니까했다? 이는 이론적으로 의미가 있지만 우리는 실제로이 어떻게해야합니까? 어느 나는 또한 산책 할 이유 여기 사람들과 함께 코드를 통해. 그래서 의사가 너희들이 시간. 그래서 마찬가지로이 점을 명심 우리는 이상 전환에 대한 것입니다. 그래서 우리는 몇 가지 카운터를 가질 수 우리의 스왑을 추적 우리는 확인해야하기 때문에 우리가 확인하고있다. 그리고 우리는 전체 배열을 반복 우리는이 예제와 함께했던 것처럼. 요소는 이전보다 크면 우리가 어디서 왔는지 후 요소, 우리는 그들을 교환 우리는 우리를 증가 카운터, 우리가 교환하는 즉시 때문에 우리는 우리의 카운터가 알 수 있도록 할 수 있습니다. 이 질문? 뭔가 여기에 재미 보인다. 학생 : 당신은 카운터를 0으로 설정 마십시오 당신이 루프를 통해 갈 때마다? 당신은 계속하지 마십시오 다시 때마다 제로? 강사 : 꼭 그렇지는 않습니다. 그래서 무슨 일이 우리가 여기를 통해 이동합니다. 그래서 동안은,이 기억 할 반드시 한 번 실행됩니다. 그래서 설정 것 제로인, 카운터, 그것은을 반복하는 것입니다. 그것을 통해 반복 할 때마다, 이 카운터를 업데이트합니다. 이 카운터 업데이트로,이 끝나면, 이 배열의 끝에 도달 할 때있어, 우리의리스트가 정렬되지 않은 경우, 카운터가 업데이트 된 것입니다. 그럼이 상태를 확인하고 OK, 0보다 카운터 큰 말했다. 이 경우, 다시 그것을 할. 당신은 너무 때를 그 재설정 할 통과, 카운터가 0과 같다. 당신은 정렬을 통해 이동하는 경우 배열은, 아무것도, 변경되지 않습니다 이 실패하고 정렬 된 목록을 반환합니다. 그 의미가 있습니까? 학생 : 조금 파일에있을 수 있습니다 그것은. 강사 : OK. 다른이 있다면 온다 질문입니다. 예. 학생 : 어떤 것이 기능 요소를 스와핑 할 수? 강사 : 그래서 우리가 실제로 쓸 수 있습니다 우리가 지금 당장 거라면 그. 쿨. 그 메모 그래서, 앨리슨 것입니다 다시 장비로 전환합니다. 재미있을거야. 그리고 우리는 우리의 좋은이 여기에 거품 정렬 것. 그래서 이미 자전거를했다 배열을. 우리는 우리의 스왑이 그 제로 같다. 그래서 우리는 인접한 교환 할 요소들은 순서가 있다면. 그래서 첫 번째 것은 우리가 필요 우리의 배열을 반복한다 않습니다. 그렇다면 우리가 수도 생각 우리의 배열을 반복? 우리는에 대해하고 난 0 같습니다. 우리는 내가 덜되고 싶어 N 1을 뺀 마이너스 K보다. 그리고 두 번째의 것을 설명 할 것이다. 그래서이 최적화는 여기이고, 나는 모든 패스를 말했다 어떻게 기억 배열 우리를 통해 어떤 입어 -의 알고 그래서 하나의 통과 후 우리 이 정렬됩니다 것을 알고있다. 두 개의 패스 후 우리는 알고있다 이 모든 분류된다. 세 지나면 우리 그 정렬 알아. 방법 그래서 반복 해요 여기에 배열을 통해, 그것은 단지 가서 확인하는 것입니다 우리가 알고있는 것을 통해 정렬되지 않은 것입니다. OK? 그건 그냥 최적화입니다. 당신은 순진을 쓸 수있다 모든 통해 반복, 그것은 단지 더 오래 걸릴 것입니다. 이 4 개의 루프로 그것은이다 단지 좋은 최적화 우리는 그 모든 전체, 후 알고 있기 때문에 여기에 배열을 통해 반복, 여기에 모든 전체 루프처럼, 우리는 알고있다 이들 요소들 중 하나 이상의 것을 마지막에 정렬됩니다. 그래서 우리는 사람들에 대해 걱정할 필요가 없습니다. 즉 모든 사람에게 의미가 있습니까? 그 멋진 작은 트릭? 이 경우에, 만일 그렇다면 우리는을 반복하고 우리는 우리가 있는지 확인하고자하는 것을 알고 배열 N 및 N 플러스 1은 순서에 있습니다. 확인을 클릭합니다. 그래서 여기에 의사입니다. 우리는 있는지 확인하려면 배열 N n은 1을 더한 순서에 있습니다. 그래서 우리가 무엇을해야 할 수도 있습니다? 그것은 몇 가지 조건이 될거야. 이 경우 될 것입니다. 학생 : 배열 N 인 경우 배열 N 플러스 1 이하. 강사 : 그래 그래. 음,보다 작거나보다 큰. 학생 :보다 큼. 그런 다음 우리는 그들을 교환하고 싶습니다. 정확히. 그래서 지금 우리는 무엇에 들어가 를 교환하기위한 메커니즘? 그래서 우리는이 간단히 통해 갔다, 스왑 함수의 유형 지난주. 누군가는이 일을 어떻게 기억합니까? 그래서 우리는 바로, 재 할당 할 수 없습니다? 그 중 하나가 길을 잃기 때문입니다. 우리가 말했다 경우는 B를 B와 동일합니다 같은지, 둘 갑자기 B. 단지 동일 그래서 우리가해야 할 우리입니다 의 임시 변수가 우리 동안 중 하나를 개최 할 예정 우리는 교환하는 과정에있어. 그래서 우리가 가지고있는 것은 우리가 어떤 지능 것입니다 당신이 그것을 할당 할 수 있습니다 난 ... 온도는 동일 둘 중 하나에 당신은, 원하는 당신 졌어요 추적 있는지 계속 확인하십시오 이 경우, 내가 갈거야 배열 N 플러스 1에 할당합니다. 그래서 개최 할 예정 무엇 이건간에 값은 그 두 번째 블록에 우리가보고있는 그. 그리고 우리가 갈 수있는 우리가 할 수있는 것입니다 앞서 및 재 할당 배열 N 플러스 1, 우리는 우리를 알고 있기 때문에 저장된 값을 가지고있다. 이는 또한 큰 중 하나이다 당신의 경우 계속 물건 모르겠어요 두을 전환하면 문제가 있었다 코드 라인은 갑자기 일이했다. 주문 CS에서 매우 중요하다. 그래서 당신이 다이어그램 만들기 일 밖으로 가능한 경우 에 대해 어떤 일이 실제로 일어나고. 그래서 지금 우리가가는거야 배열 N 플러스 1을 재 할당 우리는 우리를 알고 있기 때문에 저장된 값을 가지고있다. 그리고 우리는 배열이 할당 할 수 있습니다 n 또는이 경우 배열 I에서. 너무 많은 변수. 확인을 클릭합니다. 그래서 지금 우리가 재 할당 한 배열 나에게 더하기 1은 배열 I에 무엇이 동일합니다. 그리고 지금 우리가 갈 수 있으며, 무엇에 배열 I를 할당? 누구? 학생 : (10). 강사 : 10. 정확히. 그리고 마지막으로 하나. 우리는 지금을 교환 한 경우, 우리는 무엇을 어떻게해야합니까? 한 가지는 무엇인가 즉 우리에게 것 우리는 지금까지이 프로그램을 종료하면? 우리 것을 우리에게 알려줍니다 정렬 된 목록을 가지고? 우리가 어떤 스왑을 수행하지 않는 경우, 맞죠? 스왑하면 같다 이것의 끝에서 제로. 그래서 때마다 우리 같은 스왑을 수행 여기 한, 우리는 스왑을 업데이트 할. 그리고 내가 거기 있었는지 질문 이전에 대해 당신이 할 수있는 0 대신 또는 하나를 사용 의 참 또는 거짓. 그리고이 여기서 무엇이다. 그래서이 아닌 경우 스왑을 말한다. 스왑 0 인 경우에 따라서 이는 항상 내가 핵폭탄 낙하 얻을 나의 진리 내 falses은 혼합. 우리는 우리가 평가하고자하는 참으로 그것은 아니다. 제로있어 경우에 따라서, 그것은 거짓입니다. 당신은 그것을 부정하면 [? 쾅?] 사실이된다. 그럼이 줄을 실행합니다. 진실과 거짓과 0과 1은 미친 얻을. 그냥 천천히 걸 으면 이를 통해 이해가됩니다. 그러나 그게 무슨이 약간의 코드의 비트는 여기 않습니다. 그래서이 확인합니다 우리는 어떤 스왑을 수행했다. 그래서 아무것도 이외의 경우의 제로, 그것은 거짓이 될 것 전체 것입니다 다시 실행할 것. 쿨? 학생 : 휴식은 무엇입니까? 강사 : 그냥 휴식 루프의 당신을 나누기. 이 경우는 것 그래서 단지 프로그램을 종료하고자 당신은 단지 것 당신의 정렬 된 목록을 가지고있다. 학생 : 놀라운. 강사 : 미안 해요? 학생 : 때문에 우리는 이전에 제로 서면을 통해 1을 기록 사용 경우 그 선보여 그 일을하거나하지 않습니다. 강사 : 네. 그래서 당신은 제로 또는 1을 반환 할 수 있습니다. 이 경우, 때문에 우리는 실제로 아니에요 기능 아무것도, 우리는 그냥 헤어지고 싶어. 우리가 정말 그것에 대해 걱정하지 않는다. 브레이크는 경우 좋은 그것은 탈옥을 위해 사용되는 네 루프 또는 조건의 당신은 실행 유지하고 싶지 않아요. 그것은 그냥 밖으로 이동합니다. 그것은 미묘한 차이 일의 비트입니다. 거기에 같은 느낌 손 흔들며 많은, 같은 당신은 곧이에 대해 알아 보겠습니다. 하지만 당신은 곧이에 대해 알아 보겠습니다. 나는 약속드립니다. 확인을 클릭합니다. 그래서 모두가 거품 정렬을 얻을 수 있습니까? 너무 나쁜. 반복, 스왑 가지를 사용하여 임시 변수는, 우리 모두가 설정거야? 쿨. 신난다. 확인을 클릭합니다. 위로 파워 포인트. 일반 질문 약이 지금까지? 쿨. 그래 그래. 학생 : [들리지] 일반적으로 주요 int로. 이에 대한 그을 가지고 당신이 있습니까? 강사 : 그래서 우리가 찾고 다만 실제 정렬 알고리즘에서. 당신은 이내에이 있다면 큰 프로그램처럼, 당신은 INT 주요 어딘가에있을 것입니다. 어디를에 따라 이 알고리즘을 사용, 그것은 무엇을 결정하는 것 그것에 의해 반환되는. 그러나 우리의 경우, 우리는 엄격하게있어 실제로이 작업을 수행하는 방법을보고 배열을 반복합니다. 그래서 우리는 그것에 대해 걱정하지 마십시오. 그래서 우리는 모범 사례를 이야기하고 이진 검색에 대한 최악의 시나리오. 그래서 할 것도 중요 우리의 종류 각각에 대해 그. 그래서 무엇을 당신이 생각하는 최악 거품 정렬의 경우 런타임? 너희들 기억 나? 학생 : N 마이너스 1. 강사 : N 마이너스 1. 그래서이 의미 N 마이너스 1 비교. 그래서 실현하기 위해 한 가지입니다 첫 번째 반복에 그, 우리는, 우리가 비교를 통해 이동 이 둘 -은 그래서는 1. 이들 둘, 셋, 넷. 그래서 하나의 반복 후 우리 이미 네 개의 비교를해야합니다. 언제 런타임 및 N에 대해서 이야기하고. N은 비교의 수를 나타낸다 얼마나 많은 요소들의 함수로서 우리는 가지고있다. OK? 그래서 우리는 통과, 우리는 네 가지가있다. 당신이 알고 다음에 우리는하지 않습니다 이 알아서해야합니다. 우리는이 두 비교 이 두, 두, 우리는 그 최적화를하지 않은 경우 내가 쓴 4 개의 루프와, 당신은 어쨌든 여기에 비교 될 것이다. 그래서 당신은해야 할 것입니다 배열을 통해 실행 N 개의 비교를 N 회마다 우리 때문에 이 종류의 한 가지 우리를 통해 실행합니다. 그리고 우리를 통해 실행할 때마다 배열, 우리는 N 비교를합니다. 그래서 이것에 대한 우리의 런타임입니다 실제로 N 제곱하는 훨씬 더 우리의 그 때문에 끝을 로그 우리는 네 있었다 의미하는 경우 억 요소, 그것을이다 우리 네 억 걸릴 것 대신 32의 제곱. 그래서 최고는 런타임, 하지만 몇 가지에 대해, 당신이 내 있다면 당신은 알고있다 소자의 일정 범위 거품 정렬 사용이 잘 될 수 있습니다. 확인을 클릭합니다. 그래서 지금 최상의 경우 런타임은 무엇인가? 학생 : 제로? 또는 1? 강사 : 그래서 하나는 것 하나의 비교합니다. 오른쪽. 학생 : N 1을 뺀? 교수 : 그래, 좋아. 그래서 N 마이너스 1. 당신은 N과 같은 개념을 보낼 때마다 마이너스 1, 우리는 단지 그것을 내려하는 경향이 당신이 있기 때문에 우리는 단지 N 말 이거 갖다 각 쌍의 각을 비교. 그래서, 1 N 수를 뺀 것이다 우리 우리는 약 n은 말할 것입니다. 런타임을 다룰 때, 모든 가까운 것입니다. 만큼 지수 그대로 정확한, 당신은 꽤 좋은 것입니다. 우리가 다루는 방법 때문입니다. 최상의 경우는 N,되도록하는 목록이 이미 정렬되어 있다는 것을 의미 우리가하는 모든 일을 통해 실행 그것은 소팅 있는지 확인합니다. 쿨. 좋아. 당신이 여기에서 보는 바와 같이 그래서 우리 좀 더 그래프가있다. 그래서 N 제곱. 재미. 많은 우리가 보는 바와 같이 n보다 더, 그리고 로그 2N보다 훨씬 더 많이. 그리고 당신은 또한 로그 로그에 들어갈. 그리고 당신은 124 가지고, 당신은 들어가 미친 듯이입니다 로그 스타, 등. 당신이 관심이 있다면 그래서, 조회 로그 스타. 약간 재미있어. 그래서 우리는이 위대한 차트가 있습니다. 그냥 머리까지,이 멋진 차트해야합니다 우리가 있기 때문에 중기 당신이 엷게 물어 긴. 그러니 그냥 헤드 업에이를 당신의 당신의 좋은 컨닝 페이퍼에 중기 가. 그래서 우리는 거품 정렬 바라 보았다. 최악의 경우, N, N을 최상의 경우 제곱. 그리고 우리는 다른 사람을 보는 것입니다. 그리고 당신은, 단지를 볼 수 있습니다 정말 잘 수행 하나 우리가 왜에 얻을 것이다 병합 정렬입니다. 그래서 우리는에 갈거야 다음 중 하나와 ... 선택 정렬. 사람이 어떻게 기억 하는가 선택은 종류의 일? 그것을 위해 이동합니다. 학생 : 기본적으로 통과 주문 및 새로운 목록을 만듭니다. 그리고 당신은 요소를 가하고있는 것처럼 에, 적절한 장소에 넣어 새 목록에. 강사 : 그래서 소리가 삽입 정렬과 같은 더. 하지만 당신은 정말 가까이있어. 그들은 매우 유사하고 있습니다. 심지어 나는 그들이 가끔 헷갈 리더 라구. 나는 마치이 절 전에 기다립니다. 확인을 클릭합니다. 그래서 당신이 원하는 것을 수행은 선택의 일종이다 당신이 생각할 수있는 방법 IT 및 방법에 대한 나는 확실히 내가 얻을하지 않으려 고 노력하게 그들은 통과하고, 혼합 그것은 선택 적은 수의과 목록의 시작 부분에 그 넣습니다. 그것은 첫 번째 자리로 바꿉니다. 그들은 실제로 나를 위해 예를 가지고있다. 신난다. 그러니 방법 졌어요 선택 생각 종류, 가장 작은 값을 선택합니다. 우리는에 갈거야 예를 통해 실행 나는 때문에 도움이 될 것입니다 생각 나는 시각이 항상 도움을 생각합니다. 그래서 우리는 뭔가으로 시작 즉, 완전히 정렬되지 않은 것입니다. 빨강, 정렬되지 않은 것입니다 녹색 정렬됩니다. 그것은 모든 초 감각을 만들 것입니다. 그래서 우리는 통과하고 우리는 반복 처음부터 끝까지. 그리고 우리는 OK, 2 인, 말 우리의 작은 수입니다. 그래서 우리는이 걸릴거야 그리고 우리는거야 우리의 배열의 전면으로 이동 이 때문에 적은 수의 우리가 있습니다. 그래서이 여기에서 무엇을하고 있는지입니다. 그것은 단지 그 두 가지를 교환하는 것입니다. 그래서 지금 우리는 분류 한 부분과 정렬되지 않은 부분. 기억하기 좋은거야 선택 정렬에 대한 우리는 선택하고있다 정렬되지 않은 부분에서. 정렬 된 부분은 그냥 내버려. 으흠? 학생 : 무엇인가는 알 수 있을까하는 방법 비교없이 작은 어레이 내의 다른 모든 값. 강사 : 그것은 비교한다. 우리는 그것을 생략있다. 이 전체 단지 일반적이다. 그래. 우리는 난 코드를 작성하는 경우 확실히 당신은 더 만족하실 겁니다. 그러나 먼저이 저장 가장 작은 같은 요소입니다. 당신은 비교하고 OK,이 작은 말? 예. 보관하십시오. 여기가 작은? 아니? 이것은 당신의 가장 작은 당신의 값으로 재 할당. 그리고 당신은 훨씬 더 행복 할 것이다 우리는 코드를 통해 갈 때. 그래서 우리는 통과, 우리는 그러므로, 그것을 교환 우리는이 분류되지 않은 부분을 확인합니다. 그래서 우리는 세 가지 아웃을 선택하는 것입니다. 우리는 그것을에 넣어거야 우리의 정렬 된 부분의 끝. 그리고 우리는 단지 일을 계속하는거야 그 일을하고 그 일을, 그. 그래서 여기에 의사의 우리의 일종이다. 우리는 두 번째 여기에 그것을 만들 것이다. 하지만 뭔가가 산책 높은 수준에 통해. 당신은 갈거야 난에 N 마이너스 2 0 같습니다. 즉 다른 최적화합니다. 그것에 대해 너무 걱정하지 마십시오. 같은 그래서 당신은 말을했다. 야곱이 말한 바와 같이, 우리는 어떻게 할 우리의 최소가 무엇인지를 추적? 우리는 어떻게 알 수 있습니까? 우리는 비교해야 우리의 목록에있는 모든. 그래서 최소한 내가 같습니다. 단지이 경우에는 말 것 우리의 최소 값의 인덱스. 그래서 그것은을 반복하는거야 J는 내가 1을 더한 동일에서 그것은 간다. 그래서 우리는 이미 알고 즉, 우리의 첫 번째 요소입니다. 우리는 그 자체와 비교할 필요가 없다. 그래서 우리는 다음과 비교 시작 그것이 내가 더하기 1은 n으로 왜 하나는이다 빼기 1 인 이 배열의 끝. 그리고 우리는 배열의 경우 말했다 j는, 어레이 분 미만인 우리는 여기서 다시 할당 우리의 최소 인덱스이다. 그리고 만약 분, 나는 동일하지 않은 여기서 우리는 다시 여기에 있었다. 우리가 처음이 일을했을 때 그래서 좋아합니다. 이 경우에는 시작 것 제로, 그것은 두 끝나게된다. 그래서 분 결국 나는 동일하지 않을 것이다. 즉 우리는 알고 있습니다 우리는 그들을 교환해야합니다. 나는 구체적인 예를 들어 같은 느낌 이보다 더 많은 도움이 될 것입니다. 그래서 난 너희들과이를 만들 것이다 지금 나는 그것을 더 좋을 것 같아요. 종류는 점에서 그런 식으로 작동하는 경향이 그것은 단지 그들을보고하는 것이 좋습니다. 그래서 우리가 원하는 것입니다 우리는 가장 작은 원하는 배열에서의 위치에있는 요소입니다. 정확히 야곱이 한 말. 당신은 어떻게 든를 저장해야합니다. 그래서 우리는 여기에서 시작하는거야 배열의 반복. 우리는 말할거야 우리 단지 시작하는 첫 번째. 그래서 우리는 INT를해야 할 것 작은 난에서 배열과 동일하다. 그래서 한 가지, 모든 통지합니다 이 루프는 실행 시간, 우리가 함께 한 단계 더 시작하고있다. 우리가 시작하면 우리는이 하나 봐. 우리는을 통해 반복 다음에, 우리는이 하나에서 시작하고 그리고 우리의 작은 값 할당. 그래서 거품 정렬과 매우 유사 우리가 알고있는 경우 하나의 통과 후 그, 이 마지막 요소는 정렬됩니다. 선택 정렬과 함께, 그것은 그 반대입니다. 모든 패스에서, 우리는 알고 첫 번째 정렬됩니다. 두 번째 패스 후, 두 번째는 정렬됩니다. 그리고 당신은 슬라이드 예제와 함께 본대로, 우리의 정렬 된 부분은 단지 성장 유지합니다. 그래서 우리 최소 하나를 설정함으로써, 배열에 나는, 모두가이 짓을 탱탱 무엇 우리는 그렇게으로보고있다 수를 최소화 비교 우리는합니다. 즉 모든 사람에게 의미가 있습니까? 마십시오 당신은을 통해 실행하는 날 필요 다시 느리게 또는 다른 단어에? 나는 행복 해요. 확인을 클릭합니다. 그래서 우리는 저장하고 이 시점에서의 값, 그러나 우리는 또한 인덱스를 저장할. 그래서 우리는 저장거야 최소의 위치 그냥 될 것입니다 하나. 이제 야곱은 만족입니다. 우리는 저장 가지가 있습니다. 그리고 지금 우리를 통해 볼 필요가 배열의 정렬되지 않은 부분. 이 경우이 그래서 우리의 정렬되지 않은 것입니다. 이것은 내가입니다. 확인을 클릭합니다. 그래서 우리가 할거야 루프가 될 것입니다. 당신은해야 할 때마다 배열을 반복, 당신의 마음은 루프에 갈 수있다. 일부 INT의 k에 대한 그래서 우리가 어떻게 생각하십니까 equals-- K로 시작 동일한 것입니다? 이것은 우리가 우리의 작은으로 설정 무엇인가 가치와 우리는 그것을 비교하고 싶습니다. 우리는에 비교 무엇을 원하는가? 그것은 바로,이 다음 중 하나가 될 것? 그래서 우리는 초기화 케이 원하는 에에게 나는 플러스 1을 시작합니다. 그리고 우리는이 경우 k는 원하는 우리 이미 크기가 여기에 저장되어, 그래서 우리는 단지 크기를 사용할 수 있습니다. 크기 어레이의 크기 인. 그리고 우리는 원하는 한마다로 K를 업데이트합니다. 쿨. 그래서 지금 우리는 찾을 필요 여기에 가장 작은 요소입니다. 그래서 우리는 반복을 통해, 우리 , 말하고 싶은 경우 k에 배열 우리의 작은 value-- 미만 우리가 실제로있어 곳이다 무엇을 추적 작은 매우 ... 우리는 다시 할당 할 우리의 작은 값은 무엇인지. 이것은 오, 우리가있어, 것을 의미한다 여기를 반복. 무엇이든 값이 여기에있다 하지 우리의 작은 것. 우리는 그것을 원하지 않는다. 우리는 그것을 다시 할당 할 수 있습니다. 우리가 그것을 다시 지정하는 경우 그래서, 무엇을 여기에이 코드에있을 것 같아요? 우리는 다시 할당 할 작고 위치. 이제 작은 무엇인가? 학생 : 배열 K. 강사 : 배열 K. 그리고 위치는 지금 무엇인가? 의 인덱스 무엇입니까 우리의 작은 값? 그냥 삼진. 배열 K, K 그래서, 그들은 일치. 그래서 우리는 다시 할당하고 싶었다. 그리고 우리는, 우리의 작은 발견 후 후 이 루프의 끝에 그렇게 여기에 우리가 발견 한 내용을 우리의 작은 값은, 그래서 우리는 그냥 교환합니다. 이 경우, 같은 우리 말 가장 작은 값은 여기입니다. 이것은 우리의 가장 작은 값입니다. 우리는 단지이다, 여기를 교환 할 무엇을 바닥에 그 스왑 기능 우리가 그냥 쓴, 한 함께 몇 분 전. 그래서 익숙 할 것이다. 그리고 그것은 단지 반복합니다 통한 모든 방법으로 도달 할 때까지 당신을 의미 말에 분류되지 않은 있습니다 제로 요소가 그리고 다른 모든 정렬되었습니다. 이해가? 보다 구체적으로 작은? 코드 도움? 학생 : 크기를 들어, 결코 정말 정의하거나 변경, 어떻게 알 수 있습니까? 강사 : 그래서 한 가지에 INT 크기가 여기에 알 수 있습니다. 그래서 우리는이 sort-- 종류에 말을하는지 인이의 기능은 그것의 case-- 선택 정렬, 그것을 통과 것 기능에. 이 통과되지 않은 경우 그래서 에에게, 당신이 뭔가를 할 것입니다 어레이의 길이 등에 또는 당신은을 통해 반복 할 것 길이를 찾을 수 있습니다. 그러나 전달 있기 때문에 에, 우리는 그것을 사용할 수 있습니다. 당신은 사용자가 있다고 가정 당신에게 유효한 크기를 준 실제로 나타냅니다 배열의 크기. 쿨? 너희들은 다음에 어떤 문제가있는 경우 또는 더 많은 연습 코딩 종류를 원하는 직접 수행해야 study.cs50로 이동합니다. 그것은 도구입니다. 그들은 검사가 그 당신은 실제로 쓸 수 있습니다. 그들은 의사를 않습니다. 그들은 더 많은 동영상과 슬라이드를 내가 여기에 사용하는 것을 포함. 당신은 여전히​​를 느끼는 경우에 따라서 약간 퍼지, 그 밖으로 시도. 언제나처럼, 너무, 얘기 온다. 질문? 학생 : 당신은 말을하고 있습니까 크기는 이전에 정의? 강사 : 네. 크기는 이전에 정의된다 여기에 함수 선언에. 그래서이 전달되어 있다고 가정 사용자에 의해, 그리고 단순화하기 위해, 우리는 가정거야 사용자는 우리에게 올바른 크기를 주었다. 쿨. 그래서 선택 정렬입니다. 얘들 아, 나는 우리가 오늘 많이 배우고 알고있다. 이 부분에 대한 치밀한 데이터입니다. 그와 그래서, 우리는 가고있다 삽입 정렬로 이동합니다. 확인을 클릭합니다. 그래서 그 전에 우리가해야 할 여기에 우리의 런타임 분석. 가장 좋은 경우에 따라서 내가 당신을 보여 주었다부터 부여 테이블에 이미 I 종류의 포기 했어. 하지만 가장 좋은 경우 런타임, 우리는 무엇을 생각 하는가? 모든 분류. N 제곱. 누군가는 설명을 당신이 생각하는 이유에 대해? 학생 : 당신가 ... 비교하고 강사 : 오른쪽. 당신은을 통해 비교하고 있습니다. 모든 반복에서, 비록 우리는 하나이를 감소시키는 것 당신은 여전히​​ 통해 검색하는 모든 작은 하나를 찾을 수 있습니다. 그래서 경우에도 작은 값 , 처음에 여기에 당신은 여전히​​ 비교하고 다른 모든 것들에 대하여 이 작은 일이 있는지 확인합니다. 그래서 통해 실행 될 겁니다 약 n 번 제곱. 좋아. 그리고 최악의 경우는 무엇인가? 당신이려고하고 있기 때문에 N 제곱 같은 절차를 수행합니다. 이 경우, 선택 그래서 일종의 뭔가가 우리는 또한 예상 런타임 부르는. 그래서 다른 사람에, 우리는 알고있다 상부 및 하부의 경계. 얼마나 미친에 따라 우리의 리스트 또는 정렬되지 않은 방법이있다, 그들은 N 또는 n 제곱 다릅니다. 우리는 모른다. 그러나 선택 정렬 동일한 있기 때문에 최악과 최선의 경우, 그 것을 우리에게 알려줍니다 입력의 종류에 관계없이 우리 완전히 여부,이 분류 또는 완전히 그것의 분류, 역 동일한 시간이 걸릴 것. 경우에 따라서, 당신의 경우 우리의 테이블에서 기억, 실제로 값을 가지고 그 이 두 종류는 없습니다 이는 예상 런타임입니다. 그래서 우리는 알고 때마다 그 우리는 선택 정렬을 실행, 그것은으로 보장된다 N 제곱 시간을 실행합니다. 아무 변화가 없습니다. 그것은 단지 예정입니다. 그리고, 다시, 당신은 배우고 싶다면 더, 봄에 CS 124을. 좋아. 우리는이 하나를 보았다. 쿨. 그래서 삽입 정렬. 그리고 아마거야 이를 통해 불꽃합니다. 너희들이 그것을 코드가 없습니다. 우리는 단지 그것을 통해 걸을 것이다. 그래서 삽입 정렬은 종류 선택 정렬에 유사한 점에서 우리는 모두 정렬되지 않은이 및 어레이의 일부를 정렬. 그러나 다른 것은 것입니다 우리는 하나 하나를 진행하면서, 우리는 어떤 수를 가지고 우리의 분류되지 않은에서 옆에 과 올바르게 정렬 우리의 정렬 된 배열로. 그것은 예를 들어 더 의미가 있습니다. 그래서 모든 분류되지 않은 시작됩니다, 단지 선택 정렬처럼. 그리고 우리는이를 정렬하는거야 우리가왔다으로 오름차순. 우리의 첫 번째 패스에 따라서 우리는 첫 번째 값을 우리는 OK, 당신이, 말 지금 혼자서 목록에서. 당신은 목록에 있기 때문에 자신에 의해, 당신은 분류되어 있습니다. 인에 대한 축하 이 배열의 첫 번째 요소. 당신은 이미 자신의 모든 정렬하고 있습니다. 그래서 지금 우리는 분류 한 및 정렬되지 않은 배열입니다. 그래서 지금 우리는 첫 번째 가져 가라. 무슨 일 사이에 발생 여기, 우리가 말할 것입니다 OK, 우리는 보는거야 우리의 정렬되지 않은 배열의 첫 번째 값 우리는에 입력을거야 그 정렬 된 배열에서 올바른 위치. 그래서 우리는 5 걸릴 우리가 무엇을 우리가, 5가 3보다 큰, OK, 말 그래서 우리는 바로 삽입 그 오른쪽. 우리는 좋은 것입니다. 그래서 우리는 우리의 다음 단계로 계속. 그리고 우리는이 걸릴. 우리는 OK, 2 작, 말 3보다, 그래서 우리는 알고 그것을 그 에 있어야 지금 우리의 목록의 앞. 그래서 우리가 할 것은 우리가 아래 3과 5를 밀어입니다 우리는 첫 번째 슬롯에 2를 이동합니다. 그래서 우리는 단지에 삽입하고 그것이 있어야 올바른 위치. 그럼 우리가보고 우리 다음 하나는, 우리는 6을 말한다. OK, 6보다 큰 우리의 정렬 된 배열에 모든 것을, 그래서 우리는 마지막에 그것을 태그입니다. 그리고 우리는 4 봐. (4)이 6 미만인, 덜 야 5보다하지만 3보다 큰입니다. 그래서 우리는 바로 삽입 (3)과 (5) 사이의 중간. 그래서 조금 확인하기 보다 구체적인 비트, 여기 가지입니다 무슨 일이 있었는지의 생각. 각 정렬되지 않은 요소에 대한 그래서 우리 여기서 정렬 된 부분에 결정 그 것이다. 그래서 마음에두고 분류 분류되지 않은, 우리는 통해도 통과해야 이 정렬 된 배열에 맞는 곳을. 그리고 우리는 이동에 의해 삽입 그것의 오른쪽 아래에 요소. 그리고 우리는 계속 우리까지를 반복 완전히 정렬 된 목록을 가지고 지금 제로 분류되지 않은 곳이다 및 정렬이 차지 우리의 목록의 전체. 그래서, 다시, 심지어 물건을 만들기 위해 보다 구체적인, 우리는 의사가 있습니다. 그래서 기본적으로 내가 때문이다 N 마이너스 1에 0이, 즉 우리의 배열의 단지 길이입니다. 우리와 같은 일부 요소가 첫 번째 배열 또는 최초의 인덱스. 우리는 그와 같은 J를 설정합니다. j는보다 큰 반면 그래서 제로와 배열, J 마이너스 1 보다 큰 요소, 모든 있도록 뭐하는거야 있는지 확인하고있다 당신의 j는 정말 표현 배열의 정렬되지 않은 부분. 아직 일이 있지만 그래서 정렬 J 하나를 뺀 무엇 핵폭탄 낙하하는 요소 그녀는? J는 여기에 정의되지 않았습니다. 그것은 성가신 가지입니다. 확인을 클릭합니다. 어쨌든. 그래서 J 마이너스 1, 당신은 확인 중 그 전에 요소입니다. 당신은 OK, 요소, 말을하는지 나는의하자 am-- 어디든지 전에 실제로이를 그립니다. 그래서이 말씀이하자 우리의 두 번째 패스에있다. 그래서 나는 동일이 될 것입니다 1로, 이는 여기에있다. 그래서 나는 1 인이 될 것입니다. 이 2, 4, 5, 6, 7이 될 것이다. 좋아. 이 경우에 따라서 우리의 요소 4와 동일 할 것입니다. 그리고 우리의 일부 J가 1과 동일 할 것. 아, j는 감소시키는됩니다. 즉 그것이 무엇인지입니다. 그래서 J는 I와 같다, 그래서 이것은 무엇인가 말은, 우리가 앞으로 이동한다는 것입니다 우리는 확인하고있어 우리는 이상 아니라는 걸 우리가하려고 할 때이 방법을 인덱싱 우리의 정렬 된 목록에 물건을 삽입합니다. 그래서이 경우 j는 1로 동일한 경우 및 그래서 배열 J 마이너스 1 보이면 배열 J 마이너스 그건 경우이 case--에 2 요소보다 큰 모든이하고있다 물건을 아래로 이동하고있다. 이 경우, 어레이 j를 뺀 하나 그래서 2 배열 제로가 될 것입니다. 2, 4보다 크지 그래서이 실행되지 않습니다. 그래서 변화는 아래로 이동하지 않습니다. 이것이 여기서하는 일은 그냥 아래로 정렬 된 배열을 이동. 이 경우, 실제로, 우리 하더라도 - 수의이 3를 만들어 보자. 그래서 우리는 끝까지 걸을 수 있다면 이 예는, 우리가 지금 여기있어. 이 정렬됩니다. 이 분류되지 않은 것입니다. 쿨? 그래서 나는 이렇게, 2와 동일 우리의 요소는 3과 같다. 그리고 우리 j는 2와 동일하다. 그래서 우리는 우리과를 통해 보면 OK, 배열 J 빼기 하나, 말 요소보다 큰 우리가보고있는 것을? 그리고 그 대답은 바로 '예? 도 4는도 3 및 J보다 크다 2, 그래서이 코드가 실행됩니다. 그래서 지금 우리가 배열을 무엇을 2, 바로 여기, 그래서 우리는 그들을 교환합니다. 그래서 우리는 OK, 배열, 말 2에서 지금은 3가 될 것입니다. 그리고 J는 동일 할 것입니다 1 J 마이너스 1. 즉, 끔찍하지만, 너희들은 아이디어를 얻을. J는 현재 1과 동일하다. 그리고 배열 ​​J는 될 것입니다 4이었다 우리의 요소와 동일. 내가 뭔가를 삭제 내가하지 말아야 이 있거나 잘못 적었다 무엇인가, 하지만 너희들은 아이디어를 얻을. 그것은 N에서 이동합니다. 이 있었다 다음 경우에, 그것은 루프 것 다시는 OK, j는 현재 1, 말할 것입니다. 그리고 배열 ​​J 마이너스 1은 지금 2입니다. (2) 우리의 요소보다 작은? 아니? 그것은 우리가했습니다 것을 의미한다 이 요소를 삽입 우리의 정렬 된 배열에서 올바른 자리에. 그리고 우리는이 걸릴 수 있으며 우리는 말, OK, 우리의 정렬 된 배열은 여기에있다. 그리고이 숫자 6을 가지고있을 것 같은, 확인,이 수보다 6 적은? 아니? 쿨. 우리는 괜찮아요. 다시 작업을 수행합니다. 우리는 7을 말한다. 마지막 7보다 작 우리의 정렬 된 배열? 아니오. 그래서 우리는 괜찮아요. 그래서이 정렬 될 것이다. 기본적으로이 모든 수행 그것은 테이크를 말하는 것입니다 의 첫 번째 요소 당신의 정렬되지 않은 배열, 이 어디로 가는지 파악 당신의 정렬 된 배열에. 그리고 이것은 바로 처리한다 스왑의 작업을 수행합니다. 당신은 기본적으로 그냥 교환하고 때까지 오른쪽하다고. 시각적 이미지는 걸이다 그 작업을 수행하여 모든 것을 아래로 이동합니다. 그래서 반 거품 같은 것이 - 억양입니다. 연구 (50)를 확인하십시오. 나는 매우 노력하는 것이 좋습니다 이런 방법을 직접 코딩합니다. 당신은 어떤 문제가 또는 당신이 원하는 경우 삽입 정렬에 대한 샘플 코드를 참조하십시오 알려 주시기 바랍니다. 나는 주위에 항상 해요. 그래서 최악의 경우 런타임 최상의 경우 런타임. 당신은 사람 나는 이미 표에서 보듯 그것은 제곱 N 것 모두 N, 당신을 보여 주었다. 그래서 종류의 우리가 이야기 무엇을하러 갈 우리의 이전 종류의 약, 최악의 경우 런타임 인​​ 경우 그 그것은 완전히 정렬되지 않은 것, 우리는이 N 배의 모든 비교해야합니다. 우리는 비교의 전체 많이 할 이 역순으로인지하기 때문에, 우리는 OK,이 말을 겁니다 이 좋은, 동일 이 하나 비교하는 것 첫 번째에 대해 다시 이동합니다. 그리고 우리를 향해 얻을로 꼬리 끝, 우리가 비교 비교하고 모든 비교할. 그래서이되는 끝 약 N 제곱. 그것은 다음 맞습니다 경우 당신은 좋은 것, 2, 확인을 말한다. 도 3에는 2와 비교하는. 당신은 좋은 것입니다. 4, 당신은 꼬리에 비교합니다. 당신은 좋은 것입니다. 6, 당신은 괜찮아요, 꼬리에 비교합니다. 그래서 모든 자리는 이미 경우 분류, 당신은 하나의 비교를하고 있어요. 그래서 그냥 N입니다. 그리고 우리는 최상의 경우 런타임을 가지고 있기 때문에 n 및 n 인 최악의 경우의 런타임 제곱, 우리는 더 예상 런타임이 없습니다. 그것은 단지에 따라 달라집니다 거기에 우리의 목록의 혼란. 그리고 또 다른 그래프와 다른 테이블. 종류의 차이 그래서. 난 그냥 통해 산들 바람거야, 나는 우리는 광범위하게 얘기했습니다 같은 느낌 어떻게 모든 종류의에 대한 의 변화와 함께 연결합니다. 그래서 일종의 마지막 하나는 병합 나는 당신에게 사람을 지루하게하여야한다. 우리는 꽤 다채로운 그림을 가지고 않습니다. 그래서 일종의 재귀 알고리즘 병합합니다. 그래서 당신들이 아는 건 재귀 함수는? 사람은하고 싶은 말? 당신이 시도하고 싶어? 그래서 재귀 함수는 그냥 자신을 호출하는 함수입니다. 그래서 너희들은 잘 알고있는 경우 피보나치 수열과, 그 때문에 재귀 것으로 간주 것 당신은 이전의 두 걸릴 함께 추가 다음 중 하나를 얻을 수 있습니다. 그래서 재귀, 나는 항상 생각 나선형 등의 재귀 그래서 당신은 그것으로 아래로 나선형 같은거야. 그러나 그것은 단지 함수의 그 자체를 호출합니다. 그리고, 사실, 정말 빨리 I 그 모습을 보여줄 수 있습니다. 우리가 보면 여기 그래서 재귀,이입니다 재귀 방법은 배열을 통해 요약합니다. 그래서 모든 우리가 할 것입니다 우리는 sum 함수를 크기와 배열을 취하는 합. 그리고 당신이 나는 경우, 크기 한마다로 감소. 그리고이하는 모든 x가 동일한 경우이다 zero-- 그렇다면 배열의 크기 그것은 0을 반환 zero--과 같다. 그렇지 않으면이 요약 배열의 마지막 요소, 다음의 합을합니다 배열의 나머지. 그래서 그냥 아래로 깨고 더 작은 문제로. 길고도 짧은 이야기, 재귀, 자신을 호출 기능. 즉이 나왔을 모든 있다면, 즉 재귀 함수가 무엇인지입니다. 당신이 51을 가지고가는 경우에, 당신은 매우 얻을 것이다, 재귀 매우 편안. 정말 멋진. 이 같은 의미에서 만든 아웃 오전 3시 밤. 그리고, 왜 같았다 나는이를 사용 적이 없다? 기본적으로, 병합 종류에 따라서 무엇을 할 것 것은 그것의이다 그것을 파괴하고 그것을 깰 것 그것은 단지 하나의 요소 때까지 아래로. 하나의 요소는 정렬하기 쉽습니다. 우리는을 참조하십시오. 당신은 하나의 요소가 있다면, 그건 이미 정렬 된 것으로 간주. n 개의 요소의 입력에 따라서, n이 2 미만이면, 그냥 의미하기 때문에 반환 우리가 보았 듯이 0 또는 1 중 하나입니다. 사람들은 정렬 된 요소로 간주됩니다. 그렇지 않으면 반으로 휴식. 두 번째 정렬 상반기 정렬 반하고 그들을 함께 병합합니다. 왜이 병합 종류라고. 우리는이를 정렬 할 것이다 그래서 우리는 여기에있다. 그래서 우리는 그들을 가진 유지 배열 크기가 1이 될 때까지. 이 일을 그래서 때, 우리는 단지 반환 이 정렬 된 배열이기 때문에, 이것은 정렬 된 배열이고, 그건 정렬 된 배열, 우리는 모든 분류하고 있습니다. 그럼 우리가하는 일 우리는 그들을 함께 병합 시작합니다. 그래서 방법을 수행 할 수 있습니다 병합이 생각 당신은 단지 작은 제거 서브 어레이의 각각의 개수 그냥 등장 배열에 추가합니다. 그래서 만약 우리가 때, 이쪽을 봐주세요 이러한 세트는 우리는 4, 6, 및 일이있다. 우리는이를 병합 할 때, 우리는 이러한 처음 두 볼 우리는 1 작, OK, 말, 그것은 앞으로 간다. 4, 6, 비교 아무것도 없다 그것은 단지 말미에에 태그를. 우리는이 두 가지를 결합 할 때, 우리 단지 이 두 가지의 작은 하나를 수행 그래서 1입니다. 그리고 지금 우리는을 이 두, 그래서이 작은. 이 두, 3의 작은. 이러한 두, 4, 5, 6 이하이다. 그래서 그냥이를 당겨하고 있습니다. 그리고 그들은했습니다 때문에 이전에 분류 된, 당신은 단지 하나가 비교가마다. 여기에 그래서 더 많은 코드, 단지 표현입니다. 그래서 만약 당신이 중간에서 시작 당신 종류의 왼쪽과 오른쪽 다음은 그 병합합니다. 그리고 우리는 코드가없는 바로 여기에 병합합니다. 그러나, 다시, 당신은에 갈 경우 (50) 연구, 거기있을거야. 그렇지 않으면 나에게 이야기를 올 당신이 있다면 여전히 혼란. 그래서 여기에 멋진 일이 그 최상의 경우는, 최악의 경우, 예상 런타임 n은 모든 로그에 있고 우리는 것보다 훨씬 낫다 우리의 종류의 나머지 본. 우리는 본 N 제곱 한 실제로 우리는 무엇을 큰 인 N N 로그 여기에 얻을. 즉 얼마나 잘 봐. 이러한 좋은 곡선. 그래서 훨씬 더 효율적입니다. 만약 당신이 할 수있는 경우, 사용은 일종의 병합합니다. 그것은 당신에게 시간을 절약 할 수 있습니다. 그럼 다시, 우리가 말했듯이, 경우 당신이 낮은 지역에서 아래로있어 그것은 그가되지 않습니다 많은 차이. 당신은 수천 일어나 및 입력의 수천, 당신은 확실히 원하는 더 효율적인 알고리즘. 모든 그리고 다시, 우리의 사랑스러운 테이블 너희들이 오늘 배운 종류. 그래서 나는 그것이 조밀 한 하루 였어요 알고있다. 이것은 필요하지 않을 당신의 pset에 도움을주는. 하지만 난 그냥 고지 사항을 확인하려면 그 부분은 Pset에 대해하지 않습니다. 이 모든 재료는 공정하다 당신의 중간 고사를위한 게임. 그리고 당신은 CS와 계속 할 수도있는 경우, 이들은 정말 중요한 기본이다 것을 당신은 알고 있어야합니다. 그래서 어떤 일이있을 것입니다 좀 더 PSET 도움, 하지만 몇 주는 것입니다 훨씬 더 실제 내용 그 슈퍼를 보이지 않을 수도 지금 당신에게 유용, 계속하면 그러나 나는 약속 에 매우, 매우 유용 할 것이다. 그래서이 부분은 여기까지. 와이어에 이르기까지. 나는 1 분 이내에 그것을했다. 그러나 거기 당신은 간다. 그리고 나는 도넛이나 사탕을해야합니다. 알레르기 사람이하는 것입니다 그런데 아무것도? 계란과 우유. 그래서 도넛은 더는 없다? 확인을 클릭합니다. 좋아. 초콜릿 없음? 별 모양. 육각형 좋다. 확인을 클릭합니다. 우리는 할 겁니다 다음 다음 주에 별 모양. 그게 내가거야거야. 너희들은 멋진 한 주를 가지고있다. 당신의 사양을 참조하십시오. 당신은 질문이있는 경우 알려주세요. PSET 두 등급이어야한다 목요일에 의해 당신에게 밖으로. 당신은 질문이있는 경우 내가 뭔가를 채점 방법에 대한 또는 왜 내가 곧 길이 뭔가 등급 나에게 이메일을 보내 주시기 바랍니다 않았다, 얘기 온다. 내가 좀 미친이있어 주,하지만 약속 나는 아직도 24 시간 이내에 회신 해 드리겠습니다. 그래서 멋진 한 주, 모두를 가지고있다. 당신의 pset에 행운을 빕니다.