Сұрыпталған тізбектерді біріктіру

Екі А жіне В реттелген тізімдер берілген. Оның ұзындықтары сәйкесінше m және n. Біріктіру нәтижесінде ұзындығы m және n болатын С реттелген тізімін алу қажет. әрбір элемент бойынша біріктіру жүргізіледі. Ағымдағы өткізу нүктесі әрбір тізімнің басына орналасады. Ағымдағы нүктедегі мәндер салыстырылады. Нәтижесінде солардың кішісі массивке көшіріледі. Тізбектегі мән өңделіп болғаннан кейін келесі санға бір қадам жасалады да, салыстыру жалғастырылады.

Тізімдер алғашында реттелген болғандықтан элементтер шығатын массивке сұрыпталған ретпен көшіріледі. Тізбектің біреуі аяқталғаннан кейін келесі тізбектің қалған бөліктері яғни элементтері шығтын массивке көшіріле салады.

Сұрыпталған тізбектерді біріктіру алгоритмі

1. Бір тізбек немесе тізбектің екеуі де біткенше келесі әрекеттерді орындау керек. Яғни, егер 1-тізбектің 1-элементі 2-тізбектің элементіне тең немесе кіші болса, онда оны шығатын тізбекке жазып қойып, 1-тізбектің келесі элементіне көшу керек. Әйтпесе, шығатын тізбекке 2-тізбектің элементін жазып, 2-тізбектің келесі элементіне көшу керек. Одан кейін шығатын тізбектің келесі элементіне көшу керек.

Егер біреуі аяғына дейін өңделмесе, онда сол қалдықты шығатын тізбекке көшіру керек.

Дәріс 5.

Тізімдерде іздеу әректтерін жүргізу

Мақсаты: Тізбектерде элементті іздеу ұғымын енгізу.

Іздеу (поиск) екіге бөлінеді:

1. Тізбектеліп іздеу.

2. Бинарлық іздеу.

1. Тізбектеліп іздеу. Тізбектеліп іздеудің мағынасы элементтерді тізбекпен таңдап алуды және элементтерді кілт мәнімен салыстырудан тұрады.

Функция парамертлер ретінде массивті, элементтер санын және кілт мәнін алады. Сәйкес элементтің индексін қайталайды, егер іздеу сәтсіз болса, -1 мәнін береді. Тізбектеліп іздеу кез келген тізбек үшін қолайлы, тізбектеліп іздеудің орталық тиімділігі O(n) тең болады.

2. Бинарлық іздеу.

Бинарлық іздеулер тек қана реттелген тізімдер үшін ғана қолданылады. Мысалы элементтер тұратын массив берілсін. Тізімнің басындағы және соңындағы элементтердің индекстері мынадай low=0 high=n-1 дейін болады. Бинарлық іздеудің алгоритмі:

1. Массивтің ортаңғы элементінің индексін табу: mid=(low+high)/2.

2. Орталық элементтің мәнін кілтпен салыстыру «Key». Егер салыстыру нәтижесінде сәйкестік бар болса, онда mid индексін кілтті табу үшін қолданамыз. Егер орталық элемент мәні кілттен кіші болса, онда қарастырылып отырған тізімнің оң жағындағы бөлігінде іздеу жүргіземіз. Егер керісінше үлкен болса, онда сол жақтағы бөлігінде іздеу жүргіземіз.

3. Егер ізделіп отырған элемент тізімде жоқ болса, онда үзу индикаторын береміз.

Мысалға: Бүтін сандар тұратын А массиві берілсін. 33 кілті берілген элементі бар табу керек.

Мысал элементтері: А

0	1	2	3	4	5	6	7	8
-7	3	5	8	12	16	23	33	55

Low=0

High=8

mid=4

33>A(mid) 0 1 2 3 4 5 6 7 8

-7

3

5

8

12

16

23

33

55

mid

Low=5

High=8

mid=6

33>A(mid)

0 1 2 3 4 5 6 7 8

-7

3

5

8

12

16

23

33

55

mid

Low=7

High=8

mid=7

33=A(mid)

Сонда тізбектеліп іздеуде 8 салыстыру, ал бинарлық іздеуде 3 салыстыру жүргізіледі.

Дәріс 6.

Файлдар және сыртқы тасымалдаушылардағы мәліметтер мен операциялар.

Мақсаты: Файлдар және сыртқы тасымалдаушылардағы мәліметтер мен операциялар жүргізу ұғымын қалыптастыру. Балансталған көп жолдық бірігу, табиғи бірігу арқылы сұрыптау, сыртқы сұрыптау амалдарын түсіндіру.

Көптеген қосымшаларда дисктердегі файлдарда орналасқан мәліметтерге кіру қажет болады. Мәліметтердің ұлкен жиындары жадыға бір уақытта сыйғызуға мүмкін емес миллиондаған жазулардан тұруы мүмкін. Оларды басқару үшін сыртқы сұрыптау мен іздеу алгоритмдері қажет.

Аппаратты тұрғыдан алғанда файл жазулары дискте сақталатын, белгілі ұзындықтағы мәліметтер блоктарын құрайды. Логикалық тұрғыдан алғанда жазулар файлда тізбектеліп орналасады.

Файлдық жүйе жекелеген жазуларға, сондай-ақ, барлық файлға толығымен кіруді жүзеге асыруға мүмкіндік береді.

Сыртқы сұрыптау

Файлдар түрінде ұйымдастырылған мәліметтерді сұрыптау сыртқы сұрыптау деп аталады. Егер файл оперативті жадыда сыймайтындай үлкен болса, онда сұрыптау - өте үлкен проблема. Барлық мәліметтерді бір массивте сақтауға болмайтындықтан, оларды сақтау үшін уақытша файлдарды қолдану керек.

Тура біріктіру арқылы сұрыптау екі реттелген тізімді біріктіретін жай біріктіру әдісін қолданады. Басты идеясы біртіндеп үлкейетін элементтер түрінде файл ұйымдастырылатынында, яғни жазулар тізбегі r1<=r2<=…<=rn жазулар тізбегі. Мысалға, 3 деген ұзындықтағы сериялармен ұйымдастырылған бүтін сандар тізбегі:

7 15 29 7 11 13 16 22 31 5 12

Мұнда соңы 3 тен кем ұзындықта болуы мүмкін, бірақ оның жазулары да сұрыпталған.

Сұрыптау алгоритмі

FC 5,15,35,30,20,45,35,5,65,75,40,50,60,70,30,40,25,10,45,55

1. Файлды екіге бөлеміз. Оның элементтерін сәйкесінше екіге бөлеміз. Осылайша, әрбір жаңа файлда элементтер тізімі пайда болады.

2. Ішкі тізімдерді салыстырамыз. Яғни, FA файлынан және FB файлынан бір-бір элементтен таңдап алып, жай біріктіру алгоритмін пайдалана отырып, қайтадан FC файлына жазамыз. Осылайша, барлық элементе қайтадан FC файлға ауысқанша жалғастырамыз.

FА 5,35,20,35,65,40,60,30,25,45

FВ 15,30,45,5,75,50,70,40,10,55

FC 5,15,30,35,20,45,5,35,65,75,40,50,60,70,30,40,10,25,45,55

3. Бір қадамды қайталап, FА және FВ файлдарына екі элементті серияларды жазып шығарамыз.

FА 5,15,20,45,65,75,60,70,10,25

FВ 30,35,5,35,40,50,30,40,45,55

4. FА және FВ файлдарындағы екі элементті серияларды FC файлына 4 элементті серияға біріктіреміз. Мұнда реттелген тізімдерді біріктіру алгоритмін пайдаланамыз.

FC 5,15,30,35, 5,20,35,45

40 50 65 75 30 40 60 70 10 25 45 55

5. FС файлын екіге бөлетін қадамды FА және FВ файлында сәйкесінше 4 8 т.с.с элементтер серияларын құрай отырып және сериялардың әрбір жұптарын біріктіре отырып қайталаймыз. Процесс FА және FВ файлдары бір-бір реттелген тізімнен тұрғанда және олар FC сұрыпталған файлына соңғы рет бірікенде аяқталады.

Түзу бірігу сұрыптау анализі.

Сұрыптау бір элементі ішкі тізімдердің жүрістер сериясынан тұрады, әрбір жүрісте ішкі тізімнің ұзындығы екі еселенеді. Ол үшін log₂n жүріс қажет болады. Түзу бірігу арқылы сұрыптау 2n log₂n мәліметтерді қарауды талап етеді, сондықтан оның күрделілік реті O(n log ₂n).