Қазақстан республикасының бiлiм және ғылым министрлiгi

Нәтижесінде , алтя элемент үшін 5+4+3+2+1 = 15 салыстыру және 8 орын ауыстырулар өткізілді.

Жалпы жағдайда, әр n-1 қадамда орташа n/2 салыстырулар өткізіледі, сондықтан салыстырулар саны үшін бағалау n(n-1)/2 жазбасымен бейнеленеді, яғни берілген әдіс O(n²) классына байланысты. Аналогті түрде, орын ауыстырулар саны да n² мәніне пропорционалды. Бұл әдіс ең тиімді емес сұрыптау әдісі болып табылады. Мысалы, 1000 элементтер үшін салыстырулар саны 500 мыңға жұық болады.

Бағдарламалық түрде іске асыру екі циклдан тұрады: сыртқы нәтижі –алгоритмнің негізгі қадамдары, ішкі – элементтерді салыстырады және орындарын массивтің соңынан бастап ауыстырады.

1. 
   «Көпіршік» әдісінің ерекшелігі неде?
   
2. 
   Бұл сұрыптау әдісі қандай классқа жатады?
   
3. 
   Бұл әдіс тағы қалай аталады?
   
4. 
   Берілген сұрыптау әдісінің ішіне қандай цикл жатады?
   
5. 
   Берілген әдіс тиімді болып табылама?
   

Біріншіден, егер массив бөлігінде қозғалыстарда орын ауыстырулар болмаса онда массивтің бұл бөлігі сұрыпталған болып есептеледі, сондықтан, оны қарастырудан алып тастауға болады.

Берілген алгоритмнің С++ тіліндегі реализациясы:

1. 
   Шейкерлік сұрыптау қай әдістің жақсартылған версиясы болып табылады?
   
2. 
   Бұл әдістің ең үздік жағдайы болып не табылады?
   
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 алдын ала белгілі минималды элементті алмастырады (кіші немесе тең) массивтің барлық элементтерінде.

1. 
   Берілген әдіс «көпіршік » және таңдау әдісінен немен ерекшелінеді?
   
2. 
   Кезекті элементті дұрыс орны қай жолмен табылады?
   
3. 
   Ортақ жіне ең жаман жағдай қалай бағаланады?
   
4. 
   «Күзетші элемент» деген не?
   
5. 
   setmin(T& x) функциясы нені орындайды?
   

Шелл әдісінің алгоритмі екі негізгі амалдың көп рет қайталанудан тұрады:

     бір ереже бойынша массивтің кейбір элементтерін біріктіру

        біріктірілген элементтер арасында әдеттегідей қосу әдісімен сұрыптау

Бірінші кезеңде жеткілікті улкен қадамды кіріс жиынның элементтері топталады. Мысалы, барлық 1000-ші элементтер, яғни топтар құрастырылады:
Топ 1: 1, 1001, 2001, 3001 және т.б.

Топ 2: 2, 1002, 2002, 3002 және т.б.

Топ 3: 3, 1003, 2003, 3003 және т.б.

. . . . . . . . . . . . . . . . . . . . .

Топ 1000: 1000, 2000, 3000 және т.б.
Әр топтың ішінде әдеттегідей қосу сұрыптауы орындалады, бұл топтағы элементтер саны аз болғандықтан тиімді болады.

Екінші кезеңді топтасу кішірек қадаммен орындалады, мысалы - қалған барлық жүзінші элементтер. Әр топта тағыда әдеттегідей сұрыптау орындалады. Бірінші кезеңнен кейін әр топта жиын бөлікті топталған болады.

..........

Соңғы кезеңде басында топтасы 1 қадаммен орындалады, бұл n өлшемді тек бір жиынды құрастырады, содан кейін – практикалық түрде сұрыпталған жиын іріктіріледі.

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

Сонымен – 12 салыстыру және 4 ауыстыру, алдында қарастырылған әдістерден жақсырақ емес. Бірақ мұнда екі факторды ескеру керек.

1, 3, 5, 9, 17, 33, . . . (жалпы формула: t_k = (2* t_k-1) –1 )

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767 . . . (жалпы формула: t_k = (2* t_k-1) +1, ал қарапайымы – (2^k – 1)).

Бағдарламалық түрде іске асыру

for m := 1 to t do {t – топтасудың қадамдарының саны, m – қадамның номірі}

begin

k := h [m]; {берілген массивте қадамның өлшемін таңдау }

temp := a [i]; j := i – k;

a [j + k] := a [j]; j := j – k;

a [j + k] := temp;

Шелла әдісінің күрделілігі O(n^1,2) сәйкестікпен бағаланады,бұл қарапайым әдістерге қарағанда әлде қайда жақсы.

1. 
   Шелл әдісі неде негізделеді?
   
2. 
   Бұл әдіс өзінің атын неден алды?
   
3. 
   Берілген әдіс сқрыптау әдістерінің қай классына жатады?
   
4. 
   Берілген әдістің күрделілігі қалай бағаланады?
   
5. 
   Шелл әдісінің тиімділігі неге тәуелді?
   

1. 
   Жылдам сұрыптаудың негізгі идеясы неде?
   
2. 
   Бұл әдіс кіммен ұсынылды?
   
3. 
   Негі бұл әдіс жылдам сұрыптау деп аталады?
   
4. 
   Жылдам сұрыптау алгоритмімен қолданып бір мысал келтіріңіз?
   

Берілген дәрісте бұл алгоритмнің базалық нұсқасы қарастырылатын болады, бұл алгоритмның жылдамдығы жоғары емес. Жылдамдықтары жоғарырақ алгоритмдердің нұсқаларын сәз Интернетте «Heap sort modification» типті сұраныс арқылы таба аласыз.