«Информатиканың теориялық негіздері»
-ДӘРІС. Іздеу және тандау алгоритмдері
жүктеу/скачать 0,6 Mb.
|
- Бұл бет үшін навигация:
- Тізбектеліп іздеу.
- Бинарлық іздеу.
- 13-ДӘРІС. Сұрыптау. Қарастырылатын сұрақтар
| 12-ДӘРІС. Іздеу және тандау алгоритмдері.
Қарастырылатын сұрақтар: Тізбекті іздеу. Екілік іздеу. Таңдау. Іздеу (поиск) екіге бөлінеді: Тізбектеліп іздеу. Бинарлық іздеу. Тізбектеліп іздеу. Тізбектеліп іздеудің мағынасы элементтерді тізбекпен таңдап алуды және элементтерді кілт мәнімен салыстырудан тұрады. Функция парамертлер ретінде массивті, элементтер санын және кілт мәнін алады. Сәйкес элементтің индексін қайталайды, егер іздеу сәтсіз болса, -1 мәнін береді. Тізбектеліп іздеу кез келген тізбек үшін қолайлы, тізбектеліп іздеудің орталық тиімділігі O(n) тең болады. Бинарлық іздеу. Бинарлық іздеулер тек қана реттелген тізімдер үшін ғана қолданылады. Мысалы элементтер тұратын массив берілсін. Тізімнің басындағы және соңындағы элементтердің индекстері мынадай low=0 high=n-1 дейін болады. Бинарлық іздеудің алгоритмі: Массивтің ортаңғы элементінің индексін табу: mid=(low+high)/2. Орталық элементтің мәнін кілтпен салыстыру «Key». Егер салыстыру нәтижесінде сәйкестік бар болса, онда mid индексін кілтті табу үшін қолданамыз. Егер орталық элемент мәні кілттен кіші болса, онда қарастырылып отырған тізімнің оң жағындағы бөлігінде іздеу жүргіземіз. Егер керісінше үлкен болса, онда сол жақтағы бөлігінде іздеу жүргіземіз. Егер ізделіп отырған элемент тізімде жоқ болса, онда үзу индикаторын береміз. Мысалға: Бүтін сандар тұратын А массиві берілсін. 33 кілті берілген элементі бар табу керек. Мысал элементтері: А
Low=0
High=8 mid=4
33>A(mid) 0 1 2 3 4 5 6 7 8
mid Low=5 High=8
mid=6 33>A(mid) 0 1 2 3 4 5 6 7 8
mid Low=7
High=8 mid=7
33=A(mid) Сонда тізбектеліп іздеуде 8 салыстыру, ал бинарлық іздеуде 3 салыстыру жүргізіледі. 13-ДӘРІС. Сұрыптау. Қарастырылатын сұрақтар: Қосулар арқылы сұрыптау. Көпіршік сұрыптауы. Шелл сұрыптауы. Түпкі сұрыптау. Пирамидалық сұрыптау. Тоғыстырма сұрыптау. Жылдам сұрыптау. Сыртқы көпфазалық сұрыптау. Массивтерді сұрыптау алгоритмдері 4-ке бөлінеді: Таңдау арқылы сұрыптау. Ауыстыру арқылы сұрыптау (көпіршік әдіісі). Қою арқылы арқылы сұрыптау. Тез сұрыптау. Сұрыптау немесе объектілер тізімін реттеу деп осы объектілердің қандай да бір сызықтық реттілікке қатысты өсуі мен кемуі бойынша орындауды айтамыз. Сұрыптаудың мәні сонда жазулар тізімінің реттілігін кілттік өріс мәндері кемімейтін тізбек құратындай етуіміз керек. Басқа сөзбен айтқанда R1, R2, .. , Rn жазулары кілттік мәндері K1, K2,…,Kn орналасуы керек. Ki1 Мұнда реттелген тізбектегі кілттердің бірдей мәндері бар жазулар бір-бірімен қатар орындалады. Сұрыптау әдістері 2 категорияға бөлінеді: - массивтерді сұрыптау (ішкі сұрыптау) - тізбектелген файлдарды сұрыптау (сыртқы сұрыптау). Массивтер ішкі оперативті жадыда орналасады. Оған кез келген уақытта тез кіруге болады. Ал сыртқы сұрыптау реттеуге тиісті мәліметтер көлемі өте үлкен болғанда мәліметтердің оперативті жадыға симай қалғанда қолданылады.
жүктеу/скачать 0,6 Mb. Достарыңызбен бөлісу:
|