DOUG LLOYD: Dus in CS50 we geleerd over diverse sorteer- en zoekopties algoritmen. Soms kan het een beetje lastig te houden spoor van wat algoritme doet wat. We hebben eigenlijk alleen magere het oppervlak ook, Er zijn vele andere zoeken en sorteeralgoritmes. Dus in deze video laten we slechts een paar minuten duren om te proberen te distilleren elk algoritme tot zijn kernelementen dus je kunt de meest herinneren belangrijke informatie over hen en in staat zijn om het te verwoorden verschillen, indien nodig. 

De eerste is een soort selectie. Het basisidee achter selectie sorteren ze zijn de kleinste ongesorteerde element in een array en wisselen met de ongesorteerde eerste element van deze array. We hebben gezegd dat de worst-case looptijd van die werd n kwadraat. En als je wilt herinneren waarom nemen Een blik op de selectie soort video. De best-case runtime Ook n kwadraat. 

Bubble sort, het idee achter dat een is om aangrenzende paren wisselen. Dus dat is de sleutel die u helpt herinner me hier het verschil. Selectie soort is, tot nu toe, vindt de smallest-- bubble sort wil ruilen aangrenzende paren. We wisselen aangrenzende paren elementen indien zij zijn buiten de orde, die effectief bubbels grotere elementen naar rechts, en tegelijkertijd begint ook kleinere elementen naar links te verplaatsen. De worst-case case runtime van bubble sort is n kwadraat. De best-case runtime van bubble sort is n. Omdat in deze situatie we niet actually-- We zouden niet moeten maken elke swaps op alle. We hebben slechts een te maken passeren over alle n elementen. 

In insertion sort, de basisidee hier is aan het verschuiven. Dat is het sleutelwoord voor het inbrengen soort. We gaan een keer te doorlopen de array van links naar rechts. En als we dat doen, zijn we naar elementen verschuiven We hebben al gezien om ruimte te maken voor kleinere die moeten ergens passen terug doordat gesorteerd gedeelte. Dus we bouwen aan de gesorteerde array één element tegelijk, van links naar rechts, en we verschuiven dingen om ruimte te maken. De worst-case looptijd van insertion sort is n kwadraat. De best-case looptijd is n. 

Samenvoegen sort-- het trefwoord hier is splitsen en samenvoegen. We deelden de volledige reeks, of het zes elementen, acht elementen, 10.000 elements-- we splitsen tot de helft, de helft met de helft, totdat we onder scala n één element arrays. Een verzameling van n één element arrays. Dus begonnen we met één 1000-element array, en we krijgen tot het punt waar we heeft een 1000-element arrays. Dan beginnen we met die sub-arrays samenvoegen weer bij elkaar in de juiste volgorde. Dus nemen we twee een-element arrays en een twee-element array. We nemen twee twee-element arrays en het creëren van een vier-element serie en zo voort en zo verder tot we hebben weer herbouwd one n element array. 

De worst-case looptijd van samenvoegen soort n keer log n. We hebben n elementen, maar Dit recombineren proces neemt log n stappen om terug naar volledige array. Het beste geval run tijd is ook n log n omdat dit proces niet echt schelen of de array was gesorteerd of niet te beginnen. Het proces is hetzelfde, er geen manier om kortsluiting dingen. Zo n log n in het ergste geval, n log n in het beste geval. 

We spraken over twee zoeken algoritmen. Dus lineair zoeken is ongeveer iteratie. We verder over de array een keer, van links naar rechts, proberen om het nummer te vinden dat we zoeken. De worst-case looptijd is groot O n. Het zou ons iteratie over elk element het element we zoeken vinden voor, hetzij in de laatste positie, of helemaal niet. Maar we kunnen niet bevestigen dat tot we hebben gekeken naar alles. m het beste geval, vinden we onmiddellijk. De best-case looptijd van lineair zoeken is omega van 1. 

Ten slotte was er binary search, die vereist dat diverse array. Vergeet niet dat is een zeer belangrijke overweging bij het werken met binaire zoeken. Het is een vereiste voor het gebruik het-- de array die u op zoek bent door middel van moeten worden gesorteerd. Anders, de trefwoord is verdeel en heers. Splits de array in de helft en de helft van de elementen te elimineren elke keer als je verder door. Vanwege deze verdeel en heers en splitsen dingen in de helft aanpak, het ergste geval runtime van binaire zoeken is log n, die in hoofdzaak beter dan lineair zoeken is n. De best-case run tijd is nog steeds één. 

We zouden het onmiddellijk het vinden eerste keer maken we een divisie, maar, weer, bedenk dan dat hoewel binaire zoeken is aanzienlijk beter dan lineair zoeken vanwege zijn log n versus n, je zou kunnen hebben om te gaan door het werk sorteren eerste array, waarbij zou het minder effectief afhankelijk maken van de grootte van het itereren gesorteerd. 

Ik ben Doug Lloyd, dit is CS50.