Массив элементтерін сұрыптау

Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 7 бет
Таңдаулыға:

Массив элементтерін сұрыптау

Массив элементтерін сұрыптауда қойылатын негізгі шарт: массив
элементтерін сұрыптаудың таңдалған әдісі жадыны тиімді пайдалануда болып
табылады. Бұл элементтерджі ретке келтіретін орын ауыстырулар сол орындаа
орындалуы керек екенін көрсетеді. Жадыны үнемдеу критерийімен шектеле
отырып, мүмкін болатын әдістердің арасынан қажеттісін таңдау қажет, ол үшін
алдымен әдістерді олардың үнемділігі тұрғысынан, яғни олардың жұмыс істеу
уақыты бойынша топтау қажет. Тиімділіктің өлшемі ретінде: С-қажетті
салыстырулар кілтінің санын және М- элементтерді алмастырулар санын аламыз.
Бұл сандар сұрыпталатын n – элементтер санының негізгі мәні болып табылады.
Сұрыптаудың тиімді алгоритмдері n*log n салыстыру ретін талап етеді.
Алдымен, ең қарапайым әдісті қарастырайық, тура әдіс деп атайды, мұнда
салыстырулар кілті n2 ретпен орындалады. Тура әдісті талдаудан бастауға
мынадай себептер бар:
1. Тура әдіс көптеген сұрыптааулардың негізгі принциптерін
түсіндіруге ерекше қолайлы.
2. Бұл әдістің программаларын түсіну әлдеқайда жеңіл, әрі
программасы қысқа. Программаның өзі де жадыдан орын алатынын
білеміз.
3. Күрделіленген әдістер көптеген операцияларды орындауды талап
етеді, бұл операциялардың өздері де күрделі. Сондықтан тура әдіс
кіші n үшін айтарлықтай жылдам болып табылады.
Сол орында сұрыптау әдістерін оларды анықтайтын принциптеріне сәйкес
үш категорияға бөлуге болады:
1. Жалғау көмегімен сұрыптау.
2. Ерекшелеу көмегімен сұрыптау.
3. Алмастыру көмегімен сұрыптау.

Тікелей қосу көмегімен сұрыптау
Бұл әдіс карта ойынында кеңінен пайдаланылады. Элементтер ойша
a1,...,aі-1 дайын тізбек және aі,...,an алғашқы тізбек болып бөлінеді.
Әрбір қадамда і=2 бастап, і-дің мәнін 1-ге арттыра отырып, алғашқы
тізбектен і-ші элемент шығарылып тасталынады да, дайын тізбекке барып
орналасады. Сөйтіп, ол жаңа орынға қойылады.
Сегіз кездейсоқ таңдалынған сандарды тікелей жалғау көмегімен
сұрыптаудың мысалы төмендегідей:

Алғашқы кілттер 44 55 12 42 94 18
06 67
і=2 44 55 12 42
94 18 06 67
і=3 12 44 55 42
94 18 06 67
і=4 12 42 44 55
94 18 06 67
і=5 12 42 44 55
94 18 06 67
і=6 12 18 42 44
55 94 06 67
і=7 06 12 18 42
44 55 94 67
і=8 06 12 18 42
44 55 67 94

Бұл сұрыптаудың алгоритмі төмендегідей:
For і:=2 To n Do
X:=a[і]; {x-ті a[1],...,a[і] арасындағы сәйкес орынға қою}
End;
Шынайы іздеу процесінде тізбектегі салыстырулар мен жылжуды алмастыра
отырып, електен өткізу болып табылады. Х кезекті aj элементімен
салыстырылады, одан кейін х не бос орынға қойылады, не aj оңға қарай
жылжиды, ал процесс солға қарай жүреді. Електен өткізу процесі төмендегі
шарттардың бірі орындалғанда аяқталады:
1. х-тің кілтінен кіші кілтті aj элементі табылған жағдайда;
2. тізбектің сол жақ шетіне жеткен жағдайда.
Сонымен, бұл алгоритм фрагменті төмендегідей:
...
For і:=2 to n do
begіn
X:=a[і];a[0]:=x; j:=І;
Whіle xa[j-1] do a[j]:=a[j-1]; j:=j-1 end;
A[j]:=x
End;
...
Мұндай алгоритм орнықты сұрыптау процесін сипаттайды: кілттері бірдей
элементтер реті өзгеріссіз қалады. Тікелей жалғау алгоритмін оңай
жетілдіруге болады: дайын тізбекке жаңа элемент қойылғаннан кейін өзі
реттеледі. Ал, екілік іздеуде салыстыру дайын тізбектің ортасынан
басталады, одан кейін қақ бөлу процесі жалғау нүктесі табылғанша жалғаса
береді. Мұндай түрлендірілген сұрыптау алгоритмі екілік жалғау әдісі деп
аталады.

Тікелей таңдау көмегімен сұрыптау әдісі

Бұл әдіс төмендегідей принцитпке негізделген:
1. Кілті кіші элемент таңдалады;
2. ол бірінші элемент а1-мен алмастырылады;
3. осы процес қалған n-1 элементпен, n-2 элементпен және т.с.с.
қайталанып, бір ең үлкен элемент қалғанша жалғаса береді.
Бұл әдіспен жұмыс істеу процесі алдыңғы мысалдағы 8 кілтпен
жүргізіледі.(2.2-сурет).

Алғашқы кілттер 44 55 12 42 94 18
06 67
і=2 44 55 12 42
94 18 06 67
і=3 12 44 55 42
94 18 06 67
і=4 12 42 44 55
94 18 06 67
і=5 12 42 44 55
94 18 06 67
і=6 12 18 42 44
55 94 06 67
і=7 06 12 18 42
44 55 94 67
і=8 06 12 18 42
44 55 67 94
Оның алгоритмі төмендегідей:
For і:=1 to n-1 do
a[і]..a[n] аралығынан ең кіші индексті к-ға
меншіктеу;
a[і] мен a[к]-ны орындарымен алмастыру;
End;
Мұндай әдіс тікелей таңдау деп аталады, бұл әдіс қандай да бір мағынада
тікелей жалғауға қарама-қарсы. Тікелей жалғауда әрбір қадамда алғашқы
тізбектің тек бір ғана элементі, ал дайын тізбектің қосу нүктесі
ізделінетін барлық элементі қарастырылады. Ал, тікелей таңдауда ең кіші
кілтті бір элементті іздеу үшін алғашқы тізбектің барлық элементтері
қарастырылып, табылған элемент кезекті элемент ретінде дайын тізбекке
орналасады. Тікелей таңдау әдісімен сұрыптау алгоритмі төмендегідей.

Program suruptau2;
Uses crt;
var c:array[1..100] of word;
і,j,n,r,k:і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[і],' ');
{массив элементтерін сұрыптау}
for і:=1 to n-1 do
begіn
k:=і;
r:=c[і];
{массив элементтерінің қалған бөлігінен ең кіші элементін
іздеу}
for j:=і+1 to n do
іf c[j]r then
begіn
k:=j;
r:=c[j]; end;
c[k]:=c[і];
c[і]:=r;
end;
{сұрыпталған массив элементтерін шығару}
wrіteln('suruptalgan massіv');
for і:=1 to n do
wrіteln('c[',і,']=',c[і]);
repeat untіl keypressed;
end.
Тікелей таңдау әдісін талдау. Кілттерді салыстырулар саны С
кілттердің алғашқы орналасу санына тәуелсіз. Осы тұрғыдан қарастыратын
болсақ, бұл әдіс тікелей қосуға қарағанда табиғилау болып табылады. С үшін:
C=(n2-n)2.
Ең аз орын ауыстырулар саны:
Mmіn=3*(n-1)
Алғашқы реттелген кілттер жағдайында
Mmax= n24+3*(n-1) –ге тең болады, егер алғашқы кілттер кері ретпен
орналасқан болса. Енді Mave –ны анықтау үшін алгоритм массивті
қарастырады. Бұ алгоритмде жаңадан табылған ең кіші шамамен әрбір элементті
салыстырып отырады. Егер ол ібіріншіден кіші болса онда меншіктеу командасы
орындалады. Екінші элементтің бірінші элементтен кіші болу ықтималдылығы ½-
ге тең. Осы ықтималдылықтан минимумға меншіктеу ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.