13- дәріс Тақырыбы: Іздеу алгоритмдері. Сызықтық және екілік іздеу іздеу алгоритмдері
жүктеу/скачать 19,84 Kb.
|
1 2
Байланысты:13- д ріс Та ырыбы Іздеу алгоритмдері. Сызы ты ж не екілік ізд
- Бұл бет үшін навигация:
- Сызықты сұрыптау
| Реттеу, сұрыптау алгоритмі
Деректерге көп қолданылатын амалдардың бірі – сұрыптау. Сұрыптау дегеніміз – массив элементтерін белгілі бір ережені сақтайтындай етіп, реттеп орналастыру. Сұрыптау ішкі және сыртқы деп бөлінеді. Сыртқы сұрыптауға сыртқы жадыдағы деректерді сұрыптау жатады. Ал ішкі сұрыптауға ішкі жадыға деректерді реттеп орналастыру жатады. Ішкі сұрыптау бірнеше әдіспен орындалады: 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)-салыстыру саны бойынша. Өзін тексеру сұрақтары 1. Реттелмеген массивте біртіндеп іздеу алгоритмі қалай жүреді? 2. Реттелген массивте бинарлы іздеу алгоритмі қалай жүреді? 3. Сұрыптаудың қандай әдістері бар? жүктеу/скачать 19,84 Kb. Достарыңызбен бөлісу:
|
1 2