Дәріс №4. Тікелей қосулары бар іріктеу

Дә рістің мақ саты- студенттерге берілген сқ рыптауда қ олданылатын негізгі тү сініктемелерін беру, оларғ а ә дістің негізін тү сіндіру.

Тікелей қ осулары бар іріктеу алдында айтылғ ан іріктеулерге ұ қ сайды. Ұ қ сас тү рде массивтің бө лігінде жү рістер ө ткізіледі, жә не аналогтық тү рде оның басында сұ рыпталғ ан тізім пайда болады. Алгоритмді i-ші қ адамдағ ы амалдардан бастап қ арастырайық. Алдында айтылғ андай, рет бұ л уақ ытқ а дейін екі бө лікке бө лінеді: дайын a[0]...a[i] жә не реттелмеген a[i+1]...a[n]. Келесі, алгоритмнің ә р (i+1)-ші қ адамында a[i+1] элементін аламызда дайын массивтің керекті орнына қ оямыз. Кезекті элементтің орны оның алдында тұ рғ ан элементпен салыстырулар бойынша табылады. Нә тижеге тә уелді элемент немесе ө з орнында қ алады немесе олар орындарымен ауысады. Сонымен, қ осулар процессінде біз х элементін массивтің басына қ оыямыз, бірақ кейде тқ ұ татулар орналастырамыз, егер 1. Х-тан кіші элемент табылса немесе 2. Тізімнің басына жетсек. template< class T> void insertSort(T a[], long size) { T x; long i, j; for (i=0; i < size; i++) { // ө тулер циклы, i – ө тудің номері x = a[i]; // дайын тізімде элементті іздеу for (j=i-1; j> =0 & & a[j] > x; j--) a[j+1] = a[j]; // элементті оң жақ қ а қ арай қ озғ алтамыз // орын табылды, элементті қ ою a[j+1] = x; }} Таң дауы бар сұ рыптау ә дісіне ұ қ сас салыстырулардың жә не орын ауыстырулардың ортақ жә не ең жаман саны Theta(n2) жазбасымен бағ аланады, қ осымша жады бұ л жағ дайда қ олданылмайды. Алгоритмді кішкене жақ сартуғ а болады. Ішкі циклдің ә р қ адамында ә шарт тексерілетінін белгілейік. Оларды біріктіруге болады, массивтің басына кү зетші элемент қ ойып. Ол алдын ала массивтің барлық элементтерінен кіші болуы тиіс. Онда j=0 болғ анда a[0] < = x ақ иқ ат болады. Цикл нө лбдік элементте тоқ татылады, бұ л j> =0 шартының мақ саты болды. Сонымен, сұ рыптау дұ рыс тү рде ө теді, ал ішкі циклдің ішінде бір салыстыруғ а аз болады. Ол Theta(n2) рет ө ткізілген десек, бұ л - нақ ты артық шылық. Бірақ сұ рыпталғ ан массив толық болмайды, оның ішінен бірінші элемен шығ ып кеткендіктен. Сұ рыптауды аяқ тау ү шін бұ л санды орнына қ айтару керек, содан кейін a[1]...a[n] сұ рыпталғ ан реттің ішіне қ ою керек. // кү зетші элементі бар қ осу сұ рыптауыtemplate< class T> inline void insertSortGuarded(T a[], long size) { T x; long i, j; T backup = a[0]; // бірінші элементті сақ тау setMin(a[0]); // минималды элементтің орнына қ ою // массивті сұ рыптау for (i=1; i < size; i++) { x = a[i]; for (j=i-1; a[j] > x; j--) a[j+1] = a[j]; a[j+1] = x; } // backup-ты дұ рыс орынғ а қ ою for (j=1; j< size & & a[j] < backup; j++) a[j-1] = a[j]; // элементті қ ою a[j-1] = backup; } setmin(T& x) функциясы қ олданушыме қ ұ растырулы керек. Ол x алдын ала белгілі минималды элементті алмастырады (кіші немесе тең) массивтің барлық элементтерінде.

№4 дә рістің бақ ылау сұ рақ тары

1. Берілген ә діс «кө піршік» жә не таң дау ә дісінен немен ерекшелінеді?

2. Кезекті элементті дұ рыс орны қ ай жолмен табылады?

3. Ортақ жіне ең жаман жағ дай қ алай бағ аланады?

4. «Кү зетші элемент» деген не?

5. setmin(T& x) функциясы нені орындайды?