12. Searching and Sorting

MIT 6.0001 Introduction to Computer Science and Programming in Python, Fall 2016
View the complete course: ocw.mit.edu/6-0001F16
Instructor: Prof. Eric Grimson
In this lecture, Prof. Grimson explains basic search and sort algorithms, including linear search, bisection search, bubble sort, selection sort, and merge sort.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu

[@abhishekhawaldar569]

This guy was the chancellor at MIT and yet teaches such basic concepts with sincerity and humility. Meanwhile most professors just brush over these topics assuming the students can learn it on their own. Massive respect !

[@JH-ux1re]

Exactly! The less knowledgeable the more arrogant

[@programmer1010]

42:12 merge isn’t logn iterations its at least n iterations and at most 2n iterations. You can see at 39:49 that number of prints(iterations) isn’t logn. 37:32 we aren’t cutting down the problem in half, it’s a tree 40:33. It’s logn levels of iterations(not iterations themselves) where iterations at each level together have O(n) complexity(cost of each step(iteration) is O(n) but turns out that cost of steps at same level of a tree is also O(n) 41:24. He just mixes levels with steps 42:04 Normally what we do is we multiply number of steps(O(n->2n)) to their complexity(O(n)) but in this case we use the fact that at each LEVEL of a tree sum of conplexity of steps is O(n). So number of LEVELS in a tree (O(logn)) multipled with each level’s complexity(O(n)) = O(nlogn)

[@McAwesomeReaper]

@@JH-ux1re Perfectly explains his sentiments around the political divide.

[@ildoguilhermeschneider4296]

​@@JH-ux1re😢😊😊

[@VixyMan96]

I've watched all the 12 lectures during corona time, I think professor Eric deserved a better audience, his jokes are really good and keep your attention through the course. Thanks MIT !!

[@saurabhmiyani9014]

same here

[@shamrockspb]

same game (c) Prof. Grimson

[@kannammapoona8064]

Can u share the playlist link

[@bee_irl]

@@kannammapoona8064 I'm late but it's /playlist?list=PLUl4u3cNGP63WbdFxL8giv4yhgdMGaZNA

[@utkarshaganla5724]

I do agree

[@CamiloDS]

For someone watching this. Make sure you do the problem sets. These classes mean nothing without them. It has been a great experience watching all the videos

[@leixun]

*My takeaways:* 1. Search algorithm 2:49 2. Sorting a list is also linear complexity 8:09, but when we search for something, we often search many times, therefore the cost of sorting could be balanced 9:37 3. Bogo sort (unbounded complexity) 11:00 4. Bubble sort (quadratic complexity) 12:48 5. Selection sort (quadratic complexity) 18:20 6. Merge sort (log-linear complexity) 26:20, and why it is efficient 32:55, it is the best we can have (considering worst cases not average cases)

[@Amy_Yu2023]

Lei Xun thanks

[@fc.soccercard]

Thanks for the handy time stamps.

[@marco.nascimento]

It has been an amazing learning experience to watch those 12 MIT lectures, I am really thankful to the institution for making all this avaiable to everyone, It's been really helpful. Incredible teachers and great lectures, already looking forward for the next course I will certainly "attend" hehe cheers from a brazillian comp science undergrad

[@tomifg]

I'm so grateful for MIT and everyone who helps support OCW. This course was an incredible experience and i can't believe I just did it from Argentina, during an economic crisis. Thank you!!!

[@TheDinosaurHead]

Thank you MIT, I really enjoyed this class.

[@RussTeeTrombone]

I’m in awe such incredible lectures are available free of charge on the internet. This far exceeded the quality of any CS course I’ve taken to date.

[@dominikklon1985]

One of my biggest dream was studying at MIT, I was pretty optimistic about that till I was like 16yo when I realise it is impossible, bcs I live in central Europe and I also needed to pass some difficult times so I didn't tryhard learning as much as I wanted to. These courses are making my dream partly realised. I'm so grateful for that, thank you

[@hoangnamdn682]

garbge

[@dayzed_gecko]

You did in one lecture, what my shitty lecturer tried to do in a week. Very good, simple and accurate.

[@tuanh9661]

by far the most amazing course I've taken, really thankful to you guys for taking the time and providing this

[@atyantsony2013]

Thank You MIT-OCW from bottom of my heart.... Thank You for your honest service. I really enjoyed this journey with both professors. THANK YOU :)

[@robpatty1811]

Thanks MIT for producing such great content and making it freely available. This is the third MIT course that I have finished.

[@titanfrost8445]

Those lectures are a a great chunk of knowledge I needed. I really liked the way everything is explaned. Thanks MIT

[@nicolasortiz2638]

It has been great to follow these lectures. Thanks MIT and ocw

[@imagenitin]

Thank you Prof Eric and MIT team for these wonderful lectures !

[@shittyworld]

THANKS MIT, ALL THE PROFESSORS AND MIT OCW TEAM FOR SHARING SUCH AMAZING KNOWLEDGE

[@RyanScarbrough]

Thank you Dr. Ana Bell and Prof. Grimson for the amazing lectures and all involved with OpenCourseWare for this course!

[@micahd7255]

These guys are great!! I'm now accepting donations to buy Ana and Prof. Grimson a second pair of clothes.

[@laksitowp]

They didn't record these in 1 day?

[@mvisperas]

It looks like they recorded these videos in one day.

[@kneerelief577]

@@mvisperas so the students are actors?

[@mvisperas]

@@kneerelief577 It means all the videos were shot in one day. Thus, their clothes appear to be the same. In game shows like Jeopardy, the host and the contestants bring different clothes so it appears the next show is actually the next day. The MIT videos are aimed at teaching, not vanity.

[@zigginzag584]

Thank you very much for this free resource. I've memorized all the algorithms presented after running into what I would consider a severe mental block in trying to conceptualize them in my mind before memorizing them. I only share in case anyone else is struggling with trying to deeply understand the content, my suggestion is to first memorize the algorithms, type them out a few hundred times, line by line, through memory, then the concepts will solidify in your mind and you can start to adapt them to other facets of programming. I think we'd all like to pretend we're super-genius's that "get it" on the first go-round, but, at least in my case, it just doesn't work that way.

[@aviraljanveja5155]

That ending was legendary :D

[@hermionegrful]

This was amazing. Thank you professor for making me understand these concepts so easily. I’ve been trying to understand these concepts for so many years and now I feel like I truly get it. A gifted teacher and thanks MIT for providing this!

[@ricj9594]

Thank you! hopefully the education in Brazil will get better because of your wonderful free courses. God Bless the whole world and you all.

[@jfbjavaforbeginners4176]

This the best ever cs course I have ever seen on youtube Thank you so much MIT you helped a lot

[@user-su8rr3cr7k]

I am addicted to Dr. Grimson’s lectures

[@ductive]

Thanks for your efforts that made such gems available

[@ashu7pathak]

Thank you MIT, even though I'm not attending your institute and not paying you any fees, I'm still able to learn from (atleast the so called/ supposedly) the best profs! ❤✌🇮🇳🇮🇳🇮🇳

[@amishakandi8450]

Thank you for these lectures! Very helpful for a highschool student interested in computer science.

[@OliviaLearns]

amazing lecture! I am so thankful this is available to us!

[@yourtechbuddy101]

For explanation + implementation + Key points List and short notes on all sorting algorithms with doubt support : kzbin.info/www/bejne/m6avXnehZ7WDndk All English Videos have been uploaded by 25th June 2020 and from now hindi series will start.

[@kirangajjala7148]

Thank you MIT u guys are doing a great job ... This video made my learning easy in lockdown 🙏🙏

[@theguildofsilence]

what an absolutely fantastic lecturer

[@rossgaller3662]

Thank you MIT and thank you Prof. Grimson!

[@shittyworld]

more like geller

[@dezkightz]

That joke at the end was gold lmao, Prof. Grimson has a wonderful sense of humor

[@danielkinyanjui5296]

The proffessor's presentation is poetry 😎

[@rdwells]

In the merge() function (35:14), if you change the first line of the for while loop to "if left[i]

[@bingchengduan7361]

a very impressive lesson.

[@ali51717]

professor Eric has been writing recursive solutions the whole course, so this time I spent 3 hours writing a recursive merge sort to find out it wasn't necessary to do it recursively,

[@tycho103]

great explanations!

[@PankajKumar-ji1ig]

Thank you professor for teachings

[@scorpio19771111]

For folks struggling with how recursion code runs, the animation at 40:05 shows step by step what happens for the recursive merge sort code. Study it together with the code, and hope you get a clearer picture of recursion.

[@njexictfan]

Thank you so much sir and ma'am!!

[@darianharrison4836]

love this lecture, very interesting!! thank you so much for the videos, now... to give all of this some good use =P

[@jadenmax679]

Very informative, thank you.

[@fernandomachado7795]

Thank you MIT

[@devesh3648]

Amazing lectures! Thanks OCW. Also, what should be the next course that I should take after this? (considering I want to get good at the use of data structures and algorithms)

[@akbarrauf2741]

thank you ,mit

[@kooser6]

Thank you MIT!

[@ibradalmar3764]

Much thanks to OCW

[@wewantjeremy]

love this dude

[@arjunsagar130]

Thank you MIT.

[@tarekghosn3648]

i love this dude man

[@OmigosTV]

thanks a lot.Very interesting and livefull lections for self education

[@danciulescurazvan1047]

How is this only 125k views and a guy talking about pokemon cards has over 3 million views? Can't really comprehend how this amazing lecture is posted for free on youtube and ppl are not watching it (or at least as much as it should be watched )

[@codesha]

Made My Life! Thanks Sensei!

[@chands.3207]

A BIG THANKS TO MIT.

[@abigiyatadesse2672]

Thank you so much.

[@MrSrijanb]

thanks mit!!!

[@YoungLink51423]

I really liked your sense of humor

[@hhg1560]

Thank you very much. From Vietnam ^^

[@jiayuyan4296]

Thank you

[@annebortoli]

Best professor ever!!!

[@programmer1010]

Selection sort is like the opposite of bubble. In bubble after every loop we find the maximum one and put it at the end, in selection sort we just find minimum after each loop. If it was c++ we could’ve written len(L)-j for range of j in 15:07

[@user-tn1yb1ne4e]

Thank you !!! it's great

[@HoudekM]

Great lectures and great lecturers. And I liked the jokes :) Thank you.

[@inflem9860]

"And we deliberately admit students of different heights so John can do this demo" lol, love these lectures!

[@user-kv8oh8lx7y]

what a closure!

[@xer_t3661]

Thank you very much! 💖🙂

[@cnasir3475]

This is awesome

[@jemsmilner4416]

wooow so fantastic!!!

[@adiflorense1477]

day during quarantine .sounds good

[@yamalokesh2657]

The classes are very good. I wish there were more classes to explain the algorithms in detail

[@MrTc1004]

there is one more MIT OCW course called introduction to algorithms

[@mitocw]

See ocw.mit.edu/courses/find-by-topic/#cat=engineering&subcat=computerscience&spec=algorithmsanddatastructures to see what we have for algorithms. Best wishes on your studies!

[@Damoon2543]

Thank you MIT wonderful lectures. @ Eric awful jocks ;)

[@sagartomar4210]

that was fantastic :)!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

[@user-kc1hq9rk1t]

I think bubble sort print statement should be right after the if statement

[@amywang8407]

selection sort around 18:00

[@dve845]

2:53 linear search (mentioned) is not the same as sequential search (what is meant here)

[@sciencethings5731]

He's actually quite funny

[@nicholasestrella339]

I feel like Prof. Grimson's true calling was to be a comedian. The dude is really funny!

[@johncampbell7868]

I wish I was in this lecture as bubble sort has been given a bad wrap, where: "for j in range(1, len(L)):" should be "for j in range(1, unsort_len(L)):" This would be a simple extension to the use of "swap" as "new_len". This saving was even observed in the lecture. Also, it would have made a very informative demonstration of quick_sort out on the steps on such a nice day. Merge sort also requires many storage allocations, which can be expensive and is another cost to consider with "compares", "swaps" and "allocates". Those steps would have been a great location for any divide and conquer sort, eg shell, merge or quick, and especially to demonstrate their difference.

[@subhasaha8988]

34:42

[@balanceyourmind5674]

This is amassing lecture . Please can you say where the first 11 lectures .

[@mitocw]

Here's the playlist for the series: kzbin.info/aero/PLUl4u3cNGP63WbdFxL8giv4yhgdMGaZNA. For more info, see the course on MIT OpenCourseWare at: ocw.mit.edu/6-0001F16. Best wishes on your studies!

[@anonymous.youtuber]

“And we deliberately admit students of different height so we can do this demo”Hilarious 😂. I really appreciate your jokes, Professor !

[@maninarush2112]

Raymond Hettinger would have a bird if he saw the abomination at 3:58

[@shittyworld]

is there any final exam for this course (6.001) ?

[@mitocw]

Looking at course on MIT OpenCourseWare ( ocw.mit.edu/6-0001F16 ), it doesn't look like it. We do know that the equivalent of 6.001 will be starting on EdX in late August (26th). It will have a final exam (which can even be graded if you sign up for a certificate): www.edx.org/course/introduction-to-computer-science-and-programming-7. There is an older version that has an exam (with solution) but it is based on an earlier version of Python and might not be as helpful: ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/unit-3/final-exam/

[@kiit-etc-etc-qi4mc]

are there lectures after this.?

[@mitocw]

No more lectures after this one. See the course on MIT OpenCourseWare for more details at ocw.mit.edu/6-0001F16.

[@konet1440]

there is a follow up course which is 6.0002

[@dongguodan2128]

Great though difficult ~~

[@dve845]

15:25 better turn the meaning of the swap flag upside down ... if you swap things set swap to True

[@tombrady7390]

i gave applause without him telling

[@labrecheabdelatif7188]

the playlist link please !!!!

[@mitocw]

kzbin.info/aero/PLUl4u3cNGP63WbdFxL8giv4yhgdMGaZNA

[@ankurg132]

For anyone watching this as a beginner and want to learn more computer science courses, here is the list of free courses through which you can learn sequentially - github.com/ossu/computer-science

[@hicham5770]

Very useful. Thanks!

[@McAwesomeReaper]

Is it required at MIT that profs wear the same outfit for every lecture, or is that just a consequence of filming for the video series?

[@samuelmurmu3163]

why was my college not showing this kind of example

[@gauravshukla5203]

Please provide algorithms course for c++

[@mohamedrafat3466]

go to website

[@BenyNotNice]

👏👏👏👏

[@seanliu3549]

I really hope he is my cs professor, such an adorable person

[@mathabahassan3471]

20:00

[@raihantanvir8880]

All classes included?

[@mitocw]

Yes. For more info and materials, see the course on MIT OpenCourseWare at: ocw.mit.edu/6-0001F16. Best wishes on your studies!

[@061_arsh]

34:30 what programming language is this ??

[@mitocw]

Python (v3.5). For more information and materials, see the course on MIT OpenCourseWare at: ocw.mit.edu/6-0001F16. Best wishes on your studies!

[@user-fl7vs4ed6l]

​​0:00:00 Review 0:02:54 0:04:00 0:06:10 0:08:26 Sorting will do you good 0:12:32 ​BOGO sort 0:13:58​ Bubble sort 0:15:58 0:18:25 selection sort 0:20:00 0:22:02 0:23:50 ​0:26:00 0:27:38​ Merge sort 0:30:00 0:32:26 0:34:28 ​0:36:26 ​0:38:12​ 0:40:02 0:42:00 ​0:44:00 ​ 0:46:10 ​What do computer scientist do 0:47:06