[Speel van musiek] 

ZAMYLA CHAN: Die eerste ding wat jy dalk kennisgewing oor vonds is dat ons reeds het 'n kode geskryf vir ons. Dit is die verspreiding kode genoem. So ons is nie net die skryf van ons eie kode van nuuts af nie. Inteendeel, is ons in te vul die leemtes in 'n paar pre-bestaande kode. 

Die find.c program vra vir nommers die hooiberg te vul, soek die hooiberg vir 'n gebruiker voorgelê naald, en doen dit deur te bel soort en Soek, funksies gedefinieer in helpers.c. So find.c is reeds geskryf. Jou werk is om helpers te skryf. 

So, wat doen ons? Ons is die uitvoering van twee funksies. Soek, wat terugkeer waar as 'n waarde word gevind in die hooiberg, terugkeer valse indien die waarde is nie in die hooiberg. En dan is ons ook die implementering van soort wat allerhande die skikking met die naam waardes. 

So laat se pak soek. Soek tans geïmplementeer as 'n lineêre soek, maar jy kan baie doen beter as dit. Lineêre soektog in O geïmplementeer N tyd, wat baie stadig. Alhoewel, kan dit soek enige gegewe lys om dit te. Jou werk is om binêre soek om te implementeer, wat loop tyd O log n. Dit is redelik vinnig. 

Maar daar is 'n bepaling. Binêre soek kan net soek deur pre-gesorteer lyste. Hoekom is dit? 

Wel, laat ons kyk na 'n voorbeeld. Gegewe 'n verskeidenheid van waardes, die hooiberg, ons gaan om te kyk vir 'n naald. En in hierdie voorbeeld, Die heelgetal drie. Die manier waarop binêre soek werk, is dat ons die middelste waarde van vergelyk die skikking aan die naald, baie soos hoe Ons het 'n telefoonboek oopgemaak om die middel bladsy in week nul. 

So na die middelste waarde te vergelyk die naald, kan jy weggooi óf die linker-of die regter helfte van die skikking deur strenger jou perke. In hierdie geval, aangesien drie, ons naald, is minder as 10, die middelste waarde, die reg gebind kan verminder. Maar probeer om jou grense te maak so styf as moontlik. As die middelste waarde is nie die naald, dan moet jy weet dat jy nie nodig het om te sluit dit in jou soektog. So jy is reg gebind kan draai die Soek perke net 'n klein bietjie meer, en so aan en so voort totdat jy jou naald. 

So wat beteken die pseudokode lyk? Wel, terwyl ons nog steeds deur die lys en nog elemente te hê kyk in, neem ons die middel van die lys, en vergelyk dat die Midde-waarde ons naald. As hulle gelyk is, dan beteken dit dat ons het het gevind dat die naald en ons kan terug waar. 

Andersins, as die naald is minder as Die middelste waarde is, dan beteken dit dat ons kan die regter helfte weggooi, en net soek die linkerkant van die skikking. Andersins, sal ons soek die regterkant van die skikking. En aan die einde, as jy het nie meer elemente links te soek, maar jy nog nie jou naald gevind nie, dan is jy terugkeer valse omdat die naald beslis nie in die hooiberg. 

Nou 'n netjiese ding oor hierdie pseudokode in binêre soek is, is dat dit kan wees geïnterpreteer as óf 'n iteratiewe of rekursiewe implementering. So is dit rekursiewe sou wees as jy genoem die soek funksie binne die soektog funksioneer op óf die helfte van die skikking. Ons sal 'n bietjie later in die dek rekursie Natuurlik, maar weet dat dit 'n opsie as jy wil om te probeer. 

Nou laat ons kyk na soort. Sorteer neem 'n skikking en die heelgetal n, wat is die grootte van die skikking. Nou is daar verskillende tipes van spesies, en jy kan kyk na 'n paar kortbroek vir demonstrasies en verduidelikings. Die opbrengs tipe vir ons soort funksie is nietig. So dit beteken dat ons nie gaan enige skikking te terugkeer uit sorteer. Ons is eintlik van plan om die baie verander skikking wat in ons geslaag het. 

En dit is moontlik omdat skikkings is geslaag deur verwysing in C. Nou sal ons sien later meer hieroor, maar die essensiële verskil tussen die verbygaan in iets soos 'n heelgetal en slaag in 'n skikking, is dat wanneer jy slaag in 'n heelgetal, C is net gaan om te 'n afskrif van die heelgetal en slaag dit na die funksie. Die oorspronklike veranderlike sal nie verander word nie Sodra die funksie is klaar. Met 'n skikking, aan die ander kant, is dit gaan nie 'n kopie te maak, en jy sal eintlik besig wees baie verskeidenheid self. 

So 'n tipe van soort is die seleksie soort. Die keuse soort werk deur te begin by die begin, en dan moet jy Itereer oor en vind die kleinste element. En dan moet jy ruil dat kleinste element met die eerste een. En dan beweeg jy na die tweede element , Vind die volgende kleinste element, en dan ruil dit met die tweede element in die skikking gevolg die eerste element is reeds uitgesorteer. En so dan gaan jy voort vir elke element in die identifisering van die kleinste waarde en uitruiling dit uit. 

Want ek is gelyk aan 0, is die heel eerste element om n minus 1, jy gaan te vergelyk elke volgende waarde na wat en vind Die indeks van die minimum waarde. Sodra jy die minimum waarde-indeks jy kan daardie waarde van verskeidenheid ruil minimum en verskeidenheid I. 

Nog 'n tipe van soort wat jy kan implementeer is borrel soort. So borrel soort herhaal oor die lys aangrensende elemente en vergelyk uitruiling die elemente wat is in die verkeerde volgorde. En op hierdie manier, die grootste element sal borrel tot die einde. En die lys is weer nie meer gesorteer elemente is omgeruil. 

So dit is twee voorbeelde van soort algoritmes wat jy kan implementeer vir die vonds program. Sodra jy klaar is soort, en jy het gedoen soek, is jy klaar. My naam is Zamyla, en dit is CS50. 

[Speel van musiek]