Сортировка данных в массиве

Сортировка данных в массиве

Метод выбора.

Сравнивает первый элемент массива последовательно со всеми последующими элементами и меняет местами больший с меньшим.

	1	2	3	4
а	4	-2	13	7

Пример отсортируем массив а по убыванию методом выбора. Пусть I –индекс массива, k – переменная для временного хранения данных. За один цикл отсортировать массив невозможно, тогда j будет счетчик переборов.

Разберем сортировку массива с помощью таблицы. При первом проходе будем сравнивать значение a[1] со значениями a[2],a[3],a[4]. Значит j=1, а цикл начнется со второго элемента.i=2

	j	i	A[j]	A[i]	a[j]<a[i]	k=a[i]	a[i]=a[j]	A[j]=k
1 2 3 4 а 4 -2 13 7	1	2	4	-2	no
1 2 3 4 а 13 -2 4 7	1	3	4	13	yes	13	4	13
	1	4	13	7	no

После первого прохода максимальный элемент находится в первой ячейки массива.

Второй проход, будем сравнивать значения a[2] cо значениями a[3],a[4]. Значит j=2, а цикл начнется с третьего элемента i=3.

1 2 3 4 а 13 4 -2 7	2	3	-2	4	yes	4	-2	4
1 2 3 4 а 13 7 -2 4	2	4	4	7	yes	7	4	7

Последний проход осталось отсортировать последние элементы a[3] и a[4], j=3, а i=4.

1 2 3 4 а 13 7 4 -2

3

4

-2

7

yes

-2

7

7

На основе этой таблицы можно составить блок схему решения данной задачи

Самостоятельно напишите программу сортировки массива данным методом массив заполните случайными числами.

program v11;

uses crt;

const N=4;

var

k, i,j:integer;

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

begin

clrscr;

randomize;

writeln ('метод выбора упорядочить по убыванию');

for i:=1 to N do

begin

a[i]:=round(random*10);

write (a[i]:4);

end;

writeln;

for j:=1 to N do

for i:=j+1 to N do

if a[j]<a[i] then

begin

k:=a[i];

a[i]:=a[j];

a[j]:=k;

end;

for i:=1 to N do

write (a[i]:4);

end.

Методом обмена.

Особенность метода является сравнение не каждого элемента со всеми, а сравнение в парах соседних элементов.

	1	2	3	4
а	4	-2	13	7

Пример отсортируем массив а по убыванию методом выбора. Пусть i –индекс массива, k – переменная для временного хранения данных. За один цикл отсортировать массив невозможно, тогда j будет переменна прохождения переборов.

Разберем работу с помощью таблицы. При первом просмотре будем сравнивать значение a[1] со значениями a[2], a[2] и a[3], a[3] и a[4]. Значит j=1, и цикл начнется с первого элемента i=1

Из таблицы видно что эта задача решается за три прохождения. Составим блок схему. И составим программу.

	j	i	i+1	a[i]	a[i+1]	a[i[<a[i+1]	k=a[i]	a[i]=a[i+1]	A[i+1]=k
1 2 3 4 а 4 -2 13 7	1	1	2	4	-2	no
1 2 3 4 а 4 13 -2 7	1	2	3	-2	13	yes	-2	13	-2
1 2 3 4 а 4 13 7 -2	1	3	4	-2	7	yea	-2	7	-2
1 2 3 4 а 13 -4 7 -2	2	1	2	4	13	yea	4	13	4
1 2 3 4 а 13 7 4 -2	2	2	3	4	7	yes	4	7	4
	3	2	3	4	-2	no

program v11;

uses crt;

const N=4;

var

k, i,j:integer;

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

begin

clrscr;

randomize;

writeln ('метод обмена упорядочить по убыванию');

for i:=1 to N do

begin

a[i]:=round(random*10);

write (a[i]:4);

end;

writeln;

for j:=1 to N-1do

for i:=1 to N-j do

if a[i]<a[i+1] then

begin

k:=a[i];

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

a[i+1]:=k;

end;

for i:=1 to N do

write (a[i]:4);

end.