Әдістемелік құрал
жүктеу/скачать 1,24 Mb. Pdf көрінісі
|
Алгоритм және оның мүмкіндіктері
- Бұл бет үшін навигация:
- Сұрыптау алгоритмі FC 5,15,35,30,20,45,35,5,65,75,40,50,60,70,30,40,25,10,45,55 1.
| операциялар
Көптеген қосымшаларда дисктердегі файлдарда орналасқан мәліметтерге кіру қажет болады. Мәліметтердің ұлкен жиындары жадыға бір уақытта сыйғызуға мүмкін емес миллиондаған жазулардан тұруы мүмкін. Оларды басқару 70 үшін сыртқы сұрыптау мен іздеу алгоритмдері қажет. Аппаратты тұрғыдан алғанда файл жазулары дискте сақталатын, белгілі ұзындықтағы мәліметтер блоктарын құрайды. Логикалық тұрғыдан алғанда жазулар файлда тізбектеліп орналасады. Файлдық жүйе жекелеген жазуларға, сондай-ақ, барлық файлға толығымен кіруді жүзеге асыруға мүмкіндік береді. Сыртқы сұрыптау Файлдар түрінде ұйымдастырылған мәліметтерді сұрыптау сыртқы сұрыптау деп аталады. Егер файл оперативті жадыда сыймайтындай үлкен болса, онда сұрыптау - өте үлкен проблема. Барлық мәліметтерді бір массивте сақтауға болмайтындықтан, оларды сақтау үшін уақытша файлдарды қолдану керек. Тура біріктіру арқылы сұрыптау екі реттелген тізімді біріктіретін жай біріктіру әдісін қолданады. Басты идеясы біртіндеп үлкейетін элементтер түрінде файл ұйымдастырылатынында, яғни жазулар тізбегі 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 элементті серияға біріктіреміз. Мұнда реттелген тізімдерді біріктіру алгоритмін пайдаланамыз. 71 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 сұрыпталған файлына соңғы рет бірікенде аяқталады. жүктеу/скачать 1,24 Mb. Достарыңызбен бөлісу:
|