Контрольная работа на массивы.

Сортировка массива.

Под сортировкой массива подразумевается процесс перестановки элементов с целью упорядочивания их в соответствии с каким-либо критерием. Например, если имеется массив а - целых чисел, то после сортировки по возрастанию должно выполняться условие: a[1]£a[2] £…£a[n], где n – верхняя граница индекса массива.

Существует много методов сортировки массивов. Но наиболее часто используемые это:

· метод прямого выбора (метод главного элемента);

· метод прямого обмена(метод пузырька).

Метод главного элемента.

Алгоритм сортировки массива по возрастанию методом прямого выбора или методом главного элемента может быть представлен так:

1. Просматривая массив от первого элемента, найти минимальный и поместить на место первого элемента, а первый на место минимального.

2. просматривая массив от второго элемента, найти минимальный и поместить его на место второго элемента, а второй на место минимального.

3. И так далее до предпоследнего элемента.

Ниже представлена программа сортировки массива целых чисел по возрастанию.

program vosr;

uses crt;

var a: array [1..15] of integer;

i, j, k, n, m, c: integer;

begin

clrscr;

writeln (‘’); readln (n);

for i:=1 to n do begin

write (i,’:’); readln (a[i]);

end;

for i:=1 to n-1 do begin

k:=i;

for j:=i+1 to n do

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

c:=a[i];

a[i]:=a[k];

a[k]:=c;

end;

for i:=1 to n do

writeln (a[i]);

readln;

end.

Метод прямого обмена (метод пузырька).

В основе алгоритма лежит обмен соседних элементов массива. Каждый элемент массива, начиная с первого сравнивается со следующим и если он больше следующего, то элементы меняются местами. Таким образом, элементы с наименьшим значением продвигаются к началу массива (всплывают), а элементы с большим значением – к концу массива (тонут), поэтому его и называют методом пузырька. Этот процесс повторяется на единицу меньше раз чем элементов в массиве, либо возможно другой способ реализации этого метода, повторяется до тех пор пока находятся соседние элементы, такие что элемент стоящий правее оказывается меньше элемента стоящего левее.

program vosr;

uses crt;

var a: array [1..15] of integer;

i, j, k, n, m, c, f: integer;

begin

clrscr;

writeln (‘’); readln (n);

for i:=1 to n do begin

write (i,’:’); readln (a[i]);

end;

for i:=1 to n-1 do begin

for j:=1 to n-1 do

if a[j]>a[j+1] then begin

c:=a[j];

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

a[j+1]:=c;

end;

end;

for i:=1 to n do

writeln (a[i]);

readln;

end.

program vosr;

uses crt;

var a: array [1..15] of integer;

i, j, k, n, m, c, f: integer;

begin

clrscr;

writeln (‘’); readln (n);

for i:=1 to n do begin

write (i,’:’); readln (a[i]);

end;

k:=n-1;

repeat

f:=0;

for i:=1 to k do

if a[i]>a[i+1] then begin

f:=1;

c:=a[i];

a[i]:=a[i+1];

a[i+1]:=c;

end;

dec(k);

until f=0;

for i:=1 to n do

writeln (a[i]);

readln;

end.