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

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

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

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

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

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

Тапсырмалар варианттары:

Енгізілетін мәліметтер (алғашқы массив) пен шығатын мәліметтерді (сұрыпталған массив) бүтін сандардан тұратын текстік файл ретінде қалыптастыру керек.

Өткен әдістерді есептерге қолданып көр:

1. Қатардың медианасын табу керек, яғни, элементтердің бір жартысындағы кез-келгенінен үлкен және екінші жартысындағы кез-келгенінен кішкентай болатын элемент (егер қатардың элементтер саны жұп болатын болса, онда көрсетілген қасиетке ие болатын екі мәннің орташа мәнін алу керек).

2. «Көпіршік» сұрыптау әдісінде, егер қандай да бір екі көршілес элемент реттелмеген болса (мысалы, a[4] пен a[5]), олар ауыстырылады, одан кейін алгоритм келесі жұпты a[5] пен a[6] салыстыруға көшеді. Оның орынына a[4] элементін ғана қарап, оның қатардың жоғарғы жағына жүіп шығуына мүмкіндік беруге болады. Ол үшін a[4] пен a[3] салыстырамыз. Егер a[3] үлкен болса, ауыстыру жүргіземіз де, a[3] пен a[2] салыстырамыз. Осы көрсетілген әдісті жүзеге асыр.

3. Бүтін санды массивте бірдей элементтердің ең үлкен санын тап.

4. N бүтін сан берілген, a мен b аралығында неше сан жатыр?