2015-10-22
692
Сортировка массива.
Под сортировкой массива подразумевается процесс перестановки элементов с целью упорядочивания их в соответствии с каким-либо критерием. Например, если имеется массив а - целых чисел, то после сортировки по возрастанию должно выполняться условие: 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.
Упорядочение массива
Упорядочение (сортировка) - это расположение значений элементов массива в порядке возрастания или убывания их значений.
