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