>> [Музика свира]
>> ЗАМИЛА цхан: Прва ствар коју би могао Обавештење о налаза је да смо већ
су код написан за нас.
Ово се назива дистрибуција код.
Дакле, ми не само писање наше више Код са нуле.
Уместо тога, ми смо попуњавање празнина у неком већ постојећом шифром.
>> Финд.ц Програм пита за бројеве да попуни пласту сена, тражи
пласту сена за корисника подноси игле, и то чини овај позивом врсту и
сеарцх, функције дефинисане у хелперс.ц.
Дакле финд.ц је написано већ.
Ваш посао је да пишем помагаче.
>> Дакле, шта ми радимо?
Ми спровођење две функције.
Претрага, који враћа труе ако вредност се налази у пласту сена, враћа
фалсе ако је вредност не у пласту сена.
И онда смо такође спроводи врсту који сортира низ називом вредности.
>> Па хајде да се позабаве претрагу.
Тражи се тренутно спроводи као линеарно претраживање, али можете да урадите много
боље од тога.
Линеарно претраживање се спроводи у О од н времена, који је прилично спор.
Мада, могуће је претражити сваки списак дати на њега.
Ваш посао је да спроведе бинарну претрагу, који је остао од времена О лог н.
То је прилично брзо.
>> Али постоји одредба.
Бинарни претраживање може само тражење кроз унапред сортираних листама.
Зашто је то тако?
>> Па погледајмо пример.
Имајући у виду низ вредности, пласту сена, ћемо бити у потрази
за иглу.
И у овом примеру, цео број три.
Начин на који ради је бинарна претрага да упоредимо средњу вредност
низ на игле, много ми се како отворили смо именик за средину
страна у недељу нула.
>> Дакле, након поређења средњу вредност игла, можете одбаците или
лево или десно половини низа пооштравањем своје границе.
У овом случају, од три, наш игла, је мање од 10, средња вредност,
Право граница може смањити.
Али покушајте да направите границе као чврсто могуће.
Ако средња вредност није игла, онда знате да не морате да
укључити га у претрагу.
Дакле, ти си у праву граница може затегнути Претрага границе само мали мало више,
и тако даље и тако даље до сте пронашли своју иглу.
>> Дакле, шта Псеудокод изгледа?
Па док ми још увек гледа кроз листа и даље имају елементе
изгледају у, узмемо средину листе, и упоредите ту средњу вредност
наша игла.
Ако су једнаки, онда то значи да смо нашао иглу и можемо
ретурн труе.
>> У супротном, ако игла мање од средња вредност, онда значи да смо
може одбацити праву половину, а само Претраживач леву страну низа.
У супротном, ми ћемо претрагу десна страна низа.
И на крају, ако не имати било више елемената лева за претраживање, али вам
нису пронашли своју иглу још, онда сте ретурн фалсе јер игла
дефинитивно није у пласту сена.
>> Сада уредан ствар у вези овог псеудокоду у бинарном потрази је да може да буде
тумачити као било итеративни или рекурзивно имплементација.
Дакле, било би рекурзивна ако зове функција претраге у потрази
функционисати на било половини низа.
Ми ћемо покрити рекурзија нешто касније у Наравно, али не знам да је то
опција уколико желите да пробате.
>> Сада ћемо погледати врсте.
Сортирај узима низ и цео н, што је величина низа.
Сада постоје различите различите врсте врста, а можете да погледате неке
шорц за демонстрације и објашњења.
Повратни тип за наше врста функција је празнина.
То значи да не идемо да се врати било који низ од врсте.
Ми у ствари ће се променити врло низ који је донет у нама.
>> И то је могуће зато што су низови прошао по референци у Ц Сада ћемо
види више о овоме касније, али Битна разлика између усвајања
у нечему као што цео број и доношење у низу, је да када сте
проћи у цео број, Ц је само да направите копију тог интегер и проћи
га на функцију.
Оригинални променљива неће се мењати када функција заврши.
Са низом, с друге стране, то је неће да направи копију, а ви ћете
заправо уређивање Сама веома низ.
>> Дакле, једна врста врста је Избор врста.
Избор Сортирај дела, са почетком у почетак, а онда поновити
преко и наћи најмањи елемент.
И онда ви мењате да најмањи елемент са првом.
А онда сте прешли на други елемент , Наћи следећи најмањи
елемент, а затим заменити да са Други елемент у низу, јер
Први елемент је већ сортиран.
И тако онда наставите за сваки елемент у идентификовању најмањи
вредност и замене га.
>> Јер једнако 0, први елемент до н минус 1, идете да упоредите
свака наредна вредност након тога и наћи индекс минималне вредности.
Када пронађете минимална вредност индекса, можете да мењате вредност низа
минимална и низ И.
>> Други тип врсте које можете имплементирати је мехур врста.
Дакле мехур сортирање понавља преко листе упоређујући суседне елементе и
замене елементе који су у погрешним редоследом.
И на овај начин, највећи елеменат ће балон до краја.
А листа је сортирана једном нема више елементи су заменили.
>> Дакле, то су два примера врсте алгоритми које можете имплементирати за
налаз програма.
Када завршите врста, а ви сте уради претрагу, готов си.
Моје име је Замила, а то је ЦС50.
>> [Музика свира]