Нәтижесінде , алтя элемент үшін 5+4+3+2+1 = 15 салыстыру және 8 орын ауыстырулар өткізілді.
Жалпы жағдайда, әр n-1 қадамда орташа n/2 салыстырулар өткізіледі, сондықтан салыстырулар саны үшін бағалау n(n-1)/2 жазбасымен бейнеленеді, яғни берілген әдіс O(n2) классына байланысты. Аналогті түрде, орын ауыстырулар саны да n2 мәніне пропорционалды. Бұл әдіс ең тиімді емес сұрыптау әдісі болып табылады. Мысалы, 1000 элементтер үшін салыстырулар саны 500 мыңға жұық болады.
Бағдарламалық түрде іске асыру екі циклдан тұрады: сыртқы нәтижі –алгоритмнің негізгі қадамдары, ішкі – элементтерді салыстырады және орындарын массивтің соңынан бастап ауыстырады.
for i := 2 to n do
begin
for j := n downto i do
if a[j-1] > a[j] then
begin temp := a[j-1]; a[j-1] := a[j]; a[j] := temp; end;
end;
№2 дәрістің бақылау сұрақтары
«Көпіршік» әдісінің ерекшелігі неде?
Бұл сұрыптау әдісі қандай классқа жатады?
Бұл әдіс тағы қалай аталады?
Берілген сұрыптау әдісінің ішіне қандай цикл жатады?
Берілген әдіс тиімді болып табылама?
Дәріс №3 Шейкерлік іріктеу
Дәрістің мақсаты- студенттерді шейкерлік сұрыптау әдісімен және негізгі принциптерімен таныстыру.
Берілген алгоритмнің негізінде келесі позициялар жатады. Қатал берілген қайталанулардан бас тарту керек, сыртқы цикл ішкі циклдың жұмыс барысында ешқандай орын ауыстырулар болмаған жағдайда өзінің жұмысын аяқтау керек.
Шейкерлік сұрыптау: ішкі циклдің ішіндегі өтулердің бағыттаррын өзгертіп отыру керек, сөйтіп элементтердің орындарын ауыстыруларынның бағыт бойынша және кері бағыттағы «ассиметриялылығын» компенсациялауға болады.
Біріншіден, егер массив бөлігінде қозғалыстарда орын ауыстырулар болмаса онда массивтің бұл бөлігі сұрыпталған болып есептеледі, сондықтан, оны қарастырудан алып тастауға болады.
Екіншіден, массивтің соңынан басына дейін өткенде минималды элемент бірінші позицияға тұрады, ал максималды элемент тек бір позицияға оң жаққа қарай қозғалады.
Массивтің жұмыс бөлігінің шектері әр итерацияның орын ауыстыруында орнықтырылады. Массив рет бойынша оң жақтан сол жаққа және сол жақтан оң жаққа кезек кезек қарастырылады.
Бұл сұрыптаудың үздік жағдайы — сұрыпталған массив (О(n)), ең жаманы — кері бағытта сұрыпталған массив (O(n²)).
Салыстырулар санының ең кіші мәні Шейкер-сұрыптауында C=N-1. Бұл сұрыпталған массивте тек бір өтуге сәйкес (үздік жағдай)
Берілген алгоритмнің С++ тіліндегі реализациясы:
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
template
void sheikerSort(Type *arrayOfElements, int n){
int left, rigth, last;
left = 0;
last=rigth = n-1;
do{
for (int i = rigth; i>=left; i--){
if (arrayOfElements[i]
swapp(arrayOfElements[i],arrayOfElements[i-1]);
last = i;
}
}
left = last+1;
for (int i = left ; i<=rigth;i++){
if (arrayOfElements[i]
swapp(arrayOfElements[i],arrayOfElements[i-1]);
last = i;
}
}
rigth = last-1;
}while (left<=rigth);
};
|
Swapp функциясы:
?
1
2
3
4
5
|
template void swapp(Type &a, Type &b){
Type c = a;
a = b;
b = c;
};
|
№3дәрістің бақылау сұрақтары
Шейкерлік сұрыптау қай әдістің жақсартылған версиясы болып табылады?
Бұл әдістің ең үздік жағдайы болып не табылады?
Неге бұл әдісті шейкерлік деп атаған?
Шейкерлік әдісте сұрыптау неше бағыт бойынша өткізіледі?
Дәріс №4. Тікелей қосулары бар іріктеу
Дәрістің мақсаты- студенттерге берілген сқрыптауда қолданылатын негізгі түсініктемелерін беру, оларға әдістің негізін түсіндіру.
Тікелей қосулары бар іріктеу алдында айтылған іріктеулерге ұқсайды.
Ұқсас түрде массивтің бөлігінде жүрістер өткізіледі, және аналогтық түрде оның басында сұрыпталған тізім пайда болады.
Алгоритмді i-ші қадамдағы амалдардан бастап қарастырайық. Алдында айтылғандай, рет бұл уақытқа дейін екі бөлікке бөлінеді: дайын a[0]...a[i] және реттелмеген a[i+1]...a[n].
Келесі, алгоритмнің әр (i+1)-ші қадамында a[i+1] элементін аламызда дайын массивтің керекті орнына қоямыз.
Кезекті элементтің орны оның алдында тұрған элементпен салыстырулар бойынша табылады.
Нәтижеге тәуелді элемент немесе өз орнында қалады немесе олар орындарымен ауысады.
Сонымен, қосулар процессінде біз х элементін массивтің басына қоыямыз, бірақ кейде тқұтатулар орналастырамыз, егер
Х-тан кіші элемент табылса немесе
Тізімнің басына жетсек.
template
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
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
a[j-1] = a[j];
// элементті қою
a[j-1] = backup;
}
setmin(T& x) функциясы қолданушыме құрастырулы керек. Ол x алдын ала белгілі минималды элементті алмастырады (кіші немесе тең) массивтің барлық элементтерінде.
|
№4 дәрістің бақылау сұрақтары
Берілген әдіс «көпіршік » және таңдау әдісінен немен ерекшелінеді?
Кезекті элементті дұрыс орны қай жолмен табылады?
Ортақ жіне ең жаман жағдай қалай бағаланады?
«Күзетші элемент» деген не?
setmin(T& x) функциясы нені орындайды?
Дәріс №5. Шелл іріктеуі.
Дәрістің мақсаты –студенттерді берілген әдіспен таныстыру және сұрыптаудың негізгі амалдарымен таныстыру.
Шелл әдісі қосулар әдісінің жақсартылған нұсқасы.
Шелл әдісінің алгоритмі екі негізгі амалдың көп рет қайталанудан тұрады:
бір ереже бойынша массивтің кейбір элементтерін біріктіру
біріктірілген элементтер арасында әдеттегідей қосу әдісімен сұрыптау
Бірінші кезеңде жеткілікті улкен қадамды кіріс жиынның элементтері топталады. Мысалы, барлық 1000-ші элементтер, яғни топтар құрастырылады:
Топ 1: 1, 1001, 2001, 3001 және т.б.
Топ 2: 2, 1002, 2002, 3002 және т.б.
Топ 3: 3, 1003, 2003, 3003 және т.б.
. . . . . . . . . . . . . . . . . . . . .
Топ 1000: 1000, 2000, 3000 және т.б.
Әр топтың ішінде әдеттегідей қосу сұрыптауы орындалады, бұл топтағы элементтер саны аз болғандықтан тиімді болады.
Екінші кезеңді топтасу кішірек қадаммен орындалады, мысалы - қалған барлық жүзінші элементтер. Әр топта тағыда әдеттегідей сұрыптау орындалады. Бірінші кезеңнен кейін әр топта жиын бөлікті топталған болады.
..........
Соңғы кезеңде басында топтасы 1 қадаммен орындалады, бұл n өлшемді тек бір жиынды құрастырады, содан кейін – практикалық түрде сұрыпталған жиын іріктіріледі.
Мысалы. Берілген жиын: 15 – 33 – 42 – 07 – 12 - 19
3 санына тең қадаммен бөлеміз, бізде 2 элементтен тұратын і топ бар, әрқайссысын жеке жеке сұрыптаймыз:
топ 1: 15 – 07 => 07 – 15 (1 салыстыру, 1 ауыстыру)
топ 2: 33 – 12 => 12 – 33 (1 салыстыру, 1 ауыстыру)
топ 3: 42 – 19 => 19 – 42 (1 салыстыру, 1 ауыстыру)
сандардың жаңа жиыны: 07 – 15 – 12 – 33 – 19 – 42
2 санға тең 3 элементтен бөлеміз, олар жеке сұрыпталады:
топ 1: 07 – 12 – 19 => реттелген (2 салыстыру, 0 ауыстыру)
топ 2: 15 – 33 – 42 => реттелген (2 салыстыру, 0 ауыстыру)
сандардың жаңа жиыны: 07 – 12 – 19 – 15 – 33 – 42
Соңғы қадамы 1 тең бөлу сандардың керекті жиынын береді; оған 5 салыстырулары бар қосу іріктеуі қолданылады және тек бір орын ауыстыру орындалады, сонымен біз нәтижеге ие боламыз.
Сонымен – 12 салыстыру және 4 ауыстыру, алдында қарастырылған әдістерден жақсырақ емес. Бірақ мұнда екі факторды ескеру керек.
1, 3, 5, 9, 17, 33, . . . (жалпы формула: tk = (2* tk-1) –1 )
1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767 . . . (жалпы формула: tk = (2* tk-1) +1, ал қарапайымы – (2k – 1)).
Бағдарламалық түрде іске асыру
for m := 1 to t do {t – топтасудың қадамдарының саны, m – қадамның номірі}
begin
k := h [m]; {берілген массивте қадамның өлшемін таңдау }
for i := k + 1 to n do {қосу сұрыптауы әр топтың ішінде }
begin
temp := a [i]; j := i – k;
while (j > 0) and (temp < a [j]) do
begin
a [j + k] := a [j]; j := j – k;
end;
a [j + k] := temp;
end;
end;
Шелла әдісінің күрделілігі O(n1,2) сәйкестікпен бағаланады,бұл қарапайым әдістерге қарағанда әлде қайда жақсы.
№5 дәрістің бақылау сұрақтары
Шелл әдісі неде негізделеді?
Бұл әдіс өзінің атын неден алды?
Берілген әдіс сқрыптау әдістерінің қай классына жатады?
Берілген әдістің күрделілігі қалай бағаланады?
Шелл әдісінің тиімділігі неге тәуелді?
Дәріс №6. Бөлуі бар сұрыптау (жылдам сұрыптау)
Дәрістің мақсаты- студенттерді жақсартылған әдістердің біоеуңмен таныстыру, негізгі терминдермен және түсініктермен таныстыру.
Бөлуі бар әдіс Чарльзом Хоаром деген ғалыммен 1962 жылы ұсынылды.
Кесте 6. Жылдам сұрыптаудың мысалысы
Массивтің бастапқы қалпы
|
8 23 5 65 |44| 33 1 6
|
қадам 1 (x ретінде a[5] алынады)
|
|--------|
8 23 5 6 44 33 1 65
|---|
8 23 5 6 1 33 44 65
|
қадам 2 (a[1], a[5] массивінде x ретінде a[3] таңдалады)
|
8 23 |5| 6 1 33 44 65
|--------|
1 23 5 6 8 33 44 65
|--|
1 5 23 6 8 33 44 65
|
қадам 3 (a[3], a[5] массивінде x ретінде a[4] таңдалады)
|
1 5 23 |6| 8 33 44 65
|----|
1 5 8 6 23 33 44 65
|
қадам 4 (a[3], a[4] массивінде a[4] таңдалады)
|
1 5 8 |6| 23 33 44 65
|--|
1 5 6 8 23 33 44 65
|
Алгоритм тектен тек жылдам деп атамаған, өйткені, оның салыстырулар және алмасулар саны O(n?log n) жазбасымен бағаланады.
№6 дәрістің бақылау сұрақтары
Жылдам сұрыптаудың негізгі идеясы неде?
Бұл әдіс кіммен ұсынылды?
Негі бұл әдіс жылдам сұрыптау деп аталады?
Жылдам сұрыптау алгоритмімен қолданып бір мысал келтіріңіз?
Дәріс №7. Пирамидті іріктеу
Дәрістің мақсаты – студенттерге пирамидті сұрыптаудың толық жазбалауын беру.
Пирамидті сұрыптау Дж. Уильямс ғалымымен 1964 жылы ұсынылды. Бұл алгоритм массивтің кез келген элементтерін сұрыптауға арналған; оған қажетті қосымша жады көлемі берілген деректерге тәуелді емес. Алгоритмнің жұмыс істеу уақыты –орташа жағдайда, және ең жаман жағдайда және ең үздік жағдайда бірдей болады.
Берілген дәрісте бұл алгоритмнің базалық нұсқасы қарастырылатын болады, бұл алгоритмның жылдамдығы жоғары емес. Жылдамдықтары жоғарырақ алгоритмдердің нұсқаларын сәз Интернетте «Heap sort modification» типті сұраныс арқылы таба аласыз.
Арғатай барлық жерлерде массивтің бірінші элементінің индексі 0 деп есептеп отырамыз.
Достарыңызбен бөлісу: |