Теория

Под сортировкой обычно понимают процесс перестановки объектов данного множества в определенном порядке.

Цель сортировки - облегчение последующего поиска элементов в отсортированном множестве. В этом смысле элементы сортировки присутствуют почти во всех задачах. Методов сортировки много. Самые эффективные - те, которые экономно используют память. Разберем два простых метода, не задумываясь над экономией памяти.

Задание 1. Метод «пузырька». Сортировка по возрастанию. Сравниваются два соседних числа a_i и a_i+1. Если a_i>a_i+1, то делается перестановка. Самый "легкий" элемент поднимается вверх, как "пузырек". Перестановки продолжаются, пока все элементы не отсортируются.

Алгоритм и особенности этой сортировки таковы:

• 1. При первом проходе по массиву элементы попарно сравниваются между собой: первый со вторым, затем второй с третьим, следом третий с четвертым и т.д. Если предшествующий элемент оказывается больше последующего, то их меняют местами.

  2. Не трудно догадаться, что постепенно самое большое число оказывается последним. Остальная часть массива остается не отсортированной, хотя некоторое перемещение элементов с меньшим значением в начало массива наблюдается.

  3. При втором проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше.

  4. На третьем проходе уже не надо сравнивать предпоследний и третий элемент с конца. Поэтому число сравнений будет на два меньше, чем при первом проходе.

  5. В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение.

  6. После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен. Другими словами, количество проходов по массиву равно m-1, где m – это количество элементов массива.

  7. Количество сравнений в каждом проходе равно m-i, где i – это номер прохода по массиву (первый, второй, третий и т.д.).

  8. При обмене элементов массива обычно используется "буферная" (третья) переменная, куда временно помещается значение одного из элементов.

Просмотреть демонстрационный ролик

var А: array [1..1000] of integer;

n, p, i, j:integer;

begin

writeln(‘введите n’);

readln(n);

writeln(‘введите массив’);

for i:=1 to n do readln(A[i]);

for i:=1 to n-1 do

for j:=1 to n-1 do

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

p:=A[j];

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

A[j+1]:=p;

end;

for i:=1 to n do writeln(‘A[‘,i,’]=’,A[i]);

end.

Задание 2. Сортировка выбором. Сортировка по возрастанию. В массиве, начиная с первого выбирается наименьший элемент и ставится на первое место, затем, начиная со второго, эта процедура повторяется. И так, пока не отсортируется.

Просмотреть демонстрационный ролик

var i,j,n,nom,min:integer;

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

begin

writeln('введите n');

readln(n);

for i:=1 to n do A[i]:=random(100);

for i:=1 to n do writeln('A[',i,']=',A[i]);

for i:=1 to n-1 do begin

nom:=i;

min:=a[i];

for j:=i+1 to n do

if a[j]<min then begin

min:=a[j];

nom:=j;

end;

a[nom]:=a[i];

a[i]:=min;

end;

writeln('отсортированный массив:');

for i:=1 to n do writeln('A[',i,']=',A[i]);

end.

Задание 3. Составить программу для решения следующей задачи: Дан массив С(10). Сформируйте из него два массива А и В, предварительно определив их длину, включая в массив А четные положительные элементы, а в массив В — нечетные отрицательные.

var A,B,C:array[1..10] of integer;

i,j,k:integer;

begin

{ввод массива}

For i:=1 to 10 do C[i]:=random(100)-50;

{вывод массива}

writeln('массив С:');

For i:=1 to 10 do write('С[',i,']=',C[i],' ');

writeln;

{обработка массива}

j:=1; k:=1;

For i:=1 to 10 do begin

УСЛОВИЕ

{вывод массивов}

writeln('массив A:');

For i:=1 to j-1 do write('A[',i,']=',A[i],' ');

writeln;

writeln(массив B:');

For i:=1 to k-1 do write('B[',i,']=',B[i],' ');

writeln;

end.

Задание 4. Создать массив целых чисел из N=15 элементов. Заполнить его случайным образом, числами, в диапазоне от 0 до 40. Вывести его на экран. Отсортировать его методом простого обмена (“пузырька”) по невозрастанию (каждый следующий элемент меньше или равен предыдущему) и вывести отсортированный массив на экран.

Задание 5. В массиве из 15 элементов целого типа расставить по возрастанию только положительные