DOUG LLOYD: Så i CS50 vi lärt oss om en variation av sortering och sökning algoritmer. Och ibland kan det vara lite knepigt att hålla koll på vad algoritmen gör vad. Vi har egentligen bara skum ytan också, det finns många andra sökning och sorteringsalgoritmer. Så i den här videon låt oss bara ta några minuter att försöka destillera varje algoritm ner till kärnelement så att du kan minnas mest viktig information om dem och kunna artikulera skillnader vid behov. 

Den första är valet slag. Den grundläggande idén bakom val Sortera är att hitta den minsta osorterade elementet i en matris och byta den med första osorterat del av denna uppsättning. Vi sade att det värsta körtid av som n kvadrat. Och om du vill återkalla varför, ta En titt på valet sorterings video. Det bästa fall körtid är också n kvadrat. 

Bubbelsortering, tanken bakom det en är att byta intilliggande par. Så det är nyckeln som hjälper dig minns skillnaden här. Val slag är, hittills, hitta smallest-- bubblan sort vill säga byta närliggande par. Vi byter närliggande par av element, om de är i ordning, som effektivt bubblor större element till höger, och på samma gång också börjar att flytta mindre element till vänster. Det värsta fall fall körtid av bubbelsortering är N i kvadrat. Det bästa fall körtid av bubbelsortering är n. För i den situationen vi inte actually-- Vi kanske inte behöver göra några swappar alls. Vi behöver bara göra en passera över alla n element. 

I insättningssortering, den Grundtanken här håller på att förskjutas. Det är nyckelordet för insättningssortering. Vi kommer att gå en gång genom arrayen från vänster till höger. Och när vi gör, vi är kommer att skifta element Vi har redan sett att göra plats för mindre som behöver passa någonstans tillbaka i den sorterade delen. Så vi bygger den sorterade arrayen en element i taget, från vänster till höger, och vi flytta saker att göra rummet. Det värsta fall gångtid insättningssortering är n kvadrat. Det bästa fall körtid är n. 

Merge sort-- sökordet Här delas och samman. Vi dela full uppsättning, om Det är sex delar, åtta delar, 10000 elements-- vi dela den ned med hälften, med hälften, med hälften, tills vi har i array n en elementuppsättningar. En uppsättning n en elementuppsättningar. Så vi började med en 1000-elementgrupp, och vi kommer till den punkt där vi har 1000 ett element matriser. Då börjar vi att slå samman dessa undergrupper tillbaka tillsammans i rätt ordning. Så vi tar två en-elementuppsättningar och skapa en två-elementgrupp. Vi tar två två-elementuppsättningar och skapa en fyra-elementgrupp och så vidare och så vidare tills vi har igen ombyggd en n elementgrupp. 

Det värsta fall gångtid merge sort är N gånger log n. Vi har n element, men denna rekombinering process tar log n steg för att få tillbaka till ett komplett utbud. I bästa fall körtid är också n log n eftersom denna process inte riktigt bryr sig om gruppen var sorterade eller inte till att börja med. Processen är densamma, det finns inget sätt att kortslutnings saker. Så n log n i värsta fall, n log n i bästa fall. 

Vi pratade om två sökalgoritmer. Så linjär sökning handlar om iteration. Vi fortsätter över arrayen en gång, från vänster till höger, försöka hitta numret att vi letar efter. Det värsta fall körtid är stort O n. Det kan ta oss iterera över varje enskilt element att hitta elementet vi söker för, antingen i den sista positionen, eller inte alls. Men vi kan inte bekräfta att tills Vi har tittat på allt. m bästa fall finner vi omedelbart. Bästa fall gångtid linjär sökning är omega 1. 

Slutligen fanns det binär sökning, vilket kräver diverse array. Kom ihåg att det är en mycket viktigt övervägande när man arbetar med binär sökning. Det är en förutsättning för att använda det-- matrisen som du söker igenom måste sorteras. Annars sökordet är söndra och härska. Split arrayen till hälften och eliminera hälften av elementen varje gång som du går igenom. På grund av denna söndra och härska och dela upp saker i halv strategi det värsta körning av binär sökning är log n, som är väsentligen bättre än linjär sökning på n. Det bästa fall körtid är fortfarande ett. 

Vi kanske tycker att det omedelbart första gången vi gör en uppdelning, men igen, kom ihåg att även om binär sökning är betydligt bättre än linjär sökning genom att vara log n kontra n du kanske måste gå igenom arbetet sorterings arrayen först, vilket kan göra det mindre effektivt beroende på storleken av den iteration sortering. 

Jag är Doug Lloyd, är detta CS50.