Укрупненная структура программы
Сортировка прямым выбором
Первая сортировка, которую я хочу посмотреть это сортировка выбором. В чем же её суть, рассмотрим на следующем примере.
Есть массив из четырех чисел наша задача отсортировать его по возрастанию.
Будем делать следующим образом: находим в этом массиве за первый цикл максимум, и меняем максимум и последний элемент.
После чего мы точно уверены, что на последнем элементе находится максимальный элемент. Поэтому в следующем цикле наша задача рассмотреть уже следующий массив.
Который меньше, чем наш на один элемент. И повторить операцию поиска и замены максимума на последней элемент.
Таким образом получится следующая картина.
Как видно количество операций поиска максимума и замены его на последний элемент меньше на единицу, чем количество элементов в массиве.
А теперь учтем все, что было сказано выше и посмотрим на нашу программу.
program fff;
const
n=10; {Количество элементов массива}
var
i,j,k,max,im:integer;
a: array [1..10] of integer;
BEGIN
for i:=1 to n do
a[i]:=random(10); {Ввод массива случайным образом от о до 9}
k:=n;
for i:=1 to n-1 do {Количество операций по поиску и замены нашего максимума}
begin
max:=a[1];
im:=1;
for j:=1 to k do
if a[j]>max then {Поиск максимального элемента}
begin
max:=a[j]; { Если нашли мы наш максимум}
im:=j; {то запоминаем его, и его номер номер}
end;
a[im]:=a[k]; {Меняем максимум на последний элемент}
a[k]:=max ; {последний на максимум}
dec(k); { Теперь мы уверены, что на последнем элементе находится максимум поэтому следующий цикл, нужно последний элемент не трогать}
end;
for i:=1 to n do {Вывод элементов на экран}
write(a[i]:4);
writeln; {Для удобство просмотра программы}
end.
Блок схема Сортировки прямым выбором
Сортировка пузырьком
Следующая сортировка называется сортировка вставками. Рассмотрим следующий массив для примера.
Мы будем последовательно сортировать элементы в группах. Потом вставлять в нашу группу новые элементы в то место, какое соответствует их значению.
Рассмотрим наш массив. Он состоит из четырех элементов. Создадим первую группу и возьмем в нее один первый элемент. Один элемент в группе отсортирован всегда.
После этого добавим в нашу группу следующий элемент это 1 и определим его место.
Получается новая группа отсортирована, добавляем туда новый элемент и находим его место в группе.
И наконец последняя добавляем последний элемент.
А теперь используя эту идею, напишем программу.
program fff;
const
n=10; {Количество элементов массива}
var
i,j,x:integer;
a:array [0..10] of integer;
BEGIN
for i:=1 to n do
a[i]:=random(10); {Ввод массива случайным образом от о до 9}
a[0]:=-maxint-1; { Барьерный элемент, который равен самому маленькому числу для того чтоб не было зацикливания }
for i:=2 to n do {Начинаем со второго т.к. в первой группе один элемент по умолчанию отсортирован}
begin
x:=a[i]; {Элемент который мы будем добавлять в нашу группу}
j:=i-1; {Первый элемент нашей группы с которым мы будем сравнивать наш элемент}
while (x<a[j]) do {Если наш элемент больше чем посл. элемент в отсортированой группе то его мы оставим на своем месте}
begin
a[j+1]:=a[j]; {Если наш элемент меньше чем посл. то меняем его с посл местами}
dec(j); {Потом если наш элемент меньше чем предпосл. то меняем его с предпосл местами и т.д.}
end;
a[j+1]:=x;
end;
for i:=1 to n do {Вывод элементов на экран}
write(a[i]:4);
writeln; {Для удобство просмотра программы}
end.
Следующая сортировка называется сортировка пузырьком. В ней сравнивается два соседних элемента и если левый больше правого они меняются местами. Давайте рассмотрим действие данного алгоритма на примере.
Сравниваем первый и второй элементы и т.к.левый больше правого они меняются местами.
Теперь сравниваем второй элемент с третьим и т.к.левый больше правого они меняются местами.
Теперь сравниваем третий элемент с четвертым и т.к.левый больше правого они меняются местами.
Четверка как бы всплывает вверх поэтому алгоритм и называется сортировка пузырьком.
После этого смотрим на единицу, т.к. она меньше чем тройка мы её не трогаем. Переходим к тройке и сравниваем её с двойкой меняем местами.
После этого сравниваем тройку с четверткой и ничего не меняем. После этого на всякий случай еще раз пройдемся и сравним элементы начиная с единицы и видим, что теперь массив отсортирован.
Реализация алгоритма на на Паскале выглядит следующим образом:
program fff;
const
n=10; {Количество элементов массива}
var
i,c:integer;
flag:boolean;
a:array [0..n] of integer;
BEGIN
for i:=1 to n do
a[i]:=random(10); {Ввод массива случайным образом от о до 9}
repeat
flag:=true; {Наше условие, что массив отсортирован}
for i:=1 to n-1 do {Заканчиваем цикл на предпосл. элементе т.к он сравнивается в цикле с посл.}
if a[i]>a[i+1] then {сравнение двух соседних элементов}
begin
c:=a[i];
a[i]:=a[i+1]; {Если они не отсортированы то меняем их местами}
a[i+1]:=c;
flag:=false; {Если были неотсортированые элементы проходим цикл еще раз иначе массив отсортирован}
end;
until flag=true;
for i:=1 to n do {Вывод элементов на экран}
write(a[i]:4);
writeln; {Для удобство просмотра програмы}
end.