SPEAKER 1: Hey tất cả mọi người! Chào mừng trở lại phần. Vì vậy, vui mừng khi thấy rất nhiều bạn cả ở đây, và tất cả những ai đang xem trực tuyến. Vì vậy, như thường lệ chào đón trở lại. Tôi hy vọng rằng tất cả các bạn đã có một đáng yêu cuối tuần, đầy đủ nghỉ ngơi, thư giãn. Đó là đẹp ra ngày hôm qua. Vì vậy, tôi hy vọng bạn thích hoạt động ngoài trời. 

Vì vậy, đầu tiên một vài thông báo. Chấm điểm. Vì vậy, hầu hết các bạn nên đã nhận một gửi email từ tôi về Pset Scratch của bạn, cũng như chấm điểm cho Pset 1. Vì vậy, chỉ cần một vài điều. Hãy chắc chắn để sử dụng check50 trong style50. Đây có nghĩa là để được nguồn lực cho các bạn, để đảm bảo rằng bạn đang nhận được càng nhiều điểm như bạn có thể không cần thiết mà không mất chúng. Vì vậy, những thứ như phong cách là rất quan trọng. Chúng tôi sẽ cất cánh cho nó. Một số bạn có thể đã nhận thấy rằng từ Pset của bạn. Và check50 chỉ là cách thực sự dễ dàng để đảm bảo rằng chúng tôi đang thực sự trở về những gì cần phải được trả lại cho người sử dụng, và rằng tất cả mọi thứ đang làm việc đúng cách. 

Trên lưu ý thứ hai, hãy chắc chắn bạn tải lên những thứ về đúng thư mục. Nó làm cho cuộc sống của tôi chỉ là một một chút khó khăn hơn nếu bạn tải lên Pset 2 vào Pset 1 bởi vì khi tôi tải về mọi thứ, họ không tải một cách chính xác. Và tôi biết đó là một chút rung rinh trong một hệ thống để có được sử dụng để, nhưng chỉ được siêu cẩn thận, nếu chỉ cho tôi, do đó khi bạn đang nhận được email tại như 02:00 và tôi chấm điểm. Nếu không gây ra tôi phải nhìn tất cả các xung quanh cho Pset của bạn. Cool. 

Tôi biết đó là sớm, nhưng tôi hoàn toàn bị lấy mất cảnh giác bằng một bài luận đó là do thứ sáu này, mà giáo sư của tôi đã được chỉ thích, oh yeah. Hãy nhớ rằng, bạn có một bài luận do vào thứ Sáu. Vì vậy, tôi biết không ai thích để suy nghĩ về midterms, nhưng bài kiểm tra đầu tiên của bạn là vào ngày 15 tháng 10, Tháng Mười đó được bắt đầu trong tuần này. Vì vậy, nó có thể là sớm hơn hơn bạn mong đợi là tất cả. Vì vậy, bạn không ném mất cảnh giác khi Tôi đề cập đến phần vào tuần tới mà oh, đố tuần tiếp theo của bạn, tôi nghĩ Tôi muốn cung cấp cho bạn một chút hơn của một người đứng đầu ngay bây giờ. 

Vì vậy, vấn đề của bạn được thiết lập, số ba. Làm thế nào mọi người đã đọc spec ra tò mò? OK. Chúng tôi có một cặp vợ chồng. Loại giảm từ cuối cùng tuần nhưng đó là OK. Tôi biết nó đã được ra khỏi đẹp. Vì vậy, Break Out. Chắc chắn sau khi bạn được thực hiện ngày nay đọc spec của bạn ít nhất thử như tải đang phân phối và chạy như ban đầu đầu tiên điều mà họ yêu cầu bạn. Bởi vì chúng ta đang sử dụng đang phân phối và một thư viện mà chúng tôi đã chỉ được using-- --It chỉ lần thứ hai chúng tôi đã thực hiện Pset này, những điều điên rồ có thể xảy ra với thiết bị của bạn, và bạn muốn để thấy rằng ra ngay bây giờ so với sau này. 

Bởi vì nếu đó là đêm thứ năm hoặc nó Tối thứ Tư và vì một lý do thiết bị của bạn chỉ cần không muốn chạy với thư viện hoặc với phân phối mã, mà phương tiện bạn thậm chí không thể bắt đầu thực hiện việc mã hóa. Bởi vì bạn không thể kiểm tra để xem nếu nó hoạt động. Không gonna của bạn có thể để xem nếu nó biên dịch. Bạn muốn chăm sóc những đầu tuần, khi bạn vẫn có thể gửi email cho tôi hoặc một trong các TF khác, và chúng ta có thể có được những cố định. Bởi vì những người đang có vấn đề mà sẽ ngăn chặn bạn từ thực hiện bất kỳ tiến bộ thực sự. Nó không giống như một lỗi, mà bạn có thể chỉ cần loại bỏ qua. Nếu bạn đang gặp vấn đề với bạn thiết bị hoặc mã phân phối, bạn thực sự muốn nhận được rằng thực hiện quan tâm của sớm hơn là sau đó. Vì vậy, ngay cả khi bạn không gonna thực bắt đầu viết mã, tải về phân phối mã, đọc spec, hãy chắc chắn tất cả mọi thứ đang làm việc ở đó. OK? Nếu bạn chỉ có thể làm điều đó, tôi hứa hẹn cuộc sống của bạn sẽ được dễ dàng hơn. Và như vậy bạn có thể sẽ để làm điều đó ngay bây giờ phải không? OK. Vì vậy, bất kỳ câu hỏi đó? Bất kỳ điều logistic? Tất cả mọi người là tốt? OK. 

Disclaimer đối với những người bạn trong phòng và trực tuyến. Tôi sẽ phải cố gắng để chuyển đổi giữa PowerPoint trong thiết bị bởi vì chúng ta sẽ được làm một số mã hóa hiện nay do nhu cầu phổ biến của vô danh đề nghị thăm dò ý kiến ​​tôi đã gửi ra tuần trước. Vì vậy, chúng tôi sẽ làm một số mã hóa. Vì vậy, nếu các bạn cũng muốn cháy lên thiết bị của bạn, và bạn nên đã nhận được một email từ tôi, với một tập tin mẫu. Xin vui lòng làm điều đó. 

Vì vậy, chúng ta sẽ nói về GDB, mà là một trình gỡ lỗi. Nó sẽ giúp bạn loại tìm ra nơi mọi thứ đang đi sai trong mã của bạn. Nó thực sự chỉ là một cách để bạn có thể bước thông qua mã của bạn như nó đang xảy ra, và có thể in ra các biến hoặc xem những gì đang thực sự xảy ra dưới mui xe các câu chương trình của bạn chỉ cần chạy, nó giống như đứt gãy, và bạn giống như, không có ý tưởng những gì vừa xảy ra ở đây. Tôi không biết những dòng nó không thành công tại. Tôi không biết nơi mà nó đã đi sai. Vì vậy, GDB sẽ giúp bạn với điều đó. Ngoài ra, nếu bạn quyết định tiếp tục có, và mất 61, nó sẽ thực sự, thực sự là của bạn người bạn tốt nhất, vì tôi có thể cho bạn biết bởi vì tôi đang đi qua lớp đó. 

Chúng ta sẽ nhìn vào nhị phân tìm kiếm, nếu các bạn nhớ các ví dụ tuyệt vời cuốn sách điện thoại cảnh tượng từ lớp học. Chúng tôi sẽ thực hiện điều đó, và đi bộ qua đó hơn một chút, và sau đó chúng ta sẽ thông qua bốn các loại khác nhau, đó là bong bóng, Lựa chọn, chèn, và Merge. Cool. Vì vậy, GDB như tôi đã đề cập, là một trình gỡ lỗi. Và đây là những loại lớn điều, các chức năng lớn hoặc lệnh mà bạn sử dụng trong GDB, và tôi sẽ đi bộ bạn thông qua một bản demo của nó trong một giây. 

Vì vậy, đây không phải chỉ là sẽ ở lại trừu tượng. Tôi sẽ cố gắng và làm cho nó như bê tông nhất có thể cho các bạn. Vì vậy, phá vỡ. Nó hoặc là sẽ được nghỉ như, một số số, mà đại diện cho một dòng trong chương trình của bạn, hoặc bạn có thể đặt tên cho một chức năng. Vì vậy, nếu bạn nói phá vỡ chính, nó sẽ dừng lại ở chính, và cho phép bạn đi bộ qua chức năng đó. 

Tương tự như vậy, nếu bạn có một số bên ngoài hoạt động như trao đổi hoặc Cube, mà chúng ta nhìn vào tuần trước. Nếu bạn nói phá vỡ một trong những, bất cứ khi nào chương trình của bạn đạt rằng, nó sẽ chờ đợi cho bạn để nói với nó làm gì. Trước khi nó sẽ chỉ thực hiện, do đó bạn có thể thực sự bước vào bên trong chức năng và xem những gì đang xảy ra. Vì vậy, tiếp theo, chỉ cần bỏ qua trên dòng tiếp theo, đi qua các chức năng. Bước. Đây là tất cả trừu tượng ít. Vì vậy, tôi chỉ cần đi để chạy qua chúng, nhưng bạn sẽ thấy chúng được sử dụng trong một giây. 

Bước vào một chức năng. Vì vậy, như tôi đã nói, như với Swap, nó sẽ cho phép bạn thực sự là nếu bạn như thể chất bước vào bên trong, bạn có thể gây rối với các biến, in ấn ra những gì họ đang có, xem những gì đang xảy ra. Danh sách theo nghĩa đen sẽ chỉ cần in ra các mã xung quanh. Vì vậy, nếu bạn loại quên nơi bạn đang ở trong chương trình của bạn, hoặc bạn đang tự hỏi những gì đang xảy ra xung quanh nó, điều này sẽ chỉ in ra một phân khúc thích của năm hay sáu đường xung quanh nó. Vì vậy, bạn có thể định hướng về nơi bạn đang ở. 

In một số biến. Vì vậy, nếu bạn có quan trọng như trong Caesar, rằng chúng tôi sẽ xem xét. Bạn có thể nói In chính tại bất kỳ điểm nào. Nó sẽ cho bạn biết những gì giá trị là như vậy đó, có thể ở đâu đó trên đường đi, bạn ghi đè lên chìa khóa của bạn. Bạn thực sự có thể nói rằng vì bạn thực sự có thể quan sát giá trị đó. 

Trong người dân địa phương, chỉ cần in ra biến địa phương của bạn. Vì vậy, bất cứ lúc nào bạn đang trong một vòng lặp, và bạn chỉ muốn xem như, oh. Tôi của tôi là gì? Giá trị quan trọng này là gì mà tôi khởi tạo ở đây? Được thông báo vào thời điểm này là gì? Nó sẽ chỉ in tất cả của những người, do đó bạn không phải cá nhân nói, In I. In tin nhắn. In Key. Và sau đó hiển thị. Có gì đó không được như bạn bước qua chương trình, nó sẽ chỉ cần đảm bảo rằng đó là hiển thị một số biến nhất định tại mỗi điểm. Vì vậy mà bạn also-- --it là loại một phím tắt nơi bạn không có để tiếp tục đi như thế, oh. In Key hoặc In I. Nó chỉ sẽ tự động làm điều đó cho bạn. 

Vì vậy, với điều đó, chúng ta sẽ để xem cách này đi. Tôi sẽ cố gắng và chuyển đổi qua thiết bị của tôi. Xem nếu tôi có thể làm điều này. Tất cả. Chúng tôi chỉ cần đi để nhân bản nó. Không có gì là điên trên máy tính xách tay của tôi anyways. OK. Điều này cần phải được thế này. Đó là quá nhỏ bé. Hãy xem nếu chúng ta có thể làm điều này. 

OK. Alice rõ ràng là đang gặp khó khăn đây chỉ là một chút, nhưng chúng tôi sẽ nhận được nó trong một Momento. OK. Chúng tôi chỉ là đi để tăng này. OK. Tất cả mọi người có thể loại thấy rằng? Có lẽ một chút? Tôi biết đó là một chút nhỏ. Bạn có thể không khá ra làm thế nào để làm cho lớn hơn này. Nếu có ai biết. Có ai biết làm thế nào để làm cho nó lớn hơn? OK. Chúng tôi sẽ để cuộn với nó. Không quan trọng dù sao bởi vì nó chỉ đó là mã mà các bạn nên có. 

Điều quan trọng hơn là thiết bị đầu cuối ở đây. Và chúng tôi có ở đây Tại sao nó là quá nhỏ? Cài đặt. Oh. Đúng Ike. Làm thế nào đây? Ra khỏi đó. Là tốt hơn cho tất cả mọi người? OK ,. Cool. 

Bạn biết khi bạn đang ở trong một CS khó khăn kỹ thuật lớp là loại một phần của the-- Vì vậy, chúng ta cần xóa này. OK. Vì vậy, ngay tại đây trong phần, mà chúng tôi có ở đây. Caesar là một tập tin thực thi. Vì vậy, tôi đã làm cho nó. Vì vậy, có một điều nhận ra với GDB là nó chỉ hoạt động trên các tập tin thực thi. Vì vậy, bạn không thể chạy nó trên một dotsy. Bạn phải thực sự làm chắc chắn rằng mã của bạn biên dịch, và rằng nó thực sự có thể được chạy. 

Vì vậy, hãy chắc chắn rằng nếu nó không biên dịch, làm cho nó biên dịch, để bạn có thể loại chạy qua nó. Vì vậy, để bắt đầu GDB, tất cả các bạn làm, Gloria loại GDB, và sau đó chỉ tập tin mà bạn muốn. Tôi luôn luôn đánh sai Caesar. Nhưng bạn muốn chắc chắn vì nó là một thực thi, ti chấm đèn flash để có nghĩa là bạn đang đi để chạy CSI bạn sẽ thực hiện tập tin này hoặc với trình gỡ rối. OK. Vì vậy, bạn làm điều đó, bạn sẽ có được loại này vô nghĩa. Nó chỉ là tất cả mọi thứ về gỡ rối. Bạn không thực sự phải lo lắng về nó ngay bây giờ. Và như bạn thấy, chúng tôi có điều này dấu ngoặc mở, GDP, dấu ngoặc đóng, và chỉ cần loại trông giống như dòng lệnh của chúng tôi, phải không? 

Vì vậy, những gì chúng tôi muốn do-- --So, Điều đầu tiên là chúng tôi muốn chọn một nơi để phá vỡ nó. Vì vậy, có một lỗi Caesar trong chương trình này mà tôi giới thiệu, đó là chúng ta sẽ tìm hiểu. Điều gì nó là nó có đầu vào Barfoo trong tất cả các mũ, và vì một lý do nó không thay đổi A. Nó chỉ là lá nó một mình, có phải là tất cả mọi thứ khác chính xác, nhưng bức thư thứ hai A vẫn không thay đổi. Vì vậy, chúng tôi sẽ cố gắng và tìm ra lý do tại sao đó là. Vì vậy, điều đầu tiên bạn thường muốn làm bất cứ khi nào bạn bắt đầu vào GDB là tìm ra nơi để phá vỡ nó. 

Vì vậy, Caesar là một chương trình khá ngắn. Chúng tôi chỉ có một chức năng, phải không? Chức năng của chúng tôi trong Caesar là gì? Chỉ có một chức năng, chính quyền? Chính là một chức năng cho tất cả các chương trình của bạn. Nếu bạn không có chính, tôi có thể có một chút lo lắng ngay bây giờ, nhưng tôi hy vọng tất cả các bạn đã có chính trong đó. Vì vậy, những gì chúng tôi có thể làm chúng ta là có thể chỉ phá vỡ chính, chỉ cần như thế. Vì vậy, nó nói, OK. Chúng tôi thiết lập một breakpoint của chúng tôi ở đó. 

Vì vậy, bây giờ điều cần nhớ là Caesar mất một đối số dòng lệnh bên phải và chúng tôi đã không làm điều đó bất cứ nơi nào được nêu ra. Vì vậy, những gì bạn làm là khi bạn thực sự đi để chạy các chương trình, bất kỳ chương trình mà bạn chạy trong GDB cần dòng lệnh đối số, bạn sẽ đầu vào khi bạn lần đầu tiên bắt đầu chạy nó. Vì vậy, trong trường hợp này, chúng tôi làm Chạy với khóa ba. Và nó sẽ thực sự bắt đầu. 

Vì vậy, nếu bạn thấy ở đây, chúng tôi có Nếu RC là không bằng 2. Vì vậy, nếu các bạn có tất cả tập tin đó mà tôi gửi lên bạn sẽ thấy rằng đó là giống như Dòng đầu tiên chức năng chính của chúng tôi, phải không? Nó kiểm tra để xem nếu chúng ta có số lượng chính xác của các đối số. Vì vậy, nếu bạn đang tự hỏi nếu RC là chính xác, bạn có thể làm một cái gì đó giống như In RC. RC là hai, đó là những gì chúng ta mong đợi, phải không? 

Vì vậy, chúng ta có thể đi tiếp, và tiếp tục thông qua. Vì vậy, chúng tôi có một số trọng điểm có. Và chúng tôi có thể in ra chìa khóa của chúng tôi để đảm bảo rằng đó là đúng. Thú vị. Không hẳn những gì chúng tôi mong đợi. Vì vậy, có một điều nhận ra với GDB cũng là rằng nó không phải cho đến khi bạn thực sự đạt Tiếp theo, các dòng mà bạn chỉ thấy được thực thi. Vì vậy, trong trường hợp này chính chưa được ấn định nào. Vì vậy, chính là một số giá trị rác mà bạn nhìn thấy ở phía dưới đó. Âm $ 120-- --It của một tỷ và điều gì đó kỳ lạ phải không? Đây không phải là chính mà chúng ta mong đợi. Nhưng nếu chúng ta nhấn Next, và sau đó chúng tôi cố gắng và phím Print, đó là ba. 

Mọi người đều nhìn thấy điều đó không? Vì vậy, nếu bạn nhận được một cái gì đó rằng bạn có giống, chờ đợi. Điều này là hoàn toàn sai, và tôi không biết làm thế nào điều này sẽ xảy ra bởi vì tất cả tôi muốn để làm được gán một số, một biến, hãy thử nhấn Tiếp theo, hãy thử in nó một lần nữa, và thấy rằng nếu các công trình. Bởi vì nó chỉ sẽ thực hiện và thực sự chỉ định một cái gì đó sau khi bạn nhấn Next. Có ý nghĩa với tất cả mọi người? Uh huh? 

SPEAKER 2: Khi bạn ngẫu nhiên số có nghĩa là gì? 

SPEAKER 1: Nó chỉ là ngẫu nhiên. Nó chỉ là rác. Nó chỉ là một cái gì đó của bạn máy tính sẽ chỉ định một cách ngẫu nhiên. Cool. Vì vậy, bây giờ chúng ta có thể di chuyển qua, và như vậy bây giờ chúng tôi có GetString văn bản đơn giản này. Vì vậy, hãy để tôi chỉ giới thiệu những gì sẽ xảy ra khi chúng ta nhấn Next ở đây. GDB của chúng tôi loại biến mất, phải không? Đó là bởi vì GetString bây giờ được thực hiện, phải không? Vì vậy, khi chúng ta nhìn thấy văn bản đơn giản bằng GetString, dấu ngoặc mở và dấu ngoặc, và chúng tôi nhấn Next, có thực tế thực hiện ngay bây giờ. Vì vậy, nó đang đợi chúng tôi nhập vào một cái gì đó. 

Vì vậy, chúng ta sẽ phải nhập vào thực phẩm của chúng tôi là những gì nó không như tôi đã nói với bạn và chỉ nói rằng đó là thực hiện hoàn thành, đóng cửa khung có nghĩa là nó thoát ra khỏi vòng lặp đó. Vì vậy, chúng ta có thể nhấn Next, và bây giờ, như tôi chắc chắn rằng bạn đang quen thuộc từ Caesar, đây là, dòng này sẽ làm những gì. Nó cho Int tôi bằng 0, N bằng Strlen, văn bản đơn giản, và sau đó Tôi là ít hơn n, I, cộng với, cộng. Vòng lặp này sẽ làm là gì? Mở tin nhắn của bạn. Cool. Vì vậy, hãy bắt đầu làm điều đó. 

Vì vậy, nên tình trạng này phù hợp, cho một đầu tiên của chúng tôi? Nếu đó là một B, đó là văn bản đơn giản I. Chúng tôi có thể nhận được thông tin về người dân địa phương của chúng tôi. Vì vậy, tôi là số không, và nếu sáu, chúng ta mong đợi, và quan trọng của chúng tôi là ba. Tất cả những gì có ý nghĩa, phải không? Những con số này là tất cả chính xác những gì họ cần. Vì vậy, ngâm nga? SPEAKER 3: Tôi có số ngẫu nhiên cho tôi. SPEAKER 1: Vâng, chúng ta có thể check-- --we có thể trò chuyện về điều đó trong một giây. Nhưng bạn nên nhận được điều này. Vì vậy, nếu chúng ta có một vốn B cho một đầu tiên của chúng tôi, tình trạng này nên bắt nó, phải không? Vì vậy, nếu chúng ta nhấn Next, chúng ta thấy Nếu đây là thực sự thực hiện. Bởi vì nếu bạn đang theo dõi cùng trong mã của bạn, dòng này ở đây, nơi đồng bằng văn bản tôi được thay thế bằng số học này, chỉ thực hiện nếu Nếu điều kiện là đúng phải không? 

GDB chỉ sẽ cho bạn thấy những điều thực sự thực hiện. Vì vậy, nếu tình trạng này Nếu không được đáp ứng, đó là chỉ cần đi để chuyển sang dòng tiếp theo. OK? Vì vậy, chúng tôi có điều đó. Khung này có nghĩa là nó đóng cửa ra của vòng lặp đó bây giờ. Vì vậy, nó sẽ bắt đầu lại. Chỉ cần như thế. Vì vậy, chúng tôi có thể nhận được thông tin về người dân địa phương của chúng tôi ở đây, và chúng ta thấy rằng đầu tiên của chúng tôi thư đã thay đổi, phải không? Nó bây giờ là một E, như nó phải được. Vì vậy, chúng tôi có thể tiếp tục. 

Và chúng tôi có kiểm tra này. Và việc kiểm tra này nên làm việc, phải không? Đó là A. Nó nên được thay đổi ba chữ cái về phía trước. Nhưng nếu bạn thông báo, chúng tôi có được một cái gì đó khác nhau. Vì vậy, trong trường hợp này lên đây, nó bắt nó, và để dòng này thực hiện, mà sửa đổi B. của chúng tôi Nhưng, trong trường hợp này đây, chúng tôi có mà nó chỉ bỏ qua nó, và đã đi đến [? L SIFF. ?] Vì vậy, một cái gì đó đang xảy ra ở đó. Điều đó nói cho bạn đó là, chúng ta biết rằng nó nên bắt ở đây, nhưng nó không phải. Bất cứ ai có thể xem những gì chúng tôi vấn đề là trong dòng đó? Đó là một điều rất phút. Và bạn cũng có thể nhìn vào code của bạn. Nó cũng line-- quên những gì nó là dòng trong there-- nhưng nó trong [không nghe được]. Có? 

SPEAKER 4: Đó là vào lớn hơn trang nếu bạn đọc nó trong cuốn sách. SPEAKER 1: Chính xác. Vì vậy, các trình gỡ lỗi không thể nói bạn đó, nhưng chương trình gỡ rối có thể giúp bạn xuống một dòng mà bạn biết là không hoạt động. Và đôi khi, đặc biệt là khi sau này trong học kỳ, khi bạn đang đối phó với một trăm, một trăm vài dòng mã, và bạn không biết nơi mà nó thất bại, đây là một cách tuyệt vời để làm điều đó. Vì vậy, chúng tôi tìm thấy lỗi của chúng tôi. Bạn có thể sửa chữa nó trong tập tin của bạn, và sau đó bạn có thể chạy nó một lần nữa, và tất cả mọi thứ sẽ làm việc hoàn hảo. Và điều lớn nhất là điều này có thể có vẻ như, OK. Yeah. Cool. Bạn biết những gì bạn đang tìm kiếm. Vì vậy, bạn biết phải làm gì. 

GDB có thể được siêu hữu ích bởi vì bạn có thể in ra tất cả những điều mà bạn sẽ không được. Đó là hữu ích hơn nhiều so với printf. Có bao nhiêu bạn sử dụng như printf để tìm ra nơi một lỗi là, phải không? Vì vậy, với điều này, bạn không phải tiếp tục đi trở lại, và như ý kiến ​​trong Printf, hoặc cho ý kiến ​​ra, và tìm ra những gì bạn nên in. Điều này thực sự chỉ cho phép bạn bước qua, in ra những thứ như bạn đang trải qua, vì vậy, bạn có thể quan sát cách họ thay đổi trong thời gian thực, như chương trình của bạn đang chạy. 

Và nó mất một ít chút về việc sử dụng để. Tôi rất muốn giới thiệu chỉ loại trở thành một chút thất vọng với nó cho ngay bây giờ. Nếu bạn dành một giờ qua tuần tới học cách sử dụng GDB, bạn sẽ tiết kiệm cho mình rất nhiều thời gian sau này. Và theo nghĩa đen. chúng tôi nói này để người mỗi năm, và tôi nhớ khi tôi đã lớp học, tôi đã như thế, tôi sẽ bị phạt. Không. Pset 6 đã vào sân và tôi đã như thế, tôi sẽ học làm thế nào để sử dụng GDB bởi vì tôi không biết những gì đang xảy ra ở đây. 

Vì vậy, nếu bạn dành thời gian để sử dụng nó trên chương trình nhỏ hơn rằng bạn sẽ được làm việc trên, như làm việc thông qua một cái gì đó như Visionare, như thế này. Hoặc nếu bạn muốn thực hành thêm, tôi chắc chắn Tôi có thể đến với các chương trình lỗi, để bạn có thể gỡ lỗi nếu bạn muốn. 

Nhưng nếu bạn chỉ mất một thời gian để có được sử dụng nó, chỉ chơi đùa với nó, nó sẽ thực sự phục vụ bạn tốt. Và nó thực sự là một trong những điều mà bạn chỉ phải cố gắng, và có được bàn tay của bạn bẩn với, trước khi bạn thực sự hiểu nó. Tôi thực sự chỉ hiểu nó một lần Tôi đã phải debug việc với nó, và nó đẹp hơn nhiều để có một ý tưởng làm thế nào để gỡ lỗi càng sớm càng tốt. OK. Cool. Tôi biết đó là loại giống như một khóa học sụp đổ trong GDB, và tôi chắc chắn sẽ làm việc trên nhận được những nhìn lớn hơn thời gian tới. Cool. 

Vì vậy, nếu chúng ta trở lại PowerPoint của chúng tôi. Điều này sẽ làm việc? AWH. Vâng. OK. Vì vậy, nếu bạn cần bất kỳ những người một lần nữa, có trong danh sách. Vì vậy, tìm kiếm nhị phân, mà tất cả mọi người nhớ lại cảnh tượng tuyệt vời của David trích xuất sách điện thoại trong một nửa. Tôi không thực sự có được sách điện thoại nữa, bởi vì như nơi nào bạn nhận được sách điện thoại những ngày này? Tôi thực sự không biết. Tìm kiếm nhị phân. Có ai nhớ cách tìm kiếm nhị phân công trình? Bất cứ ai ở tất cả? Yeah? SPEAKER 5: Bạn biết khi nào bạn nhìn vào đó một nửa nó sẽ được ở, Trên cơ sở đó, và thoát khỏi một nửa khác. 

SPEAKER 1 Chính xác. Vì vậy, tìm kiếm nhị phân, nó là loại a-- --we thích gọi nó là phân chia và chinh phục. Vì vậy, những gì bạn sẽ làm là bạn sẽ nhìn ở giữa, và bạn sẽ thấy nó có phù hợp những gì bạn đang tìm kiếm. Và nếu không, sau đó bạn cố gắng tìm ra, là nó sẽ bị bỏ lại một nửa hoặc nửa bên phải. Vì vậy, đây có thể là nếu bạn đang tìm kiếm tại cái gì đó là chữ cái là, bạn nhìn thấy, oh. Có Allison đến trước khi M? Vâng. Vì vậy, chúng ta sẽ nhìn vào nửa đầu. 

Hoặc nó có thể là giống như với các con số. Bất cứ điều gì mà bạn có thể so sánh, nó có thể được sắp xếp. Bạn có thể sử dụng tìm kiếm nhị phân trên. Vì vậy, bất cứ ai nhớ này đồ thị hoặc này là gì? Nó phức tạp tiệm cận. Vì vậy, đồ thị này chỉ mô tả bao lâu sẽ đưa bạn đến giải quyết một vấn đề như bạn tăng số lượng các điều mà bạn đang sử dụng. 

Vì vậy, chúng tôi có tồn tại, đó là thời gian tuyến tính. Nếu N hơn hai, đó là hơi tốt hơn, vẫn phát triển nhanh chóng. Và sau đó chúng tôi đã đăng nhập, đó là những gì chúng ta xem xét tìm kiếm nhị phân. Nếu chúng tôi nhận thấy, là vấn đề của bạn được lớn hơn nhiều và nhiều hơn, thời gian nó sẽ đưa bạn để giải quyết nó không thực sự tăng nhiều. Nó giống như so sánh ở đây trong đầu. Bạn giống như, OK. Bất cứ điều gì ở đây không thực sự vấn đề mà chúng ta sử dụng, nhưng bạn nhận ra một triệu, một tỷ đồng. Bạn đang cố gắng để tìm some-- --you're cố gắng tìm một cây kim trong một đống cỏ khô. 

Tôi nghĩ rằng bạn muốn vấn đề này. Bạn muốn phức tạp này, không tuyến tính bởi vì đối với tất cả các bạn biết sẽ của bạn được tìm kiếm thông qua mỗi kim cá nhân, điều cỏ khô, cố gắng để tìm kim của bạn. Và đó không phải là quá vui vẻ theo ý kiến ​​của tôi. Tôi thích nhanh. Tôi thích hiệu quả. Và sinh viên chăm chỉ như bạn kẻ đang có, bạn biết làm việc thông minh hơn, không khó khăn hơn loại điều, làm thế nào bạn có thể tạo nên các thuật toán. 

Vì vậy, chúng ta sẽ đi bộ thông qua chỉ là một ví dụ nhanh chóng. Tôi nghĩ các bạn nên có một bàn tay lên tìm kiếm nhị phân, nhưng trong trường hợp bất cứ ai là một chút mờ, muốn củng cố nó, chúng ta sẽ chỉ cần đi thông qua một ví dụ ở đây. Vì vậy, chúng tôi đang tìm kiếm nếu mảng chứa bảy. 

Vì vậy, điều đầu tiên chúng tôi làm là nhìn ở giữa, phải không? Và cũng có thể bạn sẽ được mã hóa Tìm kiếm nhị phân chỉ trong một giây. Vì vậy, nó sẽ được vui vẻ. Vì vậy, chúng ta hãy nhìn vào mảng nhỏ giữa 3. Có 3 bằng 7? Không. Đó là sáu. Vì vậy, nó ít hơn hoặc lớn hơn bảy? Ít hơn. Vâng. Tốt công việc guys. Tôi cảm thấy tôi thích nên tôi có kẹo vì tôi muốn ném nó ra vào bãi. Đó là những gì tôi sẽ làm trong tuần tiếp theo. Nó sẽ giữ cho bạn kẻ sắc nét. 

Vì vậy, chúng ta vứt đi mà nửa đầu, phải không? nó là ít hơn. chúng ta biết rằng tất cả mọi thứ trên đó phía bên tay trái là có được ít hơn những gì chúng tôi đang thực sự tìm kiếm. Vì vậy, không có nhu cầu chú ý đến nó. Chỉ cần quên nó. Vì vậy, bây giờ chúng ta nhìn vào phía bên tay phải của chúng tôi, và chúng ta nhìn vào giữa ở đó, và bây giờ là chín. Vì vậy, 9 is-- --Everyone? Lớn hơn những gì chúng tôi tìm kiếm, phải không? Vì vậy, chúng ta sẽ ném đi tất cả mọi thứ bên phải. Như thế. Bây giờ, tất cả chúng tôi đang trái với là một. Vì vậy, chúng tôi kiểm tra, là một trong những gì này chúng tôi đang tìm kiếm? nó được. Chúng tôi tìm thấy những gì chúng tôi muốn. Vì vậy, chúng tôi đang thực hiện. Bilinear Search. 

Và nếu bạn thấy, chúng tôi có bảy đầu vào đó. Nó chỉ đưa chúng tôi như ba lần, nhưng nếu bạn đang làm như một tỷ đồng, Các bạn có biết có bao nhiêu bước nó sẽ mất nếu chúng ta có bốn tỉ những thứ? Bất kỳ dự đoán? Đó là 32. 32 bước để tìm một cái gì đó trong bốn tỷ phần tử mảng vì quyền hạn của hai. Vì vậy, hai là 32, là bốn tỷ. 

Vì vậy, cách khá điên rồ bạn vẫn còn trong vòng như một số lượng khá nhỏ bước để tìm một cái gì đó trong bốn tỷ yếu tố. Vì vậy, trên lưu ý rằng, chúng tôi sẽ mã này vậy các bạn có thể thực sự loại xem cách làm việc này. Được rồi, vậy các bạn có thể mã. Tôi sẽ để cho các bạn nói chuyện một chút. Nhận biết những người xung quanh bạn, mà là những gì một người nào đó muốn từ phần cuối. 

Vì vậy, nhận biết những người xung quanh bạn. Nói chuyện một chút. Và tất cả tôi muốn từ bạn kẻ ngay bây giờ chỉ là cố gắng tạo ra một phác thảo của giả. OK? Whoa. Tất cả tôi muốn từ các bạn là bạn chỉ cần đi để điền vào trong trường hợp trong khi điều này. Vì vậy, tôi đã thiết lập các trên và giới hạn thấp hơn mà đại diện đầu và cuối mảng của chúng tôi. Và bạn sẽ thực sự lặp qua và tìm ra những gì chúng ta đang làm trong vòng lặp trong khi điều này. 

Vì vậy, nếu bạn có thể tìm out-- tôi có một gợi ý there-- các trường hợp là gì mà chúng ta có ở đây? Vì vậy, nếu bạn muốn tìm ra trường hợp, chúng tôi sẽ giả những và sau đó chúng tôi sẽ thực sự mã chúng. Và nó sẽ được, tôi nghĩ, hy vọng nó sẽ thấy là một chút dễ dàng hơn bạn mong đợi. Bởi vì nó không phải là nhiều mã, trên thực tế, đó là thực sự mát mẻ. 

Mm-hm? 

HỌC SINH: [không nghe được]? GIẢNG: Có. Có cái gì đó tìm ở giữa. 

SINH VIÊN: Vì vậy, chúng ta có thể sử dụng đó. OK. 

GIẢNG: Hoàn hảo. Vì vậy, đó là điều đầu tiên chúng ta cần làm. Vì vậy, tìm thấy giữa. Tuyệt vời. Vì vậy, bạn có một ý tưởng làm thế nào chúng ta có thể thực sự tìm thấy giữa với mã? 

HỌC SINH: Yeah. n hơn 2? GIẢNG: Vì vậy, n hơn 2. Vì vậy, có một điều cần nhớ là giới hạn trên và dưới của bạn thay đổi. Chúng tôi tiếp tục thắt phần của mảng, chúng tôi đang tìm kiếm. Vì vậy, n trên 2 sẽ chỉ làm việc cho điều đầu tiên chúng tôi làm. Vì vậy, lấy trên và dưới vào tài khoản, làm thế nào chúng ta có thể nhận được rằng yếu tố trung? Bởi vì chúng tôi muốn giữa giữa trên và dưới, phải không? Mm-hm? 

HỌC SINH: [không nghe được]. 

GIẢNG: Vì vậy, chúng tôi có một số trung lưu. Và nó sẽ được trên cộng thấp hơn 2. Tuyệt vời. Hiện chúng tôi đi. Một dòng xuống. Các bạn đang trên đường của bạn. Vì vậy, bây giờ chúng ta có của chúng tôi trung, những gì chúng tôi muốn làm gì? Chỉ cần nói chung. Bạn không cần phải mã nó. Vâng. HỌC SINH: [không nghe được]? GIẢNG: Vì vậy, nó cộng vì bạn việc tìm kiếm trung bình giữa hai trong số họ. Vì vậy, nếu bạn nghĩ về họ như loại tăng từ hai bên, suy nghĩ về nó khi bạn tiếp cận giữa, bạn muốn như thế. Vì vậy, nếu bạn đang ở hai bên của trung bình, và chúng tôi có giống như 5 và 7. Khi bạn thêm chúng với nhau bạn nhận được 12, bạn chia cho 2, 6. 

Đôi khi thật khó để giải thích lý do tại sao mà các công trình, nhưng nếu bạn làm việc thông qua một ví dụ đôi khi, nó sẽ giúp bạn tìm ra nếu nó phải được cộng hoặc trừ. Vâng. 

HỌC SINH: [không nghe được] chính xác ở giữa nếu họ đã có một trường hợp có rất nhiều con số nhỏ hơn và như một số lượng lớn? 

GIẢNG: Vì vậy, tất cả các bạn cần là giữa mảng. Vì vậy, nếu bạn đã có một loạt các con số nhỏ và sau đó một số thực sự lớn ở cuối, nó không quan trọng. Tất cả những vấn đề là họ đang sắp xếp, bạn chỉ cần muốn nhìn vào giữa mảng bởi vì bạn vẫn còn cắt vấn đề của bạn trong một nửa. Cool. Vì vậy, bây giờ chúng ta có trung bình, chúng ta làm gì tiếp theo? 

HỌC SINH: So sánh. GIẢNG: Các so sánh. Vì vậy, so sánh giữa để value_wanted. Cool. Vì vậy, bạn nhìn thấy ở đây chúng tôi có giá trị này, chúng tôi muốn ở đây. Hãy nhớ rằng đây là một mảng. Vì vậy, trung đề cập đến chỉ số. Vì vậy, chúng tôi muốn làm giá trị trung bình. Đừng quên nếu bạn muốn để so sánh, bình đẳng đôi. Bạn làm đơn bằng bạn chỉ cần đi để gán lại nó, và sau đó, tất nhiên, đó là sẽ là giá trị bạn muốn. Vì vậy, không làm điều đó. 

Vì vậy, chúng ta sẽ xem các giá trị ở giữa bằng với giá trị chúng ta muốn. Đừng quên niềng răng của bạn. Dropbox sẽ biến mất. Vì vậy, chúng ta làm gì trong trường hợp này? Nếu đó là những gì chúng ta muốn quay trở lại? Chúng tôi đang cố gắng để nói. 

HỌC SINH: In tắt. 

GIẢNG: Vâng, chúng tôi không muốn in ra. Vì vậy, đây là một bool ở đây, vì vậy chúng tôi muốn trở lại đúng hay sai. Chúng ta đang nói, là con số này một [? RRA? ?] Vì vậy, nếu nó là, chúng tôi chỉ trả lại sự thật. Nếu tôi có thể đánh vần đúng. 

HỌC SINH: Tại sao bạn sẽ không quay trở lại không? GIẢNG: Vì vậy, bạn có thể trở về zero nếu bạn muốn. Nhưng trong trường hợp này bởi vì chức năng của chúng tôi trả về một bool, chúng ta cần phải trở về đúng hoặc sai. HỌC SINH: Khi bạn nói rằng biểu thức boolean, bạn có thể thiết lập nó bằng giả? Cũng giống như nếu tôi muốn nói, nếu tình trạng này không được đáp ứng, giống như là trên bằng giả. Nó sẽ hiểu nếu bạn chỉ đặt sai ở phía bên kia? GIẢNG: Yeah. Vì vậy, thực sự nếu bạn bao giờ làm điều gì đó như là trên hoặc thấp hơn, trả về đúng hay sai và đó là phong cách thực sự xấu nói bằng bằng đúng hay equals bằng giả. Bạn muốn sử dụng kết quả đó như chính nó như là kiểm tra của bạn. Không phải những gì tôi muốn. Đó là những gì tôi muốn. Vì vậy, trong trường hợp bạn đang yêu cầu về một cái gì đó giống như tiết kiệm này trong c. 

Vì vậy, nếu chúng tôi có int main (void) và một cái gì đó như thế này. Và nếu bạn có là trên của một số đầu vào và bạn yêu cầu nếu bạn có thể làm một cái gì đó như thế này? Phải không? HỌC SINH: Tôi đã cố gắng để làm điều đó [không nghe được]. Bởi vì nếu it's-- GIẢNG: Đúng vậy. Vì vậy, bạn muốn điều này là sai lầm, phải không? HỌC SINH: Yeah. GIẢNG: Vì vậy, trong trường hợp này bạn muốn nó để thực thi nếu nó không đúng sự thật. Vì vậy, điều bạn làm mát có này. Vì vậy, nhớ chấm than điểm phủ nhận điều này? Nó nói [không nghe được] có nghĩa là không. Vì vậy, nếu chúng ta nhìn vào chỉ phần này ở đây, bạn muốn nói rằng để đánh giá giả như bạn muốn nó. Không sai là đúng mà có nghĩa là điều này sẽ thực thi. Điều đó có ý nghĩa? HỌC SINH: Yeah. GIẢNG: Awesome. OK. Vì vậy, chúng tôi chỉ có thể trở lại đúng trong trường hợp này. Vì vậy, bây giờ chúng tôi có hai khác trường hợp trong trường hợp này. Hai trường hợp khác của chúng tôi là gì? Hãy làm theo cách này. Vì vậy, hãy bắt đầu với người khác nếu giá trị ở giữa là thấp hơn giá trị chúng ta muốn. Vì vậy, giá trị của chúng tôi ở giữa là ít hơn giá trị mà chúng ta đang tìm kiếm. 

Vì vậy mà ràng buộc làm bạn nghĩ rằng chúng tôi muốn cập nhật? Trên hoặc thấp hơn? Trên? Vì vậy, mà phía của mảng chúng ta sẽ được xem xét? 

HỌC SINH: càng thấp. 

GIẢNG: Chúng tôi chúng ta sẽ được tìm kiếm ở bên trái. Vì vậy, nếu người nào khác ít có giá trị ít hơn. Vì vậy, giá trị trung bình của bạn ở đây là ít hơn những gì chúng ta muốn. Vì vậy, chúng tôi muốn đi phía bên phải của mảng của chúng tôi. Vì vậy, chúng ta sẽ cập nhật ràng buộc thấp hơn của chúng tôi. Vì vậy, chúng tôi sẽ phân công lại thấp hơn của chúng tôi. Và điều gì làm bạn nghĩ thấp nên được? HỌC SINH: Giá trị trung? GIẢNG: Vì vậy, các value-- trung HỌC SINH: Plus 1. GIẢNG: --plus 1. Bất cứ ai có thể cho tôi biết tại sao chúng tôi đã có cộng với 1? 

HỌC SINH: [? Không có giá trị?] là bình đẳng hơn với nó. 

GIẢNG: Đúng vậy. Bởi vì chúng ta đã biết rằng giá trị trung bình của chúng tôi không phải là bằng nó và chúng tôi muốn loại trừ nó từ tất cả tìm kiếm tiếp theo. Nếu bạn quên rằng cộng với 1, điều này sẽ giống như vòng lặp vô thời hạn. Và bạn sẽ chỉ được bắt gặp trong một vòng lặp vô hạn và sau đó bạn sẽ segfault và những điều xấu đi. Vì vậy, luôn luôn đảm bảo rằng bạn không bao gồm cả các giá trị mà bạn chỉ cần nhìn. Vì vậy, chúng tôi chăm sóc đó với một cộng thêm 1. 

Vì vậy, bây giờ chúng tôi có điều kiện cuối cùng của chúng tôi mà tôi luôn luôn vì lợi ích an toàn bạn có thể kiểm tra ở đây, hoặc nếu giá trị tại giữa là lớn hơn giá trị chúng ta muốn. Điều đó có nghĩa rằng chúng ta muốn Mặt nửa trái. Vì vậy, mà một trong những chúng tôi sẽ cập nhật? Thượng. Và điều này sẽ tương đương là gì? Trung trừ đi 1 bởi vì, Tất nhiên, chúng tôi muốn để đảm bảo rằng chúng tôi không nhìn vào đó giá trị trung bình một lần nữa. Và sau đó chúng tôi có nó. Có bấy nhiêu thôi. Đó là tất cả tìm kiếm nhị phân là. Nó không phải là xấu, phải không? Nó giống như 10 dòng mã với không gian trắng. Vì vậy, rất mạnh mẽ, rất hữu ích, bạn sẽ được sử dụng nó trong một trong psets sau này của bạn. Có lẽ không phải thế này, nhưng sau đó. Vì vậy, tìm hiểu nó. Tình yêu nó. Nó sẽ đối xử với bạn tốt. Vì vậy, không ai có bất cứ câu hỏi về tìm kiếm nhị phân? Vâng. 

HỌC SINH: Có vấn đề gì dù n của bạn là chẵn hay lẻ? 

GIẢNG: số Bởi vì chúng tôi bỏ nó vào giữa như một int, nó sẽ chỉ cắt nó. Vì vậy, nó sẽ ở lại một số nguyên và nó sẽ cuối cùng sắp xếp thông qua tất cả mọi thứ. Vì vậy, bạn không phải lo lắng về điều đó. Tất cả mọi người tốt? Tuyệt vời. Cool. Vì vậy, các bạn đã nhận điều này. Slideshow. Vì vậy, như chúng tôi đã nói về, tôi biết David đề cập runtimes phức tạp. 

Vì vậy, trong trường hợp tốt nhất, nó chỉ là một, mà chúng ta gọi là hằng số thời gian. Bất cứ ai có thể cho tôi biết lý do tại sao mà có thể được? Loại kịch bản đó sẽ đòi hỏi? Mm-hm. 

HỌC SINH: [không nghe được] first-- GIẢNG: Vì vậy, giữa là Yếu tố đầu tiên mà chúng tôi đến, phải không? Vì vậy, hoặc một mảng của một hoặc bất cứ điều gì chúng ta đang tìm kiếm chỉ sẽ xảy ra là smack thoa ở giữa. Vì vậy, đó là trường hợp tốt nhất của chúng tôi. Bạn nhận được vào vấn đề thực sự, có lẽ không sẽ đạt tới [không nghe được] thường. Những gì về trường hợp tồi tệ nhất của chúng tôi? Trường hợp xấu nhất của chúng tôi là log n. Và điều đó đã làm với toàn bộ quyền hạn của hai điều mà tôi đã nói. 

Vì vậy, trong trường hợp xấu nhất nó sẽ có nghĩa mà chúng tôi đã để cắt các mảng xuống cho đến khi nó là một phần tử của một. Vì vậy, chúng tôi phải đốn chặt nó xuống một nửa nhiều lần chúng tôi có thể có thể. Đó là lý do tại sao nó log n vì bạn chỉ cần tiếp tục phân chia bởi hai. Vì vậy, giả định, mọi thứ bạn cần phải biết nếu bạn đã từng sẽ sử dụng tìm kiếm nhị phân. Các yếu tố của bạn phải được sắp xếp. Họ phải được sắp xếp bởi vì đó là cách duy nhất bạn có thể biết nếu bạn có thể để ném ra một nửa của nó. 

Nếu bạn có túi lộn xộn này các con số và bạn đang nói, OK, tôi sẽ kiểm tra giữa số lượng và số lượng tôi đang tìm kiếm là ít hơn, tôi chỉ cần đi tự ý ném ra một nửa. Bạn sẽ không biết nếu bạn trong số đó một nửa khác. Danh sách của bạn đã được sắp xếp. Cũng như vậy, điều này có thể đi về phía trước một chút, nhưng bạn cần phải có quyền truy cập ngẫu nhiên. Bạn cần để có thể chỉ đi đến đó yếu tố trung. Nếu bạn phải đi qua thông qua một cái gì đó hoặc nó sẽ đưa bạn thêm bước để có được yếu tố đó giữa, nó không phải đăng nhập nữa vì n bạn đang thêm nhiều công việc hơn vào nó. Và điều này sẽ làm cho một ít ý nghĩa hơn trong hai tuần, nhưng tôi chỉ loại muốn lời nói đầu, cung cấp cho các bạn một ý tưởng về những gì tới. Nhưng những người là hai giả định quan trọng mà bạn cần cho một danh sách nhị phân. Hãy chắc chắn rằng nó được sắp xếp. Đó là một lớn đối với các bạn ngay bây giờ. Và ngày đó chúng ta có thể đi vào phần còn lại của các loại của chúng tôi. Vì vậy, bốn bong bóng sorts--, chèn, lựa chọn, và hợp nhất. Họ là tất cả các loại mát mẻ. Nếu các bạn quyết định đi CS 124, bạn sẽ tìm hiểu về tất cả các loại của các loại. Và nếu bạn là một fan hâm mộ XKCD, có là về truyện tranh thực sự mát mẻ giống như các loại thực sự không hiệu quả, mà tôi khuyên bạn nên bạn sẽ xem xét. Một trong số họ là như hoảng loạn sắp xếp, mà là như thế, oh không, trở về mảng ngẫu nhiên. Hệ thống Shutdown. Để lại. Vì vậy, sự hài hước geeky là luôn luôn tốt. 

Vì vậy, không ai nhớ loại giống như chỉ là một ý tưởng chung làm thế nào bong bóng sắp xếp hoạt động. Bạn có nhớ không? 

HỌC SINH: Yeah. 

GIẢNG: Go cho nó. 

SINH VIÊN: Vì vậy, bạn đang trải qua và nếu nó lớn hơn, sau đó bạn trao đổi hai. 

GIẢNG: Mm-hm. Chính xác. Vì vậy, bạn chỉ cần lặp qua. Bạn hãy kiểm tra hai con số. Nếu một trước khi lớn hơn một sau đó, bạn chỉ cần trao đổi chúng vì vậy mà trong cách này tất cả các con số cao hơn bong bóng lên vào cuối danh sách và tất cả các con số thấp hơn bong bóng xuống. 

Anh ấy đã cho mọi người thấy mát mẻ hiệu ứng âm thanh phân loại video? Đó là loại mát mẻ. Vì vậy, như Robert vừa nói, thuật toán mà bạn chỉ cần bước qua danh sách, trao đổi các giá trị liền kề nếu họ không theo thứ tự. Và sau đó chỉ cần giữ lặp đi lặp lại cho đến khi bạn không thực hiện bất kỳ giao dịch hoán đổi. Vì vậy, không xấu, phải không? Vì vậy, chúng tôi chỉ có một ví dụ nhanh chóng ở đây. Vì vậy, điều này sẽ sắp xếp chúng trong thứ tự tăng dần. Vì vậy, khi chúng tôi đi qua đầu tiên thời gian, chúng tôi xem xét thông qua tám và sáu rõ ràng không phải theo thứ tự, chúng tôi trao đổi chúng. 

Vì vậy, nhìn vào kế tiếp. Tám và bốn không theo thứ tự. Trao đổi chúng. Và sau đó tám và hai, trao đổi chúng. Hiện chúng tôi đi. Vì vậy, vượt qua đầu tiên của bạn sau khi bạn biết rằng số lượng lớn nhất của bạn là có được tất cả các cách ở phía trên bởi vì nó chỉ sẽ liên tục lớn hơn mọi thứ khác và nó chỉ cần đi để bong bóng lên tất cả các cách để kết thúc ở đó. Điều đó có ý nghĩa với tất cả mọi người? Cool. 

Vì vậy, sau đó chúng ta nhìn qua thứ hai của chúng tôi. Sáu và bốn, chuyển đổi. Sáu và thứ hai, chuyển đổi. Và bây giờ chúng tôi có một vài điều theo thứ tự. Vì vậy, cho mỗi đường chuyền mà chúng ta thực hiện thông qua toàn bộ danh sách của chúng tôi, chúng ta biết rằng như thế nhiều số cuối cùng sẽ được sắp xếp. Vì vậy, chúng tôi làm một vượt qua thứ ba, đó là một trong trao đổi. Và sau đó vào thứ tư của chúng tôi vượt qua, chúng tôi đã không khe. Và vì vậy chúng tôi biết rằng chúng tôi mảng đã được sắp xếp. 

Và đó là lớn điều với bong bóng sắp xếp. Chúng ta biết rằng khi chúng ta có không hoán đổi, mà có nghĩa là tất cả mọi thứ là để hoàn tất. Đó là loại như thế nào chúng tôi kiểm tra. Vì vậy, chúng tôi cũng sẽ mã bong bóng loại mà cũng không phải là xấu. Không ai trong số này là xấu. Tôi biết họ có thể có vẻ một chút đáng sợ. Tôi biết khi tôi lấy lớp học, ngay cả khi tôi đang dạy lớp cho lần đầu tiên vào năm ngoái, Tôi đã như thế, làm thế nào để làm điều này? Nó có ý nghĩa về mặt lý thuyết, nhưng làm thế nào để chúng tôi thực sự làm điều này? Đó là lý do tại sao tôi cũng muốn đi bộ thông qua các mã với các bạn ở đây. Vì vậy, tôi có một giả cho các bạn thời gian này. Vì vậy, chỉ giữ điều này trong tâm trí như chúng tôi sắp chuyển qua. Vì vậy, chúng tôi có một số truy cập mà theo dõi giao dịch hoán đổi của chúng tôi, bởi vì chúng tôi cần phải chắc chắn rằng chúng tôi đang kiểm tra đó. Và chúng ta lặp toàn bộ mảng như chúng ta chỉ cần làm với ví dụ này. Nếu phần tử trước lớn hơn các yếu tố sau, nơi chúng tôi đang ở, chúng tôi trao đổi chúng và chúng tôi tăng của chúng tôi truy cập bởi vì ngay khi chúng tôi trao đổi, chúng tôi muốn cho truy cập của chúng tôi biết điều đó. Bất kỳ câu hỏi đó? Một cái gì đó có vẻ buồn cười ở đây. HỌC SINH: Bạn thiết lập các truy cập đến số không mỗi khi bạn đi qua các vòng lặp? Không bạn tiếp tục đi trở lại bằng không mỗi lần? GIẢNG: Không nhất thiết. Vì vậy, những gì xảy ra là chúng tôi đi qua ở đây. Vì vậy, thời gian, hãy nhớ, đây sẽ thực hiện một lần mà không thất bại. Vì vậy, nó sẽ thiết lập truy cập bằng không, sau đó nó sẽ lặp qua. Khi nó lặp thông qua, nó sẽ cập nhật truy cập. Khi nó cập nhật truy cập, khi nó được thực hiện, khi nó đạt đến kết thúc của mảng, nếu danh sách của chúng tôi đã không được sắp xếp, truy cập sẽ được cập nhật. 

Vì vậy, sau đó nó sẽ kiểm tra điều kiện và nó nói, OK, là truy cập lớn hơn không. Nếu có, làm điều đó một lần nữa. Bạn muốn thiết lập lại để khi bạn đi qua, đếm bằng số không. Nếu bạn đi qua một sắp xếp mảng, không có gì thay đổi, điều này không, và bạn trở về danh sách được sắp xếp. Điều đó làm cho tinh thần? HỌC SINH: Nó có thể trong một chút. GIẢNG: OK. Nếu có bất kỳ khác câu hỏi mà đi lên. Vâng. 

HỌC SINH: Điều gì sẽ chức năng là để trao đổi các yếu tố? 

GIẢNG: Vì vậy, chúng tôi thực sự có thể viết rằng nếu chúng ta đang đi sang phải bây giờ. Cool. Vì vậy, trên lưu ý rằng, Alison sẽ chuyển đổi trở lại thiết bị. Nó sẽ được vui vẻ. Và chúng tôi có đẹp của chúng tôi bong bóng sắp xếp điều ở đây. Vì vậy, tôi đã làm xe đạp thông qua mảng. Chúng tôi có giao dịch hoán đổi của chúng tôi là bằng không. Vì vậy, chúng tôi muốn trao đổi liền kề yếu tố nếu họ ra lệnh. Vì vậy, điều đầu tiên chúng ta cần phải làm là lặp qua mảng của chúng tôi. 

Vì vậy, làm thế nào để bạn nghĩ rằng chúng ta có thể lặp qua mảng của chúng tôi? Chúng tôi có cho và i bằng 0. Chúng tôi muốn tôi là ít hơn n trừ đi 1 trừ đi k. Và tôi sẽ giải thích rằng trong một giây. Vì vậy, đây là một tối ưu hóa ở đây, nơi, nhớ làm thế nào tôi đã nói mỗi đường chuyền sau thông qua các mảng chúng tôi biết rằng bất cứ điều gì on-- 

Vì vậy, một đường chuyền sau khi chúng tôi biết rằng điều này đã được sắp xếp. Sau khi hai qua chúng ta đã biết rằng tất cả điều này được sắp xếp. Sau khi ba đi chúng tôi biết đó là sắp xếp. Vì vậy, cách tôi đang lặp lại qua mảng ở đây, là nó làm cho chắc chắn chỉ đi thông qua những gì chúng ta biết là không được phân loại. OK? Đó chỉ là một tối ưu hóa. Bạn có thể viết nó ngây thơ chỉ lặp qua tất cả mọi thứ, nó sẽ chỉ mất nhiều thời gian. Với vòng bốn này nó chỉ là một tối ưu hóa đẹp bởi vì chúng ta biết rằng sau mỗi lần đầy đủ lặp qua mảng ở đây, như mỗi vòng lặp đầy đủ ở đây, chúng ta biết rằng một trong nhiều các yếu tố sẽ được sắp xếp ở cuối. 

Vì vậy, chúng tôi không phải lo lắng về những người. Điều đó có ý nghĩa với tất cả mọi người? Đó là mẹo nhỏ mát mẻ? Vì vậy, trong trường hợp đó, nếu chúng ta đang lặp lại thông qua, chúng tôi biết rằng chúng tôi muốn kiểm tra xem mảng n và n + 1 là theo thứ tự. OK. Vì vậy, đây là giả. Chúng tôi muốn kiểm tra xem mảng n và n + 1 là theo thứ tự. Vì vậy, những gì chúng ta có thể có ở đó? Nó sẽ có một số điều kiện. Nó sẽ là một nếu. 

HỌC SINH: Nếu mảng n là ít hơn mảng n + 1. GIẢNG: Mm-hm. Vâng, nhỏ hơn hoặc lớn hơn. HỌC SINH: Lớn hơn. Sau đó, chúng tôi muốn trao đổi chúng. Chính xác. Vì vậy, bây giờ chúng tôi nhận được vào những gì là cơ chế trao đổi chúng? Vì vậy, chúng tôi đã đi qua một thời gian ngắn, một loại chức năng trao đổi tuần trước. Có ai nhớ nó như thế nào làm việc? Vì vậy, chúng ta không thể gán cho họ, phải không? Bởi vì một trong số họ sẽ bị mất. Nếu chúng ta nói A là bằng B và sau đó B bằng A, tất cả đột nhiên cả hai chỉ bằng B. 

Vì vậy, những gì chúng ta phải làm là chúng tôi có một biến tạm thời đó là sẽ tổ chức một trong những khi chúng ta chúng tôi trong quá trình trao đổi. Vì vậy, những gì chúng tôi có là chúng tôi sẽ có một số int tạm thời bằng đối với: bạn có thể gán cho nó để bất cứ một trong những bạn muốn, chỉ cần chắc chắn rằng bạn theo dõi it-- vậy trong trường hợp này, tôi sẽ gán nó vào mảng n + 1. Vì vậy, đó là sẽ giữ bất cứ điều gì giá trị trong đó khối thứ hai mà chúng ta đang tìm kiếm. 

Và sau đó chúng ta có thể làm là chúng ta có thể đi trước và mảng phân công lại n + 1, bởi vì chúng tôi biết chúng tôi có giá trị lưu trữ. Đây cũng là một trong những lớn things-- Tôi không biết nếu có của bạn có vấn đề mà nếu bạn chuyển đổi hai dòng mã đột nhiên mọi thứ làm việc. Trật tự là rất quan trọng trong CS. Vì vậy, hãy chắc chắn rằng bạn sơ đồ những điều trên nếu có thể như những gì đang thực sự xảy ra. Vì vậy, bây giờ chúng tôi đang đi để phân công lại mảng n + 1, bởi vì chúng tôi biết chúng tôi có giá trị lưu trữ. 

Và chúng ta có thể gán vào mảng n hoặc trong trường hợp này mảng i. Quá nhiều biến. OK. Vì vậy, bây giờ chúng tôi đã bố trí mảng i cộng thêm 1 để bằng những gì trong mảng i. Và bây giờ chúng ta có thể quay trở lại và gán mảng tôi những gì? Bất cứ ai? 

HỌC SINH: 10. 

GIẢNG: 10. Chính xác. Và một điều cuối cùng. Nếu chúng ta đã trao đổi nó bây giờ, những gì chúng ta cần phải làm gì? Một điều gì đó là sẽ để cho chúng tôi nếu chúng ta bao giờ chấm dứt chương trình này? Những gì cho chúng ta biết rằng chúng ta có một danh sách được sắp xếp? Nếu chúng ta không thực hiện bất kỳ giao dịch hoán đổi, phải không? Nếu giao dịch hoán đổi bằng zero vào cuối này. Vì vậy, bất cứ khi nào bạn thực hiện một trao đổi, như chúng tôi chỉ cần làm ở đây, chúng tôi muốn cập nhật giao dịch hoán đổi. Và tôi biết có một câu hỏi trước đó về có thể bạn sử dụng không có hoặc có một thay vì của đúng hay sai. Và đó là điều này không có gì ở đây. Vì vậy, điều này nói nếu không giao dịch hoán đổi. Vì vậy, nếu giao dịch hoán đổi là số không, mà tôi luôn luôn is-- được sự thật của tôi và falses của tôi lẫn lộn. Chúng tôi muốn chúng tôi đánh giá đúng sự thật và nó không phải. Vì vậy, nếu nó không, thì đó là sai. Nếu bạn phủ nhận nó với một [? đập?] nó trở thành sự thật. Vì vậy, sau đó dòng này thực hiện. 

Chân lý và sai lầm và số không và những người nhận được điên. Chỉ cần nếu bạn từ từ đi bộ thông qua đó nó sẽ có ý nghĩa. Nhưng đó là những gì nhỏ này bit mã ở đây không. Vì vậy, đây sẽ kiểm tra xem Chúng ta đã thực hiện bất kỳ giao dịch hoán đổi. Vì vậy, nếu đó là bất cứ điều gì ngoài bằng không, nó sẽ là sai lầm và toàn bộ điều là sẽ thực hiện một lần nữa. Mát mẻ? 

HỌC SINH: không nghỉ làm gì? 

GIẢNG: Phá vỡ chỉ phá vỡ bạn ra khỏi vòng lặp. Vì vậy, trong trường hợp này nó sẽ chỉ muốn kết thúc chương trình và bạn sẽ chỉ có danh sách được sắp xếp của bạn. HỌC SINH: Amazing. GIẢNG: Tôi xin lỗi? SINH VIÊN: Bởi vì trước đây chúng tôi được sử dụng bằng văn bản 1 hơn bằng văn bản không trình bày rằng nếu mà sẽ làm việc hay không. 

GIẢNG: Yeah. Vì vậy, bạn có thể trở lại không hay 1. Trong trường hợp này, bởi vì chúng tôi không thực sự làm bất cứ điều gì với chức năng, chúng tôi chỉ muốn nó để phá vỡ. Chúng tôi không thực sự quan tâm về nó. Phanh cũng tốt nếu nó được sử dụng để phá vỡ ra của bốn tuyến hoặc điều kiện bạn không muốn tiếp tục thực hiện. Nó chỉ đưa bạn ra khỏi chúng. Đó là một chút của một điều sắc thái. Tôi cảm thấy như có rất nhiều tay vẫy, như bạn sẽ tìm hiểu về điều này sớm. 

Nhưng bạn sẽ tìm hiểu về điều này sớm. Tôi hứa. OK. Vì vậy, không tất cả mọi người có được bong bóng sắp xếp? Không quá xấu. Lặp thông qua, trao đổi việc sử dụng một biến temp, và tất cả chúng ta thiết lập ở đó? Cool. Tuyệt vời. OK. Quay lại PowerPoint. Bất kỳ câu hỏi nói chung về những cho đến nay? Cool. Mm-hm. 

HỌC SINH: [không nghe được] int chính thường. Bạn phải có mà cho điều này? 

GIẢNG: Vì vậy, chúng tôi chỉ tìm kiếm chỉ tại các thuật toán phân loại thực tế. Nếu bạn đã có nó trong vòng giống như một chương trình lớn hơn, bạn sẽ có một nơi nào đó chính int. Tùy thuộc vào nơi bạn sử dụng thuật toán này, nó sẽ xác định những gì được trả về bởi nó. Nhưng đối với trường hợp của chúng tôi, chúng tôi nghiêm chỉnh nhìn vào cách thực hiện điều này thực sự lặp thông qua một mảng. Vì vậy, chúng tôi không lo lắng về nó. 

Vì vậy, chúng ta đang nói về trường hợp tốt nhất và tình huống xấu nhất cho tìm kiếm nhị phân. Vì vậy, nó cũng quan trọng để làm rằng đối với mỗi loại của chúng tôi. Vì vậy, những gì bạn nghĩ là tồi tệ nhất trường hợp thời gian chạy của bong bóng sắp xếp? Các bạn nhớ không? 

HỌC SINH: N trừ 1. GIẢNG: N trừ 1. Vì vậy, đó có nghĩa là có n trừ đi 1 so sánh. Vì vậy, một điều nhận ra là mà trên phiên đầu tiên, chúng tôi đi qua, chúng ta so sánh các two-- vì vậy đó là 1. Hai, ba, bốn. Vì vậy, sau một lần lặp chúng tôi đã có bốn so sánh. Khi tôi đang nói về thời gian chạy và n. N đại diện cho số lượng so sánh như một chức năng của bao nhiêu yếu tố chúng tôi có. OK? 

Vì vậy, chúng tôi đi qua, chúng tôi có bốn. Thời gian tiếp theo bạn biết chúng tôi không phải chăm sóc này. Chúng tôi so sánh hai, hai, hai, và nếu chúng ta không có tối ưu hóa với các vòng lặp bốn mà tôi đã viết, bạn sẽ được so sánh ở đây anyways. Vì vậy, bạn sẽ phải chạy qua mảng và thực hiện so sánh n n lần, bởi vì mỗi lần chúng tôi chạy qua nó we loại một điều. 

Và mỗi khi chúng ta chạy qua mảng, chúng tôi làm n so sánh. Vì vậy, thời gian chạy của chúng tôi cho điều này là thực sự n bình phương, mà là tồi tệ hơn trong của chúng tôi cuối vì đó đăng nhập có nghĩa là nếu chúng ta có bốn tỷ yếu tố, đó là sẽ đưa chúng ta bốn tỷ bình phương thay vì 32. Vì vậy, không phải là thời gian chạy tốt nhất, nhưng đối với một số điều, bạn đã biết, nếu bạn đang trong vòng một phạm vi nhất định của các yếu tố bong bóng sắp xếp có thể là tốt để sử dụng. 

OK. Vì vậy, bây giờ là thời gian chạy trường hợp tốt nhất là gì? HỌC SINH: Zero? Hay 1? 

GIẢNG: 1 Vì vậy, sẽ là một so sánh. Phải. 

HỌC SINH: N trừ 1? 

GIẢNG: Vì vậy, yeah. Vì vậy, n trừ đi 1. Bất cứ khi nào bạn có một khái niệm như n trừ đi 1, chúng ta có xu hướng chỉ cần thả nó đi và chúng tôi chỉ nói n bởi vì bạn có để so sánh mỗi these-- mỗi cặp. Vì vậy, nó sẽ là n trừ đi 1, mà chúng tôi chúng tôi chỉ nói là khoảng n. Khi bạn đang làm việc với thời gian chạy, tất cả mọi thứ là trong xấp xỉ. Miễn là các số mũ là chính xác, bạn đang khá tốt. 

Đó là cách chúng ta đối phó với nó. Vì vậy, trường hợp tốt nhất là n, mà có nghĩa là danh sách đã được sắp xếp, và tất cả chúng tôi làm là chạy qua và kiểm tra xem nó được sắp xếp. Cool. Được rồi. Vì vậy, như bạn thấy ở đây, chúng tôi chỉ có một số đồ thị hơn. Vì vậy, n bình phương. Fun. Nhiều tồi tệ hơn n như chúng ta thấy, và nhiều, tồi tệ hơn nhiều so với đăng nhập 2n. Và sau đó bạn cũng nhận được vào các bản ghi log. Và bạn có 124, bạn nhận được vào như sao nhật ký, mà là giống như điên. Vì vậy, nếu bạn quan tâm, tra cứu sao log. Đó là loại vui vẻ. Vì vậy, chúng ta có biểu đồ này rất lớn. Chỉ cần một người đứng đầu lên, một này biểu đồ tuyệt vời để có cho trung hạn của bạn bởi vì chúng tôi thời gian để yêu cầu bạn những mỏng. Vì vậy, chỉ là một người đứng đầu lên, có này của bạn giữa kỳ về đẹp cheat sheet của bạn có. Vì vậy, chúng ta chỉ cần nhìn vào bong bóng sắp xếp. Trường hợp xấu nhất, n bình phương, trường hợp tốt nhất, n. Và chúng ta sẽ nhìn vào những người khác. 

Và như bạn có thể thấy, chỉ một thực sự làm tốt là sắp xếp hợp nhất, mà chúng tôi sẽ nhận được vào lý do tại sao. Vì vậy, chúng ta sẽ đi đến tiếp theo một lựa chọn loại here--. Có ai nhớ làm thế nào lựa chọn loại làm việc? Đi cho nó. 

HỌC SINH: Về cơ bản đi qua một trật tự và tạo ra một danh sách mới. Và cũng giống như bạn đang đặt yếu tố trong, đặt chúng vào đúng vị trí trong danh sách mới. 

GIẢNG: Vì vậy, âm thanh giống như sắp xếp chèn. Nhưng bạn thực sự gần gũi. Họ rất giống nhau. Ngay cả khi tôi nhận được chúng lẫn lộn đôi khi. Trước khi phần này, tôi được như thế, chờ đợi. OK. Vì vậy, những gì bạn muốn làm là lựa chọn sắp xếp, cách bạn có thể nghĩ về nó và cách Tôi chắc chắn rằng tôi không cố gắng để có được họ hỗn hợp lên, là nó đi qua và nó chọn số nhỏ nhất và nó đặt rằng vào đầu danh sách của bạn. Nó hoán đổi nó với vị trí đầu tiên. Họ thực sự có một ví dụ cho tôi. Tuyệt vời. Vì vậy, chỉ là một cách để suy nghĩ lựa chọn it-- sắp xếp, chọn giá trị nhỏ nhất. Và chúng ta sẽ chạy qua một ví dụ mà tôi nghĩ rằng sẽ giúp đỡ vì Tôi nghĩ rằng hình ảnh luôn luôn giúp đỡ. Vì vậy, chúng ta bắt đầu với một cái gì đó đó là hoàn toàn không được phân loại. Red sẽ không được phân loại, màu xanh lá cây sẽ được sắp xếp. Tất cả sẽ làm cho tinh thần trong một giây. 

Vì vậy, chúng tôi đi qua và chúng ta lặp từ đầu đến cuối. Và chúng ta nói, OK, 2 là số lượng nhỏ nhất của chúng tôi. Vì vậy, chúng ta sẽ mất 2 và chúng ta sẽ để di chuyển nó vào phía trước của mảng của chúng tôi bởi vì đó là số nhỏ nhất chúng ta có. Vì vậy, đó là những gì đang thực hiện ở đây. Nó chỉ đi để trao đổi hai. Vì vậy, bây giờ chúng tôi đã sắp xếp một một phần và một phần được phân loại. Và những gì tốt để nhớ về việc lựa chọn loại là chúng tôi chỉ lựa chọn từ phần phân loại. 

Các phần được sắp xếp bạn chỉ để lại một mình. Mm-hm? 

HỌC SINH: Làm thế nào để biết nó là gì nhỏ nhất mà không so sánh nó để các giá trị khác trong mảng. GIẢNG: Nó không so sánh nó. Chúng tôi thích bỏ qua nó. Đây chỉ là nói chung chung. Yeah. Khi chúng tôi viết mã tôi chắc chắn bạn sẽ hài lòng hơn. Nhưng bạn lưu trữ này đầu tiên yếu tố như là nhỏ nhất. Bạn so sánh và bạn nói, OK, là nó nhỏ hơn? Vâng. Giữ nó. Đây là nó nhỏ hơn? Không có? 

Đây là nhỏ nhất của bạn, phân công lại nó để giá trị của bạn. Và bạn sẽ có nhiều hạnh phúc hơn khi chúng tôi đi qua các mã. Vì vậy, chúng tôi đi qua, chúng tôi trao đổi nó, vì vậy sau đó chúng ta nhìn vào phần không được phân loại này. Vì vậy, chúng ta sẽ chọn ra ba. Chúng ta sẽ đặt nó trên tại cuối phần được sắp xếp của chúng tôi. Và chúng tôi chỉ cần đi để tiếp tục làm rằng, làm điều đó, và làm điều đó. Vì vậy, đây là loại của chúng tôi giả ở đây. Chúng tôi sẽ mã nó lên ở đây trong một giây. Nhưng chỉ cần một cái gì đó để đi bộ thông qua trên một mức độ cao. Bạn sẽ đi từ i bằng từ 0 đến n trừ đi 2. Đó là tối ưu hóa khác. Đừng lo lắng quá nhiều về nó. Vì vậy, như bạn đã nói. Như Jacob đã nói, làm thế nào chúng ta theo dõi những gì tối thiểu của chúng tôi là gì? Làm thế nào để chúng ta biết? Chúng ta phải so sánh tất cả mọi thứ trong danh sách của chúng tôi. 

Vì vậy, tối thiểu bằng i. Nó chỉ nói rằng trong trường hợp này chỉ số của giá trị tối thiểu của chúng tôi. Vì vậy, sau đó nó sẽ lặp qua và nó đi từ j bằng i cộng thêm 1. Vì vậy, chúng tôi đã biết rằng đó là yếu tố đầu tiên của chúng tôi. Chúng tôi không cần phải so sánh nó với chính nó. Vì vậy, chúng tôi bắt đầu so sánh nó với các tiếp theo một trong đó là lý do tại sao nó là i + 1 đến n trừ đi 1, đó là cuối mảng đó. Và chúng tôi đã nói nếu mảng ở j là ít hơn mảng min, sau đó chúng tôi phân công lại nơi chỉ số tối thiểu của chúng tôi là. 

Và nếu min là không bằng tôi, như ở nơi mà chúng tôi đã trở lại ở đây. Vì vậy, giống như khi chúng tôi lần đầu tiên đã làm một này. Trong trường hợp này, nó sẽ bắt đầu bằng không, nó sẽ kết thúc được hai. Vì vậy, min sẽ không bằng i cuối cùng. Điều đó cho phép chúng ta biết rằng chúng ta cần phải trao đổi chúng. Tôi cảm thấy như một ví dụ cụ thể sẽ giúp nhiều hơn này. Vì vậy, tôi sẽ mã này với các bạn ngay bây giờ và tôi nghĩ rằng nó sẽ được tốt hơn. 

Loại có xu hướng làm việc theo cách đó trong đó nó thường tốt hơn chỉ để nhìn thấy chúng. Vì vậy, những gì chúng tôi muốn làm là trước tiên chúng ta muốn nhỏ nhất phần tử trong vị trí của nó trong mảng. Chính xác những gì Jacob đã nói. Bạn cần lưu trữ bằng cách nào đó. Vì vậy, chúng ta sẽ bắt đầu ở đây iterating trên mảng. Chúng tôi sẽ nói đó là của chúng tôi Người đầu tiên chỉ để bắt đầu. Vì vậy, chúng ta sẽ có int nhỏ nhất là bằng với mảng ở i. 

Vì vậy, một điều cần lưu ý, mỗi thời gian vòng lặp này thực hiện, chúng tôi đang bắt đầu một bước xa hơn. Khi chúng tôi bắt đầu chúng ta nhìn vào một này. Lần sau chúng ta lặp qua, chúng tôi đang bắt đầu tại một này và gán cho nó giá trị nhỏ nhất của chúng tôi. Vì vậy, nó rất giống với bong bóng sắp xếp nơi chúng ta biết rằng một đường chuyền sau, Yếu tố cuối cùng này được sắp xếp. Với lựa chọn sắp xếp, nó chỉ là ngược lại. 

Tại mỗi vượt qua, chúng ta biết rằng người đầu tiên được sắp xếp. Sau khi vượt qua thứ hai, thứ hai sẽ được sắp xếp. Và như bạn đã thấy với các ví dụ slide, phần sắp xếp của chúng tôi chỉ tiếp tục tăng. Vì vậy, bằng cách thiết lập một nhỏ nhất của chúng tôi để mảng i, tất cả nó làm được thắt những gì chúng tôi đang tìm kiếm như vậy là để giảm thiểu số so sánh chúng tôi thực hiện. Điều đó có ý nghĩa với tất cả mọi người? Bạn có cần tôi để chạy thông qua đó một lần nữa chậm hơn hay nói cách khác nhau? Tôi rất vui. OK. 

Vì vậy, chúng ta giữ giá trị tại thời điểm này, nhưng chúng tôi cũng muốn để lưu trữ các chỉ số. Vì vậy, chúng ta sẽ lưu trữ vị trí nhỏ nhất một, mà chỉ là có được tôi. Vì vậy bây giờ Jacob là hài lòng. Chúng tôi có những thứ được lưu trữ. Và bây giờ chúng ta cần phải xem xét thông qua phần không được phân loại của mảng. Vì vậy, trong trường hợp này này sẽ không được phân loại của chúng tôi. Đây là i. OK. 

Vì vậy, những gì chúng tôi đang đi làm là có được một vòng lặp. Bất cứ khi nào bạn cần lặp thông qua một mảng, tâm trí của bạn có thể đi đến một vòng lặp. Vì vậy, đối với một số int k equals-- những gì chúng ta nghĩ k sẽ bằng để bắt đầu với? Đây là những gì chúng tôi thiết lập như là nhỏ nhất của chúng tôi giá trị và chúng tôi muốn so sánh nó. Những gì chúng tôi muốn so sánh nó với? Nó sẽ là một trong những tiếp theo này, phải không? Vì vậy, chúng tôi muốn k phải được khởi tạo để tôi cộng thêm 1 để bắt đầu. 

Và chúng tôi muốn k trong trường hợp này chúng tôi đã có kích thước lưu trữ ở đây, vì vậy chúng tôi chỉ có thể sử dụng kích thước. Kích thước là kích thước của mảng. Và chúng tôi chỉ muốn k cập nhật bởi một mỗi lần. Cool. Vì vậy, bây giờ chúng tôi cần phải tìm phần tử nhỏ nhất ở đây. Vì vậy, nếu chúng ta lặp qua, chúng tôi muốn nói, nếu mảng tại k là ít hơn value-- nhỏ nhất của chúng tôi đây là nơi mà chúng tôi thực sự theo dõi những gì là các here-- nhỏ nhất sau đó chúng tôi muốn gán những gì giá trị nhỏ nhất của chúng tôi là. 

Điều này có nghĩa rằng, oh, chúng tôi lặp lại thông qua đây. Dù giá trị ở đây là không phải là điều nhỏ nhất của chúng tôi. Chúng tôi không muốn nó. Chúng tôi muốn gán nó. Vì vậy, nếu chúng ta giao lại nó, những gì làm bạn nghĩ rằng có thể là trong mã này ở đây? Chúng tôi muốn gán nhỏ nhất và vị trí. Vì vậy, những gì bây giờ là nhỏ nhất? HỌC SINH: Array k. GIẢNG: Array k. Và bây giờ là những gì vị trí? Các chỉ số của là gì giá trị nhỏ nhất của chúng tôi? Nó chỉ k. Vì vậy, mảng k, k, họ phù hợp lên. Vì vậy, chúng tôi muốn phân công lại đó. Và sau đó sau khi chúng tôi tìm thấy nhỏ nhất của chúng tôi, do đó vào cuối những điều này cho vòng lặp ở đây chúng tôi đã tìm thấy những gì nhỏ nhất của chúng tôi giá trị, vì vậy chúng tôi chỉ trao đổi nó. Trong trường hợp này, như nói của chúng tôi giá trị nhỏ nhất là ra ở đây. Đây là giá trị nhỏ nhất của chúng tôi. 

Chúng tôi chỉ muốn trao đổi nó ở đây, đó là những gì mà chức năng trao đổi ở phía dưới đã làm, mà chúng tôi chỉ viết lên cùng một vài phút trước đây. Vì vậy, nó nên trông quen thuộc. Và sau đó nó sẽ chỉ lặp đi lặp lại thông qua cho đến khi nó đạt đến tất cả các cách đến cuối, có nghĩa là bạn có không yếu tố đó là không được phân loại và mọi thứ khác đã được sắp xếp. Có ý nghĩa? Một ít cụ thể hơn? Mã giúp đỡ? 

HỌC SINH: Đối với một kích thước, bạn không bao giờ thực sự định nghĩa nó hoặc thay đổi nó, như thế nào biết? 

GIẢNG: Vì vậy, có một điều để nhận thấy ở đây là int size. Vì vậy, chúng ta đang nói ở loại sort-- này là một chức năng trong này case-- nó lựa chọn loại, nó được thông qua với các chức năng. Vì vậy, nếu nó không được thông qua trong, bạn sẽ làm điều gì đó như với chiều dài của mảng hoặc bạn sẽ lặp qua để tìm độ dài. Nhưng vì nó được thông qua tại, chúng tôi chỉ có thể sử dụng nó. Bạn chỉ cần giả định rằng người sử dụng cho bạn một kích thước hợp lệ thực sự đại diện một kích thước của mảng của bạn. Mát mẻ? 

Nếu bạn có bất kỳ rắc rối với những hoặc muốn biết thêm thực hành mã hóa các loại trên của riêng bạn, bạn nên đi đến study.cs50. Đó là một công cụ. Họ có một kiểm tra mà bạn thực sự có thể viết. Họ làm giả. Họ có nhiều video và slide bao gồm cả những cái tôi sử dụng ở đây. Vì vậy, nếu bạn vẫn còn cảm thấy một chút mờ, cố gắng mà ra. Như mọi khi, đến nói chuyện với tôi, quá. Câu hỏi? 

HỌC SINH: Bạn có nói rằng các kích thước trước đây được định nghĩa? GIẢNG: Có. Kích thước trước đây được xác định lên ở đây trong phần khai báo hàm. Vì vậy, bạn cho rằng nó được thông qua trong bởi người sử dụng, và để đơn giản, chúng ta sẽ giả định rằng người sử dụng đã cho chúng tôi kích thước chính xác. Cool. Vì vậy, đó là lựa chọn loại. Guys, Tôi biết chúng tôi học được rất nhiều ngày hôm nay. Đó là một dữ liệu dày đặc cho phần. Vì vậy, với điều đó, chúng ta sẽ để đi đến sắp xếp chèn. 

OK. Vì vậy, trước đó chúng ta phải làm phân tích thời gian chạy của chúng tôi ở đây. Vì vậy, trong trường hợp tốt nhất, cấp kể từ khi tôi chỉ cho bạn bảng tôi đã loại đã cho nó đi. Nhưng thời gian chạy trường hợp tốt nhất, những gì chúng ta nghĩ? Tất cả mọi thứ được sắp xếp. N phương. Bất cứ ai có một lời giải thích cho lý do tại sao bạn nghĩ sao? 

HỌC SINH: Bạn đang so sánh through-- GIẢNG: Đúng vậy. Bạn đang so sánh thông qua. Tại mỗi lần lặp, mặc dù chúng tôi đang decrementing này bằng một, bạn vẫn tìm kiếm thông qua tất cả mọi thứ để tìm một nhỏ nhất. Vì vậy, ngay cả khi giá trị nhỏ nhất của bạn là ở đây ngay từ đầu, bạn vẫn so sánh nó chống lại tất cả mọi thứ khác để chắc chắn rằng đó là điều nhỏ nhất. Vì vậy, bạn sẽ kết thúc chạy qua khoảng n bình phương lần. Được rồi. Và trường hợp xấu nhất là gì? Ngoài ra n bình vì bạn đang đi để được làm điều đó cùng một thủ tục. Vì vậy, trong trường hợp này, lựa chọn loại có một cái gì đó rằng chúng ta cũng gọi thời gian chạy dự kiến. Vì vậy, trong những người khác, chúng ta chỉ cần biết các giới hạn trên và dưới. Tùy thuộc vào cách điên của chúng tôi danh sách là như thế nào hoặc không được phân loại nó là, chúng khác nhau giữa n hoặc n bình phương. Chúng tôi không biết. 

Nhưng vì lựa chọn loại có cùng tồi tệ nhất và trường hợp tốt nhất, cho chúng ta biết rằng không có vấn đề gì loại của đầu vào chúng tôi có, cho dù đó là hoàn toàn sắp xếp hoặc hoàn toàn sắp xếp đảo ngược, đó là sẽ mất cùng một lượng thời gian. Vì vậy, trong trường hợp đó, nếu bạn nhớ từ bảng của chúng tôi, nó thực sự đã có một giá trị hai loại này không có, đó là thời gian chạy dự kiến. Vì vậy, chúng ta biết rằng bất cứ khi nào chúng tôi chạy lựa chọn sắp xếp, nó đảm bảo chạy một thời gian n bình phương. Không có sự thay đổi đó. Nó chỉ là dự kiến. Và, một lần nữa, nếu bạn muốn tìm hiểu hơn, có CS 124 vào mùa xuân. Được rồi. Chúng tôi đã nhìn thấy một này. Cool. Vì vậy, loại chèn. Và tôi có lẽ sẽ để ngọn lửa thông qua này. Tôi sẽ không có các bạn mã nó. Chúng tôi sẽ chỉ cần đi bộ qua nó. Vì vậy, sắp xếp chèn là loại tương tự để lựa chọn loại trong đó chúng ta có cả một không được phân loại và sắp xếp một phần của mảng. 

Nhưng điều khác biệt là như chúng tôi đi qua từng người một, chúng ta chỉ cần lấy bất cứ số là tiếp theo của chúng tôi không được phân loại, và sắp xếp nó một cách chính xác vào mảng được sắp xếp của chúng tôi. Nó sẽ có ý nghĩa hơn với một ví dụ. Vì vậy, tất cả mọi thứ bắt đầu như không được phân loại, giống như với các lựa chọn sắp xếp. Và chúng ta sẽ sắp xếp này trong thứ tự tăng dần như chúng tôi có được. Vì vậy, trên đèo đầu tiên của chúng tôi chúng ta lấy giá trị đầu tiên và chúng ta nói, OK, bạn có bây giờ trong một danh sách của mình. 

Bởi vì bạn đang ở trong một danh sách của chính mình, bạn đều được sắp xếp. Xin chúc mừng cho là Yếu tố đầu tiên trong mảng này. Bạn đã sắp xếp tất cả các ngày của riêng bạn. Vì vậy, bây giờ chúng tôi đã sắp xếp một và một mảng được phân loại. Vì vậy, bây giờ chúng ta đi đầu tiên. Điều gì xảy ra giữa đây và ở đây là chúng ta nói, OK, chúng ta sẽ nhìn vào giá trị đầu tiên của mảng không được phân loại của chúng tôi và chúng ta sẽ phải nhập vào nó trong của nó địa điểm chính xác trong mảng được sắp xếp. 

Vì vậy, những gì chúng tôi làm là chúng ta mất 5 và chúng ta nói, OK, 5 lớn hơn 3, vì vậy chúng tôi chỉ cần chèn nó bên phải bên phải đó. Chúng tôi đang tốt. Vì vậy, sau đó chúng tôi tiếp tục tiếp theo của chúng tôi. Và chúng tôi mất 2. Chúng ta nói, OK, 2 là ít hơn 3, vì vậy chúng tôi biết rằng nó cần phải được ở trước danh sách của chúng tôi bây giờ. Vì vậy, những gì chúng ta làm chúng ta đẩy 3 và 5 xuống là và chúng tôi di chuyển vào 2 khe đầu tiên. Vì vậy, chúng tôi chỉ chèn nó vào địa điểm chính xác nó nên được. 

Sau đó, chúng ta nhìn vào chúng tôi kế tiếp, chúng ta nói 6. OK, 6 lớn hơn tất cả mọi thứ trong mảng được sắp xếp của chúng tôi, vì vậy chúng tôi chỉ cần gắn thẻ trên để kết thúc. Và sau đó chúng ta nhìn vào 4. 4 là ít hơn 6, nó ít hơn hơn 5 nhưng nó lớn hơn 3. Vì vậy, chúng tôi chỉ cần chèn nó vào giữa giữa 3 và 5. Vì vậy, để làm cho rằng một chút bit cụ thể hơn, đây là loại của ý tưởng về những gì đã xảy ra. Vì vậy, cho mỗi phần tử không được phân loại, chúng tôi xác định nơi ở phần sắp xếp nó được. 

Vì vậy, giữ trong tâm trí sắp xếp và không được phân loại, chúng ta phải đi qua thông qua và con số nơi nó phù hợp trong mảng được sắp xếp. Và chúng ta chèn nó bằng cách thay đổi các yếu tố bên phải của nó xuống. Và sau đó chúng tôi chỉ cần giữ lặp lại thông qua cho đến khi chúng tôi có một danh sách được sắp xếp hoàn toàn nơi không được phân loại tại là zero và được sắp xếp chiếm các toàn bộ danh sách của chúng tôi. Vì vậy, một lần nữa, để thực hiện những điều cụ thể hơn, chúng ta có giả. 

Vì vậy, về cơ bản tôi cho là bằng 0 đến n trừ đi 1, đó chỉ là chiều dài của mảng của chúng tôi. Chúng tôi có một số yếu tố đó là bằng mảng đầu tiên hoặc các chỉ số đầu tiên. Chúng tôi thiết lập j bằng đó. Vì vậy, trong khi j lớn hơn không và mảng, j trừ 1 lớn hơn yếu tố, vì vậy tất cả đó là làm là đảm bảo rằng j của bạn thực sự đại diện cho phần không được phân loại của mảng. 

Vì vậy, trong khi vẫn còn là điều để sắp xếp và j trừ một is-- gì là yếu tố cô ấy? J không bao giờ được định nghĩa ở đây. Đó là loại gây phiền nhiễu. OK. Anyways. Vì vậy, j trừ đi 1, bạn đang kiểm tra các yếu tố trước khi nó. Bạn đang nói, OK, là phần tử trước khi bất cứ nơi nào tôi am-- hãy thực sự rút ra được điều này. Vì vậy, hãy nói điều này là như trên đèo thứ hai của chúng tôi. Vì vậy, tôi sẽ là bằng 1, mà là ở đây. 

Vì vậy, tôi sẽ là bằng 1. Đây sẽ là 2, 4, 5, 6, 7. Được rồi. Vì vậy, yếu tố của chúng tôi trong trường hợp này là có được bằng 4. Và chúng tôi có một số j đó sẽ bằng 1. Oh, j là decrementing. Đó là những gì nó được. Vì vậy, j bằng i, vì vậy đây là những gì nói là khi chúng tôi di chuyển về phía trước, chúng tôi chỉ đảm bảo rằng chúng ta không hơn lập chỉ mục theo cách này khi chúng ta đang cố gắng để chèn mọi thứ vào danh sách được sắp xếp của chúng tôi. 

Vì vậy, khi j bằng 1 trong trường hợp này và mảng j trừ one-- nên mảng j trừ 1 là 2 trong case-- này nếu đó là lớn hơn các yếu tố, sau đó tất cả điều này đang làm đang chuyển điều xuống. Vì vậy, trong trường hợp này, mảng j trừ một sẽ là mảng không, đó là 2. 2 là không lớn hơn 4, vì vậy điều này không thực hiện. Vì vậy, sự thay đổi không di chuyển xuống. Điều này không có ở đây chỉ là di chuyển mảng được sắp xếp của bạn xuống. Trong trường hợp này, trên thực tế, chúng tôi có thể do-- chúng ta hãy thực hiện 3 này. Vì vậy, nếu chúng tôi đi bộ qua với ví dụ này, chúng ta đang ở đây. Điều này được sắp xếp. Đây là phân loại. Mát mẻ? Vì vậy, tôi là bằng 2, do đó yếu tố của chúng tôi là bằng 3. Và j của chúng tôi là bằng 2. Vì vậy, chúng tôi xem xét thông qua và chúng tôi nói, OK, là mảng j trừ một lớn hơn các phần tử mà chúng ta đang tìm kiếm? Và câu trả lời là có, đúng không? 4 lớn hơn 3 và j là 2, do đó, mã này được thực thi. 

Vì vậy, bây giờ những gì chúng tôi làm một mảng ở 2, do đó ngay tại đây, chúng tôi trao đổi chúng. Vì vậy, chúng tôi chỉ nói, OK, mảng 2 giờ là có được 3. Và j sẽ bằng j trừ đi 1, đó là 1. Đó là khủng khiếp, nhưng các bạn có được ý tưởng. J tại là bằng 1. Và mảng j chỉ là có được bằng yếu tố của chúng tôi, đó là 4. Tôi xóa một cái gì đó tôi không nên có hoặc một cái gì đó miswrote, nhưng các bạn có được ý tưởng. 

Nó di chuyển với n. Và sau đó nếu điều này là, nó sẽ lặp một lần nữa và nó sẽ nói, OK, j là 1 bây giờ. Và mảng j trừ 1 bây giờ là 2. Là 2 ít hơn yếu tố của chúng tôi? Không có? Điều đó có nghĩa rằng chúng tôi đã đưa yếu tố này ở vị trí chính xác trong mảng được sắp xếp của chúng tôi. Sau đó, chúng ta có thể thực hiện việc này và chúng tôi nói, OK, mảng được sắp xếp của chúng tôi là ở đây. Và nó sẽ đưa con số này 6 và được như, OK, 6 ít hơn con số này? Không có? Cool. Chúng tôi đang sử dụng tốt. 

Làm điều đó một lần nữa. Chúng ta nói 7. 7 ít hơn cuối cùng của mảng được sắp xếp của chúng tôi? Không. Vì vậy, chúng tôi đang sử dụng tốt. Vì vậy, điều này sẽ được sắp xếp. Về cơ bản tất cả điều này là nó nói cất các yếu tố đầu tiên của mảng không được phân loại của bạn, tìm ra nơi nó đi trong mảng được sắp xếp của bạn. Và điều này chỉ chăm sóc giao dịch hoán đổi để làm điều đó. Bạn về cơ bản chỉ trao đổi cho đến khi nó ở đúng chỗ. Các hình ảnh thị giác là bạn đang di chuyển tất cả mọi thứ xuống bằng cách làm đó. 

Vì vậy, nó giống như một nửa bong bóng sắp xếp-esque. Kiểm tra 50 nghiên cứu. Tôi khuyên bạn nên cố gắng mã này trên của riêng bạn. Nếu bạn có bất kỳ vấn đề hoặc bạn muốn xem mẫu mã cho một loại chèn, xin vui lòng cho tôi biết. Tôi luôn luôn xung quanh. Vì vậy, thời gian chạy trường hợp xấu nhất và thời gian chạy trường hợp tốt nhất. Như bạn thấy anh chàng từ bảng tôi đã cho thấy bạn, nó cả n bình phương và n. 

Vì vậy, loại đi tắt của những gì chúng tôi nói chuyện về với các loại trước đây của chúng tôi, tồi tệ nhất trường hợp thời gian chạy là nếu nó hoàn toàn không được phân loại, chúng ta phải so sánh tất cả các lần n. Chúng tôi làm một toàn bộ rất nhiều so sánh bởi vì nếu nó theo thứ tự ngược, chúng ta sẽ nói, OK, điều này là như nhau, điều này là tốt, và điều này sẽ phải được so sánh chống lại một trong những người đầu tiên được chuyển trở lại. Và khi chúng ta có được về phía đuôi kết thúc, chúng tôi có để so sánh, so sánh, và so sánh với tất cả mọi thứ. 

Vì vậy, nó kết thúc lên được khoảng n bình phương. Nếu chính xác thì bạn nói, OK, 2, bạn tốt. 3, bạn đang so với 2. Bạn tốt. 4, bạn chỉ cần so sánh với đuôi. Bạn tốt. 6, so với đuôi, bạn đang sử dụng tốt. Vì vậy, cho tất cả các điểm nếu nó đã sắp xếp, bạn đang làm một so sánh. Vì vậy, nó chỉ là n. Và bởi vì chúng tôi có một thời gian chạy trường hợp tốt nhất của n và một thời gian chạy trường hợp xấu nhất của n bình phương, chúng tôi không có thời gian chạy dự kiến. 

Nó chỉ phụ thuộc vào hỗn loạn của danh sách của chúng tôi ở đó. Và một lần nữa, một đồ thị và bảng khác. Vì vậy, sự khác biệt giữa các loại. Tôi chỉ cần đi để lướt qua, tôi cảm thấy như chúng tôi đã nói chuyện rộng rãi về cách họ tất cả các loại của khác nhau và liên kết với nhau. Vì vậy, merge sort là người cuối cùng Tôi sẽ mang các bạn với. Chúng tôi có một bức tranh khá đầy màu sắc. Vì vậy, hợp nhất phân loại là một thuật toán đệ quy. Vì vậy, các bạn biết những gì một hàm đệ quy là gì? 

Bất cứ ai muốn nói không? Bạn có muốn thử không? Vì vậy, một hàm đệ quy chỉ là một chức năng mà tự gọi mình. Vì vậy, nếu các bạn đã quen thuộc với dãy Fibonacci, đó là coi là đệ quy vì bạn mất trước đó hai và thêm chúng với nhau để có được một tiếp theo của bạn. Vì vậy, đệ quy, tôi luôn luôn nghĩ của đệ quy là giống như một xoắn ốc vì vậy bạn như vun vút đổ vào nó. Nhưng nó chỉ là một chức năng mà tự gọi mình. 

Và, thực sự, thực sự nhanh chóng tôi có thể cho bạn những gì trông như thế nào. Vì vậy, đệ quy ở đây, nếu chúng ta nhìn, đây là cách đệ quy tổng hợp trên một mảng. Vì vậy, tất cả những gì chúng tôi làm là chúng tôi có chức năng tổng hợp tổng hợp mà phải mất một kích thước và một mảng. Và nếu bạn nhận thấy, kích thước xác suất của một mỗi lần. Và tất cả nó là nếu x bằng zero-- vì vậy nếu kích thước của mảng bằng zero-- nó trả về số không. 

Nếu không thì nó tóm tắt này Yếu tố cuối cùng của mảng, và sau đó có một khoản phần còn lại của mảng. Vì vậy, nó chỉ phá vỡ nó xuống vấn đề nhỏ hơn và nhỏ hơn. Long câu chuyện ngắn, đệ quy, chức năng mà tự gọi mình. Nếu đó là tất cả các bạn đã nhận ra điều này, đó là những gì một hàm đệ quy là. Nếu bạn có 51, bạn sẽ nhận được rất, rất thoải mái với đệ quy. Đó là thực sự mát mẻ. Nó có ý nghĩa như tại 03:00 một đêm ra. Và tôi đã được như thế, tại sao đã Tôi không bao giờ sử dụng này? 

Vì vậy, sắp xếp hợp nhất, về cơ bản những gì nó sẽ làm là nó sẽ phá vỡ nó xuống và phá vỡ nó xuống cho đến khi nó là yếu tố chỉ duy nhất. Các yếu tố duy nhất là dễ dàng để sắp xếp. Chúng tôi thấy điều đó. Nếu bạn có một yếu tố, đó là đã xem xét sắp xếp. Vì vậy, trên một đầu vào của n phần tử, nếu n là ít hơn 2, chỉ quay trở lại vì điều đó có nghĩa nó hoặc là 0 hoặc 1 như chúng ta đã thấy. Những người được coi là yếu tố được sắp xếp. 

Nếu không phá vỡ nó một nửa. Sắp xếp nửa đầu, sắp xếp thứ hai một nửa, và sau đó kết hợp chúng lại với nhau. Tại sao nó được gọi là sắp xếp hợp nhất. Vì vậy, chúng tôi có ở đây chúng tôi sẽ sắp xếp này. Vì vậy, chúng tôi tiếp tục có họ cho đến khi kích thước mảng là 1. Vì vậy, khi nó là 1, chúng ta chỉ trả lại bởi vì đây là một mảng được sắp xếp, và đây là một mảng được sắp xếp, và đó là một mảng được sắp xếp, chúng ta tất cả được sắp xếp. Vì vậy, sau đó những gì chúng tôi làm là chúng tôi bắt đầu kết hợp chúng lại với nhau. 

Vì vậy, cách bạn có thể suy nghĩ về việc sáp nhập là bạn chỉ cần loại bỏ nhỏ số của mỗi mảng phụ và chỉ cần thêm nó vào mảng nổi lên. Vì vậy, nếu bạn nhìn ở đây, khi chúng ta có các bộ chúng tôi có 4, 6, và 1. Khi chúng tôi muốn kết hợp này, chúng ta nhìn vào hai đầu tiên và chúng ta nói, OK, 1 là nhỏ hơn, nó đi vào phía trước. 4 và 6, không có gì để so sánh là nó, chỉ cần gắn thẻ trên để kết thúc. 

Khi chúng tôi kết hợp hai điều này, chúng ta chỉ lấy một nhỏ hơn của hai, vì vậy nó là 1. Và bây giờ chúng ta đi nhỏ hơn của hai, vì vậy 2. Nhỏ hơn của hai, 3. Nhỏ hơn của hai, 4, 5, 6. Vì vậy, bạn chỉ cần kéo ra khỏi các. Và bởi vì họ đã được sắp xếp trước, bạn chỉ có một so sánh mỗi lần có. Vì vậy, nhiều mã ở đây, chỉ là đại diện. Vì vậy, bạn bắt đầu ở giữa và bạn sắp xếp trái và bên phải và sau đó bạn chỉ cần kết hợp những người. 

Và chúng tôi không có mã cho hợp nhất ngay tại đây. Nhưng, một lần nữa, nếu bạn đi trên nghiên cứu 50, nó sẽ ở đó. Nếu không đến nói chuyện với tôi nếu bạn vẫn còn lẫn lộn. Vì vậy, điều thú vị ở đây là trường hợp tốt nhất, trường hợp xấu nhất, và thời gian chạy dự kiến là tất cả trong log n, mà là tốt hơn so với chúng tôi đã thấy cho phần còn lại của các loại của chúng tôi. Chúng tôi đã nhìn thấy n bình phương và những gì chúng tôi thực sự nhận được ở đây là n log n, đó là rất tốt. 

Hãy nhìn cách tốt hơn nhiều đó là. Như một đường cong đẹp. Vì vậy, nhiều hiệu quả hơn. Nếu bạn đã bao giờ có thể, sử dụng hợp nhất phân loại. Nó sẽ giúp bạn tiết kiệm thời gian. Sau đó, một lần nữa, như chúng tôi đã nói, nếu bạn đang xuống thấp trong khu vực này, nó không làm cho rằng nhiều sự khác biệt. Bạn nhận được lên đến hàng ngàn và hàng ngàn đầu vào, bạn chắc chắn muốn có một thuật toán hiệu quả hơn. Và, một lần nữa, bàn đáng yêu của chúng ta về tất cả các loại mà các bạn đã học được ngày hôm nay. 

Vì vậy, tôi biết nó được một ngày dày đặc. Điều này không nhất thiết sẽ để giúp bạn với pset của bạn. Nhưng tôi chỉ muốn làm cho một sự từ bỏ phần đó không chỉ là về psets. Tất cả các tài liệu này là công bằng trò chơi cho midterms của bạn. Và cũng nếu bạn tiếp tục với CS, đây là những nguyên tắc cơ bản thực sự quan trọng mà bạn sẽ cần phải biết. Vì vậy, một số ngày sẽ là một ít pset giúp đỡ thêm, nhưng một vài tuần sẽ có nội dung thực tế nhiều hơn nữa mà có thể không có vẻ siêu hữu ích cho bạn ngay bây giờ, nhưng tôi hứa nếu bạn tiếp tục trên sẽ rất, rất hữu ích. 

Vì vậy, đó là nó cho phần. Xuống dây. Tôi đã làm nó trong vòng một phút. Nhưng có bạn đi. Và tôi sẽ có bánh rán hay bánh kẹo. Có ai bị dị ứng với bất cứ điều gì, bằng cách này? Trứng và sữa. Vì vậy, bánh rán là một không? OK. Được rồi. Sô cô la không? Starburst. Starbursts là tốt. OK. Chúng ta sẽ có Starburst tuần tiếp theo sau đó. Đó là những gì tôi sẽ nhận được. Các bạn có một tuần tuyệt vời. Đọc spec của bạn. 

Hãy cho tôi biết nếu bạn có bất kỳ câu hỏi. Pset hai lớp nên được ra cho bạn thứ Năm. Nếu bạn có bất kỳ câu hỏi về cách tôi phân loại một cái gì đó hoặc lý do tại sao tôi chấm một cái gì đó là cách tôi đã, xin vui lòng gửi email cho tôi, đến nói chuyện với tôi. Tôi là một chút điên rồ này tuần, nhưng tôi hứa Tôi vẫn sẽ trả lời trong vòng 24 giờ. Vì vậy, có một tuần tuyệt vời, tất cả mọi người. Chúc may mắn trên pset của bạn.