Сортировка массивов
Сортировкой или упорядочением массива называется расположение его элементов по возрастанию (или убыванию). Если не все элементы различны, то надо говорить о неубывающем (или невозрастающем) порядке.
Вообще говоря, это большая и сложная тема, в которой известно много различных алгоритмов. Критерии оценки эффективности этих алгоритмов могут включать следующие параметры:
-
количество шагов алгоритма, необходимых для упорядочения;
-
количество сравнений элементов;
-
количество перестановок, выполняемых при сортировке.
Мы рассмотрим только одну простейшую схему сортировки - Метод "пузырька".
"Пузырьковая" сортировка- простой, не оптимальный, но самый понятный алгоритм. Представьте, что мы построились случайным образом в шеренгу и нам надо перестроиться по росту, меняя пары людей между собой.
Пойдем вдоль шеренги и найдем самого высокого(сортировка по убыванию) и поменяем его с первым. потом пойдем от второго , найдем самого высокого среди оставшихся и тоже поменяем. Можете потренироваться на людях или предметах чтобы было понятно.:)
В итоге наша шеренга буде такой, о которой мечтает физрук на уроке физкультуры.
Что нужно знать для того, чтобы запрограммировать сортировку?
1. как поменять местами 2 переменных через третью.
2. Как работает цикл
3. как ввести и вывести массив данных
Метод "пузырька"
По-видимому, самым простым методом сортировки является так называемый метод "пузырька". Чтобы уяснить его идею, представьте , что массив (таблица) расположен вертикально. Элементы с большим значением всплывают вверх наподобие больших пузырьков. При первом проходе вдоль массива, начиная проход "снизу", берется первый элемент и поочередно сравнивается с последующими. При этом:
-
если встречается более "легкий" (с меньшим значением) элемент, то они меняются местами;
-
при встрече с более "тяжелым" элементом, последний становится "эталоном" для сравнения, и все следующие сравниваются с ним .
В результате наибольший элемент оказывается в самом верху массива.
Во время второго прохода вдоль массива находится второй по величине элемент, который помещается под элементом, найденным при первом проходе, т.е на вторую сверху позицию, и т.д.
Заметим, что при втором и последующих проходах, нет необходимости рассматривать ранее "всплывшие" элементы, т.к. они заведомо больше оставшихся. Другими словами, во время j-го прохода не проверяются элементы, стоящие на позициях выше j.
Сортировка по возрастанию
var
i,j,c:integer;
mas:array[1..10] of integer;
begin
{заполнение массива случайными числами}
for i:=1 to 10 do mas[i]:=random(100);
{сортировака массива}
for i:=1 to 10 do
for j:=1 to 10 do
if mas[i]mas[j] then
begin
c:=mas[i];
mas[i]:=mas[j];
mas[j]:=c;
end;
{вывод массива}
for i:=1 to 10 do write(mas[i], ' ');
end.
К данной программе составить блок-схему, выполнить программу на компьютере результат записать в тетрадь
Задание .
1.Выполнить сортировку данного массива по убыванию.
2. Выполнить сортировку только четных элементов массива (нечетные элементы остаются на своих местах)