Дәріс. Массивтерді іздеу мен сұрыптаудың әдістері мен алгоритмдері

Массивтерді сұрыптау немесе реттеу массив элементтерiн өсу немесе кемуі реті бойынша орналасқан жағдайда ғана жасалынады. Реттеу есебі статистикалық ақпарларды, анықтама материалдарды және т.б. рәсiмдеу кезінде пайда болады. Сұрыптаудың бірнеше әдістері бар. Массивтерді сұрыптаудың кейбір алгоритмдерін сиппаттайық.

1. Таңдау бойынша сұрыптау алгоритмі

a1, a2, a3, …, an бүтін немес нақты сандар массивын қарастырып көрейік. Элементтердің орнын ауыстырғанда осы массив элементтерінің ауысуы кему реті бойынша емес (өсу реті бойынша емес) реттелуі керек. Массивтегі бірінші орында – ең кіші элемент, екінші орында – қалған элементтердің арасындағы ең кіші элемент және т.б. орналасуы қажет. Алгоритм келесідей болады: массивтің ең кіші мәнді элементті табу, бірінші элементпен орнын ауыстыру. Осы қадамды екінші элементтен бастап қайта қайталау.

2. Айырбастау бойынша сұрыптау алгоритмі.

a1, a2,a3, …, an сандарын тізбектеп қарастырып, a[i] > a[ i+1] болатындай ең кіші i-ды табу. a[i] және a[ i+1] орындарын ауыстыру, a[ i+1] және т.б. элементтерін қарастыруды қайта бастау. Осылай ең үлкен сан соңғы орынға орналасады. Қарастырылып отырылған элементтердің санын бірге азайту арқылы келесі қарастыруларды қайтадан басынан бастау. Масив тек қана бірінші және екінші элемент қатысқан қарастырудан кейін реттеледі.

3. Қарапайым ендірмелер арқылы сұрыптау алгоритмі.

a2, a3, …, an реттін қарастырып, a[i] әр жаңа әлементтін a1, a2, a3, …, a[i-1] реттелген жиынының қолайлы орнына орналастыру. Бұл орын a[i]-мен a1, a3, …, a[i-1] реттелген элементтерін тізбектік салытыруымен анықталады.

Бір өлшемді массивті кемуі реті бойынша айырбастау сұрыптау әдісі көмегімен сұрыптаудың мысалы.

Program sortmass;

Const n=;

Var

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

i, j, c: integer;

begin

{ массивті толтыру }

randomize;

for i:=1 to n do

a[i]:=random (n);

{ массивті баспаға шығару}

for i:=1 to n do

write(a[i]:4);

writeln;

for i:=1 to n-1 do

for j:=i+1 to n do

if a[j] > a[i] then

begin

c:=a[i];

a[i]:= a[j];

a[j]:=c;

end;

{сұрыпталған массивті баспаға шығару }

for i:=1 to n do

write(a[i]:4);

end.

Негізгі әдебиет: 1 [104-107]

Қосымша әдебиет: 6 [73-80], 7 [227-265]

Бақылау сұрақтары

1. Қандай жағдайда массивтің сұрыптауы орындалады?

2. Таңдау бойынша сұрыптау алгоритмін сипаттаңыз.

3. Айырбастау бойынша сұрыптау алгоритмін сипаттаңыз.

4. Қарапайым ендірмелер арқылы сұрыптау алгоритмін сипаттаңыз.

5. Сұрыптау алгоритмдердің айырмашылығы қандай?

Контрольные вопросы

1. В каких случаях производится упорядочение массива?

2. Опишите алгоритм сортировки выбором.

3. Опишите алгоритм сортировки обменами.

4. Опишите алгоритм сортировки простыми вставками.

5. В чем различие алгоритмов сортировки?

Дата добавления: 2015-07-08