DOUG LLOYD: Så i CS50 vi lærte om en række sortering og søgning algoritmer. Og nogle gange kan det være lidt vanskelig at holde styr på, hvad algoritme gør hvad. Vi har virkelig kun skummet overfladen også, der er mange andre søgning og sortering algoritmer. Så i denne video lad os bare tage et par minutter at forsøge at destillere hver algoritme ned til dens centrale elementer så du kan huske den mest vigtige oplysninger om dem og være i stand til at formulere det forskelle, hvis nødvendigt. 

Den første er valget slags. Den grundlæggende idé bag valg Sorter er at finde den mindste usorterede element i et array og bytte den med første usorteret element i denne matrix. Vi sagde, at det værst tænkelige køre tidspunktet for denne var n potens. Og hvis du ønsker at huske hvorfor, tage Et kig på valg Sorter video. Den bedste fald kørselstid også n potens. 

Bubble sortere, idéen bag det den ene er at bytte tilstødende par. Så det er den nøgle, der hjælper dig huske forskellen her. Valg Sorter er, indtil videre, finde den smallest-- boble sortere sige bytte tilstødende par. Vi bytter tilstødende par elementer, hvis de er ude af drift, som effektivt bobler større elementer til højre, og på samme tid, det også begynder at flytte mindre elementer til venstre. Det værst tænkelige tilfælde kørselstid boble slags er n potens. Den bedste fald kørselstid af boble slags er n. Fordi i denne situation vi ikke actually-- vi måske ikke behøver at eventuelle swaps overhovedet. Vi har kun at gøre en passere over alle n elementer. 

I indsættelse sortere, den grundlæggende idé her er ved at flytte. Det er nøgleordet til indsætning slags. Vi kommer til at træde en gang gennem arrayet fra venstre til højre. Og som vi gør, er vi kommer til at flytte elementer Vi har allerede set at gøre plads til mindre, som trænger til at passe sted igen der sorteret del. Så vi bygger det sorterede vifte én element ad gangen, fra venstre mod højre, og vi flytter ting at gøre plads. Det værst tænkelige køre tid af indsættelse sorteringen er n potens. Den bedst tænkelige køre tid er n. 

Flet sort-- søgeordet her er splittet og flette. Vi opdeler den fulde vifte, uanset om det er seks elementer, otte elementer, 10.000 elements-- vi delt det ned til det halve, halve, halve, indtil vi har under matrix n et element arrays. Et sæt af n et element arrays. Så vi startede med én 1000-element array, og vi kommer til det punkt, hvor vi har 1.000 én-element arrays. Så begynder vi at flette disse sub arrays sammen igen i den rigtige rækkefølge. Så vi tager to en-element arrays og oprette en to-element array. Vi tager to to-element arrays og skabe en fire-elementopstillingen og så videre og så videre, indtil vi har igen ombygget en n element array. 

Det værst tænkelige køre tid af mergesort er N gange log n. Vi har n elementer, men denne rekombination proces tager log n skridt til at få tilbage til en komplet vifte. Bedste fald køretid er også n log n fordi denne proces ikke rigtig pleje om array var sorteres eller ikke til at begynde med. Fremgangsmåden er den samme, er der ingen måde at kortslutte ting. Så n log n i værste fald, n log n i bedste fald. 

Vi talte om to søge algoritmer. Så lineær søgning er om iteration. Vi går på tværs af arrayet gang, fra venstre mod højre, forsøger at finde nummeret at vi leder efter. Det værst tænkelige køre tid er stort O i n. Det kan tage os iteration på tværs af hver eneste element at finde det element, vi leder for, enten i den sidste position, eller slet ikke. Men vi kan ikke bekræfte, at indtil Vi har kigget på alt. m det bedste tilfælde, finder vi det samme. Den bedste fald køre tid af lineær søgning er omega på 1. 

Endelig var der binær søgning, som kræver diverse array. Husk det er en meget vigtig overvejelse når du arbejder med binær søgning. Det er en forudsætning for at bruge det-- array, som du søger gennem skal sorteres. Ellers nøgleordet er kløft og erobre. Split array i halve og fjerne halvdelen af ​​elementerne hver gang, som du fortsætte gennem. På grund af denne kløft og erobre og opsplitning ting i halv tilgang, det værst tænkelige kørselstid af binære søgning er log n, som i det væsentlige bedre end lineær søgning s n. Den bedst tænkelige køre tiden er stadig en. 

Vi kan finde det straks første gang vi laver en division, men, igen, så husk at selv binær søgning er væsentligt bedre end lineær søgning i kraft af at være log n versus n, du måske nødt til at gå gennem arbejdet sortering arrayet først, hvilket kan gøre det mindre effektivt afhængigt på størrelsen af ​​iteration sorteret. 

Jeg er Doug Lloyd, det er CS50.