4. Индексли избе-из излеўдиң эффективлиги

Егер болыўы мүмкин болған барлық жағдайлар тең итималлы деп алынса, ол жағдайда излеў эффективлигин төмендегише есаплаў мүмкин:

Белгилеўлерди киритип аламыз: m – индекс өлшеми; m = n / p; p – адым өлшеми

Q = (m+1)/2 + (p+1)/2 = (n/p+1)/2 + (p+1)/2 = n/2p+p/2+1 (*)

Q ды p бойынша дифференциаллап оны нольге теңлестиремиз:

dQ/dp=(d/dp) (n/2p+p/2+1)= - n / 2 p² + 1/2 = 0

Бул жерден

p²=n ;

(*) аңлатпада р орнына р_опт ды қойып төмендеги салыстырыўлар санын аламыз:

Q = +1

Демек, индексли избе-из излеўдиң эффективлиги тәртиби O ( ) болады.

5. Излеўди жетилистириў усыллары

Улыўма алғанда, кестеде ҳәр бир элементти излеў итималлығын қандайда бир мәнис пенен түсиндириў мүмкин. Кестеде изленип атырған элемент бар деп ойлайық. Ол жағдайда излеў әмелге асырылып атырған барлық кестени дискрет жағдайға ийе система сыпатында қараў мүмкин ҳәмде онда изленип атырған элементти табыў итималлығы – бул система i-ши жағдайының итималлығын p(i) деп алыў мүмкин.

Кестени дискрет система сыпатында қарағанымызда, ондағы салыстырыўлар саны дискрет тосынарлы муғдарлар мәнислериниң математикалық күтилмесин аңлатады.

Z=Q=1p(1)+2p(2)+3p(3)+…+np(n)

Илажы барынша p(1)³p(2) ³p(3) ³…³p(n) болса, мақсадке муўапық болады.

Бул шәрт салыстырыўлар санын кемейтип, эффективликти асырады. Себеби, избе-из излеў биринши элементтен басланғанлығы ушын ең көп мүрәжәт қылынатуғын элементти бириншисине қосыў керек.

Излеў кестесин қайта тәртиплестириўдиң ең көп ислетилетуғын еки усылы бар. Оларды бир бағытлы дизимлер мысалында көрип шығамыз.

6. Табылған элементти дизим басына қосыў арқалы кестени қайта тәртиплестириў

Усы усылдың мәниси соннан ибарат, берилген гилтке тең гилтли элемент дизимде биринши элемент деп өзлестириледи, қолғанлары болса кейиге сүриледи.

Келтирилген алгоритм дизим ушын да массив ушын да орынлы. Бирақ бул алгоритм массив ушын усынылмайды, себеби элементлерди жайластырыў көрсеткишлерди жайласытырыўдан көре бир қанша көп ўақыт талап етеди.

Дизимди қайта тәртиплестириў алгоритми:

Паскаль:

q:=nil;

p:=table;

while (p <> nil) do

begin

if key = p^.k then

begin

if q = nil

then 'жайластырыў шәрт емес'

search := p;

exit;

end;

q^.nxt := p^.nxt;

p^.nxt := table;

table := p;

exit;

end;

q := p;

p := p^.nxt;

end;

search := nil;

exit;

7.Транспозиция усылы

Усы усылда табылған элемент дизимде бир алдыңғы элемент пенен орын алмастырылады. Егерде усы элементке көп мүрәжәт қылынса, биреўден алдынға сүрилип барып нәтийжеде дизим басында болады.

Сызылма. Қоңсы элементлердиң орнын алмастырыў

р – жумысшы көрсеткиш

q – жәрдемши көрсеткиш, р дан бир адым арқада болады

s - жәрдемши көрсеткиш, q дан еки адым арқада болады

Транспозиция усылы алгоритми:

Паскаль:

s:=nil;

q:=nil;

p:=table;

while (p <> nil) do

begin

if key = p^.k then

‘транспонерлеймиз

begin

if q = nil then

begin

‘жайластырылмайды

search:=p;

exit;

end;

q^.nxt:=p^.nxt;

p^.nxt:=q;

if s = nil then

table := p;

else

begin

s^.nxt := p;

end;

search:=p;

exit;

end; end;

search:=nil; exit;

Усы усыл тек ғана дизимде, бәлким массивте де қолай (себеби тек ғана еки жақын турған элемент орын алмастырылады).

8. Жетилискен излеў тереги

Егер ажыратып алынған элементлер қандайда бир турақлы топламды пайда етсе, келеси излеўлер эффективрек болыўы ушын оларды бинар терек көринисинде аңлатыў мақсетке муўапық болыўы мүмкин.

Төменде келтирилген тереклерде бинар излеўди көрип шығайық ( а)ҳәм б) сызылма). Еки теректе де үшеўден элементке ийе - к1, к2, к3 болып бул жерде к1<к2<к3. к3 элементти излеў a) сызылмада еки салыстырыўды талап етсе, б) сызылмада болса бир салыстырыўды талап етеди.

Қандайда бир жазыўды ажыратып алыў ушын зәрүр болған гилтлерди салыстырыўлар саны бинар излеў терегиндеги усы жазыў басқышына биреўин қосқанына тең.

Ойлайық:

излеў аргументи key = к1 болыўы итималлығы - p1,

излеў аргументи key = к2 болыўы итималлығы – p3,

излеў аргументи key = к3 болыўы итималлығы – p3,

key < к1 болыўы итималлығы – q0,

к2 > key > к1 болыўы итималлығы – q1,

к3 > key > к2 болыўы итималлығы – q2,

key > к3 болыўы итималлығы – q3,

C1 - a) сызылмадағы салыстырыўлар саны,

C2 - б) сызылмадағы салыстырыўлар саны.

Сызылма а) Сызылма б)

Ол жағдайда ×р1+×р2+×р3+×q0+×q1+×q2+×q3 = 1

Қандайда бир излеўде күтилип атырған салыстырыўлар саны төмендегише болады:

C1 = 2×р1+1×р2+2×р3+2×q0+2×q1+2×q2+2×q3

C2 = 2×р1+3×р2+1×р3+2×q0+3×q1+3×q2+1×q3

Қандайда бир берилген гилтлер ҳәм итималлықлар топламында күтилип атырған салыстырыўлар санын минималластырыўшы бинар излеў тереги жетирискен делинеди. Терек жаратыў алгоритми бир қанша қыйын жумыс болсада, бирақ ол жаратқан теректе излеўди әмелге асырыў бир қанша эффектив болады. Тилекке қарсы, көпшилик жағдайда, излеў аргументи итималлығы алдыннан анық болмайды.

9.Бинар излеў (тең екиге бөлиў усылы)

Ойлайық, өсиў тәртибинде тәртиплестирилген санлар массиви берилген болсын. Усы усылдың тийкарғы идеясы соннан ибарат, тосынарлы қандайда бир A_M элемент алынады ҳәм ол Х излеў аргументи менен салыстырылады. Егер A_M=Х болса, ол жағдайда излеў жуўмақланады; егер A_M <X болса, ол жағдайда индекслери М нен киши яки тең болған барлық элементлерди келеси излеўден шығарып жибериледи. Тап сондай, егер A_M >X болса.

М қәлегенше таңланғанда да усынылып атырған алгоритм коррект ислейди. Сол себепли М ди сондай таңлаў керек, изертленип атырған алгоритм эффективрек нәтийже берсин, яғный оны сондай етип таңлайық, илажы барынша кейинги процесслерде қатнасыўшы элементлер саны кем болсын. Егер биз орташа элементти, яғный массив орташасын таңласақ шешим жетилискен болады.

Төмендеги сызылма көринисинде берилген массивти қарап шығайық. Ойлайық, бизден гилти 52 ге тең болған элементти табыў талап етилсин. Дәстлепки салыстырылатуғын элемент 49 болады. 49<52 болғаны ушын, кейинги излеў 49 дан жоқарыда турған элементлер арасында әмелге асырылады. Жаңа пайда болған массив ортасы 86. Егер берилген гилт пенен усы гилтти салыстырсақ 86>52 болады. Демек, нәўбеттеги излеўлер 86 менен 49 арасындағы элементлер ишинде әмелге асырылыўы керек. Кейинги адымда белгили болдады, көрилип атырған элементлер ортасындағы элемент гилти 52 ге тең. Солай етип, массивте берилген гилтке тең болған элементти таптық.

Жоқарыдағы алгоритмди әмелге асырыў программасы Паскал тилинде төмендегише болады:

Паскалда

low := 1;

hi := n;

while (low <= hi) do

begin

mid := (low + hi) div 2;

if key = k[mid] then

begin

search := mid;

exit;

end;

if key < k[mid]

then hi := mid - 1

else low := mid + 1;

end;

search := 0;

exit

Егер key = 101 болса, керекли жазыў 3 мәрте салыстырыўларда анықланады (избе-из излеўде салыстырыўлар саны 7 болар еди).

Егер С – салыстырыўлар саны ҳәм n – кестедеги элементлер саны болса, ол жағдайда

С = log₂n.

Мәселен, n = 1024.

Избе-из излеўде С = 512, бинар излеўде С = 10.

Егер үлкен көлемдеги мағлыўматлар ишинде излеў әмелге асырылып атырған болса, ол жағдайда бинар ҳәм индексли избе-из излеўди улыўмаластырып алып барыў мүмкин. Себеби, ҳәр еки излеў де тәртиплестирилген массивте әмелге асырылады.

Қадағалаў сораўлары

1. Излеў ўазыйпасы неден ибарат?

2. Ҳасыл гилт дегенде нени түсинесиз?

3. Дизимде берилген гилтли элемент жоқ болғанда қайсы әмел орынланады?

4. Избе-из излеў ҳәм индексли избе-из излеўлердиң парқы неден ибарат?

5. Олардан қайсы бири эффективрек ҳәм не себептен?

6. Кестени қайта тәртиплестириўдиң қандай усылларын билесиз?

7. Табылған элементти басына қосыў усылының транспозиция усылынан тийкарғы парқлары нелерден ибарат?

8. Усы усыллар мағлыўматлар қандай көринисте берилгенде тезиреқ ислейди?

9. Олар қандай дизимлерде ислейди, яғный тәртиплестирилген яки қәлеген?

10. Бинар излеўдиң мазмуны ҳәм мәниси неден ибарат?

11. Қандай етип бинар теректи шетлеп өтиў мүмкин?

12. Бинар излеўди массивте ислетиў мүмкинбе?

13. Егер бос болмаған теректе тамыр өширилетуғын болса, ол жағдайда оның орнына қайсы элемент өтеди?

8-Лекция. Саралаў (4 саат)

Реже:

1. Саралаў түсиниги, оның түрлери.

2. Туўрыдан туўры қосыў арқалы саралаў.

3. Туўрыдан туўры таңлаў арқалы саралаў.

4. Туўрыдан туўры алмастырыў арқалы саралаў.

5. Саралаўдың жақсыланған усыллары.

Саралаў – бул берилген топлам элементлерин қандайда бир тәртипте жайластырыў процесси. Саралаўдың мақсети тәртиплестирилген топламда керекли элементти табыўды аңсатластырыўдан ибарат. Саралаў программаларды трансляция қылынып атырғанда, мағлыўматлар жыйындысын сыртқы ядта шөлкемлестирилип атырғанда, китапханалар, каталоглар, мағлыўматлар базасы жаратылып атырғанда пайдаланылады. Бизге белгили, саралаўдың ҳәр түрли алгоритмлери бар. Себеби, бир мәселени саралаў ушын жүда көплеген ҳәр түрли алгоритмлерден пайдаланыў мүмкин. Берилген мәселени шешиўде базылары қурамалы болыўы мүмкин. Соның ушын саралаў мәселесинде алгоритмлердиң салыстырмалы анализин өткериў зәрүрлиги пайда болады.

Саралаў мәселесиниң қойылыўын төмендегише жазыў мүмкин.

Ойлайық, а₁, а₂ ,…, а_n, элементлер избе-излиги берилген болсын. Ол жағдайда саралаў алгоритми элементлерди массивке сондай етип жайластырады, нәтийжеде олар қандайда бир қатнасқа салыстырғанда f(а_к1)f(а_к2) …f(а_кn) тәртибине ийе болады. Әдетте f тәртиплестириў функциясы қандайда бир арнаўлы қағыйда менен есапланбастан, бәлким элементтиң гилт мәниси бойынша массив элементлери тәртиплестириледи.

Мағлыўматларға қайта ислеў берилип атырғанда мағлыўматтың информациялық майданын ҳәмде оның машинада жайласыўын (адресин) билиў зәрүр.

Саралаўдың еки түри бар: ишки ҳәм сыртқы:

• ишки саралаў бул оператив ядтағы саралаў;

• сыртқы саралаў – сыртқы ядта саралаў.

Саралаў бул мағлыўматлардың гилтлери бойынша ядта регуляр көринисте жайластырыў. Регулярлық дегенде мағлыўматлар гилт мәнислери бойынша массивте басынан ақырына шекем өсиўи яки кемейиўи түсиниледи.

Егер сараланып атырған жазыўлар ядта үлкен көлемди ийелесе, ол жағдайда оларды алмастырыўлар үлкен сарп (ўақыт ҳәм яд мәнисинде) талап қылады. Усы сарплаўды кемейтиў мақсетинде, саралаў гилтлер адреси кестесинен әмелге асырылады. Бунда тек ғана мағлыўмат көрсеткишлери алмастырылып, массив өз орнында қалады. Жоқарыдағы усыл адреслер кестесин саралаў усылы делинеди.

Сараланып атырғанда бир қыйлы гилтлер ушыраўы мүмкин, бул жағдайда сараланағаннан кейин бир қыйлы гилтлилер баслағыш тәртипте қандай жайласқан болса, усы тәртипте қалдырылыўы мақсетке муўапық болады (Бир қыйлы гилтлилер өзлерине салыстырғанда). Бундай усылға турақлы саралаў делинеди.

Саралаў эффективлигин бир неше дереклер бойынша баҳалаў мүмкин:

• саралаўға кеткен ўақыт;

• саралаў ушын талап қылынған оператив яд;

• программаны ислеп шығыўға кеткен ўақыт.

Биринши деректи қарап шығайық. Саралаў орынланғанда салыстырыўлар яки алмастырыўлар саны есаплаў мүмкин.

Ойлайық, Н = 0,01n² + 10n – салыстырыўлар саны. Егер n < 1000 болса, ол жағдайда екинши қосылыўшы үлкен, кери жағдайда яғный, n > 1000 болса, биринши қосылыўшы үлкен болады.

Демек, кишкене n лерде салыстырыўлар саны n ге тең болады, үлкен n ларда болса n² қа тең болады.

Саралаўда салыстырыўлар саны төмендеги аралықларда болады:

0(n log n) дан 0 (n²) гача; 0 (n) – идеал жағдайда.

Саралаўдың төмендегише усыллары бар:

• қатаң (туўрыдан-туўры) усыллар;

• жақсылаған усыллар.

Қатаң усыллар:

1. туўрыдан-туўры қосыў усылы;

2. туўрыдан-туўры таңлаў усылы;

3. туўрыдан-туўры алмастырыў усылы.

Жоқарыда келтирилген үш усылда да алмастырыўлар саны дерлик бир қыйлы болады.

Туўрыдан-туўры қосыў усылы менен саралаў

Бундай усыл карта ойынында кең қолланылады. Элементлер (карталар) қыялый “таяр” a(1),...,a(i-1) ҳәм баслағыш избе-изликлерге бөлинеди. Ҳәр бир адымда (i=2 ден басланып, ҳәр бир адымда бир бирликке асырылып барылады) баслағыш избе-изликтен i-ши элемент ажыратып алынып таяр избе-изликтиң керекли жерине қосылады.

Усынылып атырған усылды төмендеги мысалда көрип шығамыз.

Ойлайық, гилт мәниси 4, 5, 3, 8, 1, 7 болған элементлер берилген болсын.

Керекли жерди излеў процессин төмендеги тәртипте алып барыў қолай болады. Салыстырыўлар әмелге асырыў барысында, нәўбеттеги a(j) элемент пенен салыстырылады, кейин болса х бос орынға қойылады яки a(j) оңға сүриледи ҳәм процесс шепке “кетеди”. Соны итибарға алыў керек, саралаў процесси төмендеги шәртлерди биреўи орынланғанда жуўмақланады:

1. х элементи гилтинен киши гилтли a(j) элемент табылады.

2. таяр избе-изликтиң шеп тәрепи ақырына жетип барылды.

Усынылып атырған усыл алгоритми төмендегише болады:

Procedure StraightInsertion;

Var i,j:index; x:item;

begin

for i:=2 to n do

x:=a[i]; a[0]:=x; j:=1;

while x<a[j-1] do a[j]:=a[j-1]; j:=j-1; end;

a[j]:=x;

end;

end; StraightInsertion

Алгоритм эффективлиги

Ойлайық, салыстырыўлар саны С, жайластырыўлар саны М болсын. Егер массив элементлери кемейиў тәртибинде болса, ол жағдайда салыстырыўлар саны ең үлкен болып, ол ге тең болады, яғный . Жайластырыўлар саны болса ге тең болады, яғный . Егер берилген массив өсиў тәртибинде сараланған болса, ол жағдайда салыстырыўлар ҳәм жайластырыўлар саны ең киши болады, яғный , .

Туўрыдан-туўры таңлаў усылы менен саралаў

Ойлайық, a₁, a₂, … , a_n элементлер избе-излиги берилген болсын.

Усы усыл төмендеги принциплерге тийкарланған:

1. Берилген элементлер ишинен ең киши гилтке ийе элемент таңланады.

2. Усы элемент баслағыш избе-изликтеги биринши элемент a₁ менен орын алмасады.

3. Оннан кейин усы процесс қалған n-1 элемент, n-2 элемент ҳәм басқа, бир ең “үлкен” элемент қалғанға шекем даўам еттириледи.

Усынылап атырған усыл алгоритми төмендегише болады:

Паскаль тилндеги программасы:

Procedure StraightSelection

Var

i,j,k: index; x:item;

begin

for i:=1 to n-1 do

k:=I; x:=a[i];

for j:=i+1 to n do

if a[j]<x then k:=j; x:=a[k]

end;

end;

a[k]:=a[i];

a[i]:=x

end;

end StraightSelection

Алгоритм эффективлиги:

Салыстырыўлар саны М = .

Алмастырыўлар саны C_min = 3(n - 1), C_max = 3(n - 1) (n² тәртип).

Усы усыл бойынша саралаў орынланса, ең жаман жағдайда салыстырыўлар ҳәм алмастырыўлар саны тәртиби n² болады.

Туўрыдан-туўры алмастырыў усылы менен саралаў (көбикли)

Усы усылдың идеясы төмендегише: n - 1 мәрте массивте төменнен жоқарыға қарап жүрип гилтлер жуп-жубы менен салыстырылады. Егер төменги гилт мәниси жоқарыдағы жубы гилтинен киши болса, ол жағдайда олар орын алмастырылады.

Паскал тилиндеги программасы:

for i := 2 to n do

for j := n downto i do

if a[j - 1] > a[j] then

begin

x := a[j - 1];

a[j - 1] := a[j];

a[j] := x;

end;

Бизиң жағдайымызда бир өтиў “бийкар” болды. Элементлерди артықша жайластырмаў ушын байрақша киритиў мүмкин.

Көбикли усылдың жақсыланған усылы бул шейкер саралаў усылы болып, ҳәр бир өтиўден кейин цикл ишинде бағдар өзгертиледи.

Алгоритм эффективлиги:

салыстырыўлар саны М = ,

алмастырыўлар саны C_max = 3 .

Саралаўдың жақсылаған усыллары

Quiksort – тез саралаў усылы

Идеясы: Бул усыл алмастырыў усылындағы саралаўға тийисли болып оның тийкарын гилтлерди таңланған гилтке салыстырмалы ажыратыў қурайды.

6 дан шеп тәрепте гилтлери киши, оң тәрепте болса гилтлери 6 дан үлкен болған элементлер жайластырады (жоқарыдағы сызылма).

procedure Sort (L, R: integer);

begin

i := L;

j := r;

x := a[(L + r) div 2];

repeat

while a[i] < x do

i := i + 1;

while a[j] > x do

j := j - 1;

if i <= j then

begin

y := a[i];

a[i] := a[j];

a[j] := y;

i := i + 1;

j := j - 1

end;

until i > j;

if L < j then sort (L, j);

if i < r then sort (i, r);

end;

procedure QuickSort;

begin

sort (1, n);

end;

Алгоритм эффективлиги:

О(n log n) – ең эффектив усыл.

Шелл саралаўы (қысқарып барыўшы адымлар арқалы саралаў)

Туўры қосыў усылын 1959 жылы Д. Шелл тәрепинен жетилистириў усыныс етилген. Төмендеги сызылмада усы усыл көрсетилген:

Басында бир – биринен 4 адымда жайласқан элементлер өз – ара топарға бөлинип саралаў әмелге асырылады. Бундай процесс төртлик саралаў деп аталады. Биринши өтиўден кейин элементлер қайта топарға бөлинип, енди ҳәр еки адымдағы элементлер салыстырылады. Бул болса екилик саралаў деп аталады. Ҳәм ақырында, үшинши өтиўде әпиўайы яки жеккелик саралаў әмелге асырылады.

Бир қараўда усы усыл менен саралаў әмелге асырылғанда саралаў процесси кемейиў орнына артып баратырғандай түйилсе, элементлердиң орын алмастырыўлары салыстырмалы кем әмелге асырылады.

Көринип турыпты, бул усыл нәтийжесинде тәртиплестирилген массив пайда болып, ҳәр бир өтиўден кейин саралаўлар кемейип барады. Ең жаман жағдайда ақырғы жумысты жеккелик саралаў әмелге асырады.

Барьер усылынан пайдаланылғанда ҳәр бир саралаў өзиниң барьерине ийе болыўы керек ҳәмде программа оның орнын анықлаўы ушын оны илажы барынша аңсатластырыў керек. Соның ушын массивти [-h1..N] ге шекем кеңейтириў керек болады.

h[1..t] – адымлар өлшеми массиви

a[1..n] - сараланып атырған массив

k – саралаў адымы

x – қосылып атырған элемент мәниси

Subroutine ShellSort

const t = 3;

h(1) = 5;

h(2) = 3;

h(3) = 1;

var

h: array [1..t] of integer;

a: array [1..n] of integer;

k, x, m, t, i, j: integer;

begin

for m = 1 to t do

begin

k:= h(m);

for i = k + 1 to n do

begin

x:= a(i);

for j = i-k downto k do

begin

if x < a(j ) then

a(j+k):= a(j);

else

goto 1;

end ;

end;

end;

1: a(j+1) = x ;

end;

end .

Улыўма алғанда, қандай адымлар таңланғанда ең жақсы нәтийже алыныўы дәлилленбеген болсада, лекин бул адымлар бири екиншисиниң көбейтиўшилери болмаўы кереклиги анықланған.

Д. Кнут адымлардың төмендегише избе-излигин усыныс еткен (кери тәртипте): 1,3,7,15,31,…,яғный: h_m-1=2h_m+1, h_t=1, t = [log₂n] - 1. Егер адымлар усы көринисте анықланса, алгоритм эффективлиги тәртиби O(n^1.2).