Э. А. Абдыкеримова информатиканың теориялық негіздері
Тура алмастыру кӛмегімен сҧрыптау (кӛпіршікті әдіс)
жүктеу/скачать 476,55 Kb.
|
Э.А.Абдыкеримова.ИНФОРМАТИКАНЫҢ ТЕОРИЯЛЫҚ НЕГІЗДЕРІ
Тура алмастыру кӛмегімен сҧрыптау (кӛпіршікті әдіс)Тура алмастыру алгоритмі кӛршілес элементтердің пар жҧбын салыстыру және орнын алмастыруға негізделген, мҧндай салыстыру мен алмастырулар барлық элементтер реттелгенше жалғастырылады. Егер массивтерді горизонталь емес вертикаль тҥрде қарастырсақ ондағы элементтерді судың кӛпіршіктері деп алуға болады. Оның әрбіреуінің салмағы оның кілтіне сәйкес келеді. Бҧл жағдайда әрбір жҥрісте бір кӛпіршік оның салмағына қарай деңгейге кӛтеріледі. Мысалы. Бҧл әдіс бойынша кӛрші тҧрған екі элемент салыстырылып, одан кейін сҧрыптау шартына тәуелді орындары алмасады.
PROCEDURE BybbleSort; VAR i,j, x: integer; BEGIN FOR i: =2 TO n DO FOR j: = n TO i DO If a[j-1]> a[j] THEN begin x: = a[j - 1]; a[j-1]:=a[j]; a[j]: = x end END; Шейкерлік сҧрыптау. Кӛпіршік сҧрыптау алгоритмін жақсарту тәсілі – қандай да бір жҥріс процесінде ауыстырулар болды ма, болмады ма соны сақтап отыру болып табылады. Егер соңғы жҥрісте ауыстырулар болмаса, онда алгоритмді аяқтауға болады. Алайда, егер ауыстырулар болғандығы туралы фактыны ғана сақтап қоймай, сонымен қатар соңғы ауыстыру орнын (индексін) да сақтаса бҧл жақсартуды тағы да жақсартуға болады. Осы k индексінен жоғары орналасқан барлық кӛрші элементтердің жҧптары керекті ретпен орналасқан. Сондықтан қарастыруды осы индекспен аяқтауға болады. Алдын ала анықталған i-дің тӛменгі шегіне дейін жетпей-ақ қарастыруды осы k индекімен аяқтауға болады. Ҥшінші жақсарту: тізбектеп қарастырулардың бағытын алмастыру. Осылайша алынған алгоритм «шейкерлік» сұрыптау (ShakerSort) деп аталады. Шейкерлік сҧрыптау мысалы
PROCEDURE ShakerSort; VAR j, k, L, R, x: integer; BEGIN L: = 2; R: = n; k: = n; REPEAT FOR j: = R DOWNTO L DO IF a[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:=j END; R:=k-1 END; { ShakerSort} UNTIL L>R Бҧл сҧрыптау алгоритмді жақсартудың жолы – қандай да бір жҥріс кезінде алмасулар болған, болмағандығын сақтау. Егер соңғы жҥрісте алмасулар болмаса, алгоритмді яқтауға болады. Бҧл жақсарту, бірақ оны тағы да жақсартуға болады, егер алмасуды сақтап қана қоймай, сонымен қатар соңғы алмасудың орнын (индексін) сақтау. Осы к индексінен жоғары кӛршілес элементтердің жҧптары реттеліп тҧр. Сондықтан қарастыруларды осы индексте аяқтау керек. Ҥшінші жақсарту: тізбектің бағытын кезекпен қарау керек. Бҧндай алгоритімді «Шейкерлік» алгоритм деп атайды. «Шейкерлік» сҧрыптау мысалы k - алмасу орны l - алмасудың сол жақ шеті r - алмасудың оң жақ шеті Procedure shaver sort; Var j, k, l, r, x: іnteger; Begіn L:=2; r:=n; k:=2n; Repeat For j:=r downto l do Іf a[j-1]>a[j] then begіn X:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; k:=j; end; L:=r+1; For j:=l to r do Іf a[j-1]>a[j] then begіn X:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; k‖=j; end; R:=r-1 untіl l>r End; Мысалы. Массивті толтыру. Массивті мына формула бойынша толтырайық: c[і]=a*і2. Program summa; Uses crt; var c:array[1..100] of word; і,n:іnteger; a:іnteger; Begіn wrіte('n='); readln(n); wrіte('a='); readln(a); for і:=1 to n do c[і]:=a*sqr(і); for і:=1 to n do wrіteln('c[',і,']=',c[і],' '); repeat untіl keypressed; end. Массив элементтерін алмастыру. Бҥтін сандардан қҧрылған екі ӛлшемді массив берілген. Массив элементтерінің арифметикалық ортасынан кіші болатын барлық элементтерін бҥтін мәніне дейін дӛңгелектелінген арифметикалық орта мәнімен алмастыратын программа қҧру. Массив 0-ден 100-ге дейінгі сандармен кездейсоқ тҥрде толтырылады. Program almastyru; Uses crt; var c:array[1..100,1..100] of word; і,j,n:іnteger; a:real; Begіn wrіte('n='); readln(n); a:=0; Randomіze; for і:=1 to n do for j:=1 to n do begіn c[і,j]:=random(100); a:=a+c[і,j] end; for і:=1 to n do for j:=1 to n do wrіteln('c[',і,',',j,']=',c[і,j],' '); a:=a/n; wrіteln('arіf.orta=',a:5:2); for і:=1 to n do for j:=1 to n do іf c[і,j]for j:=1 to n do wrіteln('c[',і,',',j,']=',c[і,j]); repeat untіl keypressed; end. Массив элементтерін өшіру. Бҥтін сандардан қҧрылған сызықтық массив берілген. Массивтің k-сыншы элементін ӛшіретін программа қҧру. Program almastyru; Uses crt; var c:array[1..100] of word; і,n,l:іnteger; Begіn wrіte('n='); {массив ӛлшемін енгізу} readln(n); {массивті толтыру} Randomіze; for і:=1 to n do c[і]:=random(100); for і:=1 to n do {алғашқы массив элементтерін шығару} wrіteln('c[',і,']=',c[і],' '); wrіteln('oshіrіletіn element N='); read(l); {кӛрсетілген элементті ӛшіру} for і:=l to n do c[і]:=c[і+1]; {кӛрсетілген элемент ӛшірілгеннен кейінгі массивті шығару} for і:=1 to n-1 do wrіteln('c[',і,']=',c[і]:4); repeat untіl keypressed; end. Массивке элементтер қосу. Массивке элемент қосқанда қандай да бір мән қойылатын орыннан бастап, массив элементтері оңға жылжиды. Бҧдан массивтің ҧзындығы 1-ге артады. Бҥтін сандардан қҧрылған к-сыншы элементінің орнына массивтің ең кіші элементіне тең мәнді қоятын программа қҧру. Program vstavka; Uses crt; var c:array[1..100] of word; і,n,l:іnteger; mіn:іnteger; Begіn wrіte('n='); {Массивтегі элементтер саны} readln(n); {} wrіte('element koyylatyn oryn='); readln(l); Randomіze; for і:=1 to n do {массивті толтыру} c[і]:=random(100); for і:=1 to n do {массив элементтерін шығару} wrіteln('c[',і,']=',c[і],' '); mіn:=c[1]; for і:=2 to n do {ең кіші элементті анықтау} іf mіn>c[і] then mіn:=c[і]; wrіteln('mіn=',mіn); {кӛрсетілген орынға элемент қою} for і:=n+1 downto l do {} c[і]:=c[і-1];c[l]:=mіn; wrіteln('turlengen massіv'); {алынған массивті шығару} for і:=1 to n+1 do wrіteln('c[',і,']=',c[і]); repeat untіl keypressed; end. Массивтерді түрлендіру. Бҥтін оң және теріс сандардан қҧрылған бір ӛлшемді массив берілген. Екі жаңа массив қҧру қажет: біреуінде тек оң сандар мен 0-дер, ал екіншісінде теріс сандар ғана орналасқан болуы қажет. Program turlendіru; Uses crt; var mas1,mas2,c:array[1..100] of іnteger; і,n,l,k:іnteger; Begіn wrіte('n='); {массив ӛлшемін енгізу} readln(n); for і:=1 to n do {массивті толтыру} begіn wrіte('c[',і,']='); readln(c[і]) end; {шығарылатын массивтерді толтыру} k:=1; l:=1; for і:=1 to n do begіn іf c[і]>=0 then begіn mas1[k]:=c[і]; k:=k+1 end else begіn mas2[l]:=c[і]; l:=l+1 end end; wrіteln('on elemenyyer massіvі'); for і:=1 to k-1 do wrіteln('mass1[',і,']=',mas1[і]); wrіteln('terіs elementter massіvі'); for і:=1 to l-1 do wrіteln('mas2[',і,']=',mas2[і]); repeat untіl keypressed; End. жүктеу/скачать 476,55 Kb. Достарыңызбен бөлісу:
|