Лекция тезистері
жүктеу/скачать 382.54 Kb.
|
- Бұл бет үшін навигация:
- 2. Сызықты сұрыптау
- 3. Кірістіру арқылы сұрыптау.
- 6-тақырып: « Алгоритмдер және деректер структурасы »
| 1. Көпіршіту әдісі
Әдістің бұлай аталуы массивтің 1-ші және 2-ші элементтері салыстырылып, егер 1-ші элемент үлкен болса, олар орындарын ауыстырады, ал үлкен болмаса орнында қалады, сонда ауыр элемент астына түсіп жеңілі бетіне шығатын болғандықтан көпіршу сияқты көрінеді. Мысалы. a1, a2, a3, … , an тізбегі берілген. Элементтерін өсу реті бойынша реттеу керек. алг реттеу (бүт n, нақ таб a[1:n]) aрг n, a нәт a басы бүт i, нақ Б әзір i≤n-1 ц. б. егер a[i] ≤a[i+1] онда i:=i+1 әйтпесе Б:=a[i]; a[i]:=a[i+1]; a[i+1]:=Б i:=1; бітті ц. с. а – ны шығару. Соңы. Дәл осылай кемуі бойынша да реттеуге болады. 2. Сызықты сұрыптау Массивтің ішінен ең үлкен элемент табылады. Ол элемент р-шы орында тұрсын. Сол элементті n-ші орындағы элементпен салыстырады. Егер n<>p болса, онда n-ші орында орналасқан элементпен орындарын ауыстырады. Әрі қарай қалған реттелмеген элементтердің ішінен тағы ең үлкен элемент табылады да, ол (n-1)-ші элементпен салыстырылады, егер ең үлкен элемент (n-1)-ші элементтен үлкен болса, орнында қалады да, болмаса орындарын ауыстырады. Осы процесс барлық элементтерге қолданылып шығады. Алгоритмі келесідей болады: Белгілеулер: a[1..n] –берілген массив болсын, r – массивтің реттелмеген элементтерінің саны. 1. R=n болсын. 2. Max=max{a[1..r]} табамыз. 3. Max<>r және a[max]<>a[r] болса, онда a{max] элементі мен a[r] элементі орындарын ауыстырады 4. әйтпесе R=r-1 деп реттелмеген келесі элементтерге көшеміз. Алғашқы r элементтер – реттелмеген элементтерді құрайды, ал соңғы n-r элементтер өсуі бойынша реттеледі. 5. Егер r=1 болса, онда реттеу аяқталады, әйтпесе 2-ші пунктке көшеді. 3. Кірістіру арқылы сұрыптау. Алдында қарастырылған көпіршіту және сызықты сұрыптау әдістері кемімелі қадаммен сұрыптауға жатады. Шынында да, әрбір сұрыптау итерациясын орындаған сайын реттелмеген элементтер саны 1-ге кеміп отырады. Ал кірістіру арқылы сұрыптау өзгеше принциппен орындалады: Массивтің алғашқы 2 элементі реттеледі де реттелген s жиынын құрайды. Сосын келесі екі элемент реттеледі де сол жағынан үлкен элемент, оң жағынан кіші элемент орналаспайтындай етіп s –реттелген жиынға кірістіріліп отырады. S жиынға кірістірілетін элементтің орны дихотомия әдісімен анықталады. Кірістіру әдісінде келесі бағалаулар дұрыс: Салыстыру саны=1+2+[log23]+1+[log24]+1+…+[log2(n-1)]+1=(n-1)+log2(n-1)!=nlog2n; Меншіктеу саны: min=0; max=3+4+5+…+n+1=(n+4)(n-1)/2 Күрделілігі: O(n2)-меншіктеу саны бойынша, O(nlog2n)-салыстыру саны бойынша. Өзін тексеру сұрақтары Реттелмеген массивте біртіндеп іздеу алгоритмі қалай жүреді? Реттелген массивте бинарлы іздеу алгоритмі қалай жүреді? Сұрыптаудың қандай әдістері бар? Ұсынылатын әдебиеттер Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж. Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж. Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г. Острейковский В.А. Информатика, Москва, 2000 г. Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990. 6-тақырып: «Алгоритмдер және деректер структурасы» жүктеу/скачать 382.54 Kb. Достарыңызбен бөлісу:
|