Зертханалық жұмыс №1 Тақырыбы: Ақпаратты көрсету. Ақпаратты есептеу
жүктеу/скачать 0.88 Mb.
|
- Бұл бет үшін навигация:
- 12.3. Жеке тапсырмалар
- Зертханалық жұмыс №13 Тақырыбы: Шелл әдісі бойынша сұрыптау алгоритмі (13 апта, 2 сағ) 13.1. Жұмыс мақсаты
- 13.2. Әдістемелік нұсқау 13.2.1. Сұрыптау алгоритмі. Шелл әдісі. Ара қашықтығын кеміте отырып қосулар көмегімен сұрыптау.
| 1 2.2.2. Шейкерлік сұрыптау.Көпіршік сұрыптау алгоритмін жақсарту тәсілі – қандай да бір жүріс процесінде ауыстырулар болды ма, болмады ма соны сақтап отыру болып табылады. Егер соңғы жүрісте ауыстырулар болмаса, онда алгоритмді аяқтауға болады. Алайда, егер ауыстырулар болғандығы туралы фактыны ғана сақтап қоймай, сонымен қатар соңғы ауыстыру орнын (индексін) да сақтаса бұл жақсартуды тағы да жақсартуға болады. Осы k индексінен жоғары орналасқан барлық көрші элементтердің жұптары керекті ретпен орналасқан. Сондықтан қарастыруды осы индекспен аяқтауға болады. Алдын ала анықталған i-дің төменгі шегіне дейін жетпей-ақ қарастыруды осы k индекімен аяқтауға болады. Үшінші жақсарту: тізбектеп қарастырулардың бағытын алмастыру. Осылайша алынған алгоритм «шейкерлік» сұрыптау (ShakerSort) деп аталады.
Шейкерлік сұрыптау мысалы
PROCEDURE ShakerSort; VAR j, k, L, R, x: integer; BEGINL: = 2; R: = n; k: = n; REPEAT FOR j: = R DOWNTOLDO IFa[j-1]>a[j]THEN BEGIN x: = a[j-1]; a[j-1]:=a[j]; a[j]: = x; k: = j END; L: = k+1; FOR j:=L to R do IF a[j-1]>a[j] THEN BEGIN x:=a[j-1];a[j-1]:=a[j];a[j]:=x;k:=jEND; R:=k-1 UNTIL L>R END; { ShakerSort} 12.3. Жеке тапсырмалар Тізімді көпіршікті және Шейкерлік сұрыптау алгоритмі көмегімен жүргізілген барлық қадамдардың нәтижесін жазыңдар (7; 3; 9; 4; 2; 5; 6; 1; 8) (8; 6; 4; 3; 9; 7; 5; 1; 2) (1; 9; 6; 8; 4; 2; 7; 5; 3) (6; 3; 2; 8; 4; 7; 5; 9; 1) (4; 6; 8; 9; 5; 7; 3; 2; 1) (4; 7; 5; 1; 2; 9; 8; 3; 6) (8; 6; 2; 5; 9; 3; 4; 1; 7) (3; 9; 6; 8; 4; 7; 1; 5; 2) (23; 17; 21; 3; 42; 9; 13; 1; 2; 7; 35; 4) (2; 35; 8; 41; 9; 41; 11; 6; 58; 77; 23; 7) (7; 13; 52; 77; 53; 56; 68; 2; 71; 22; 95; 58) (51; 50; 52; 94; 15; 25; 38; 68; 15; 44; 84; 25) Зертханалық жұмыс №13 Тақырыбы: Шелл әдісі бойынша сұрыптау алгоритмі (13 апта, 2 сағ) 13.1. Жұмыс мақсаты – Шелл әдісі бойынша сұрыптау алгоритмдерін құрып үйрену. 13.2. Әдістемелік нұсқау 13.2.1. Сұрыптау алгоритмі. Шелл әдісі. Ара қашықтығын кеміте отырып қосулар көмегімен сұрыптау. 1959 жылы Д.Шелл тікелей қосу көмегімен сұрыптаудың жақсартылған тәсілін ұсынды. Әдістің өзі тікелей қосу әдісіндегі стандартты мысал негізінде көрсетіліп түсіндіріледі. Алдымен бір-бірінен ара қашықтығы 4 позиция (элемент) болатын элементтер топтастырылады және сұрыпталады. Мұндай процесс төртттік сұрыптау деп аталады. Мысалда сегіз элемент және әрбір топ тура екі элементтен тұрады. Бірінші жүрістен кейін элементтер қайта топтастырылады – енді топтың әрбір элементі бір-бірінен екі позицияда орналасқан – және қайта сұрыпталады. Бұл екілік сұрыптау деп аталады. Енді үшінші жүрісте әдеттегі немесе бірлік сұрыптау жүреді. 44 55 12 42 94 18 06 67 төрттік сұрыптау мынаны береді 44 18 06 42 94 55 12 67 екілік сұрыптау мынаны береді 06 18 12 42 44 55 94 67 бірлік сұрыптау мынаны береді 06 12 18 42 44 55 67 94 t = 4 үшін келтрілген алгороитм программа 13.1-де Shellsort процедурасымен сипатталған PROCEDURE ShellSort; CONST t = 4; VAR i, j,k,s; index; x: item; m: 1 .. t; h:ARRAY [1 .. t] OF INTEGER; BEGIN h[1]: = 9; h[2]: = 5; h[3] : = 3; h[4] : = 1; FOR m: = 1 TO t DO k: = h[m]; s: = -k; (*бөгет орны*) FOR i: = k + 1 NO n DO x: = a[i]; j: = i – k; IF s = 0 THEN s: = -k END; s: = s + 1; a[s] : = x; WHILE x < a[j] DO a[j + k] : =a[j];j:= j-k END; a [j + k] : = x END END END ShellSort Программа. 13.1 Шелл сұрыптауы. жүктеу/скачать 0.88 Mb. Достарыңызбен бөлісу:
|