Сортировка – это упорядочивание набора однотипных данных по возрастанию или убыванию.
Простые методы сортировки можно разделить на три основные категории:
сортировка методом "пузырька" (простого обмена);
сортировка методом простого выбора (простой перебор);
сортировка методом простого включения (сдвиг-вставка, вставками, вставка и сдвиг).
Сортировка методом "пузырька" (простого обмена)
Самый известный алгоритм – пузырьковая сортировка (bubble sort, сортировка методом пузырька или просто сортировка пузырьком). Его популярность объясняется интересным названием и простотой самого алгоритма.
Алгоритм попарного сравнения элементов массива в литературе часто называют "методом пузырька", проводя аналогию с пузырьком, поднимающимся со дна бокала с газированной водой. По мере всплывания пузырек сталкивается с другими пузырьками и, сливаясь с ними, увеличивается в объеме. Чтобы аналогия стала очевидной, нужно считать, что элементы массива расположены вертикально друг над другом, и их нужно так упорядочить, чтобы они увеличивались сверху вниз.
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает – массив отсортирован. При проходе алгоритма элемент, стоящий не на своём месте, "всплывает" до нужной позиции
For i:=N downto 2 do
For j:=1 to i-1 do
If x[j]>x[j+1] then
Begin r:=x[j]; x[j]:=x[j+1]; x[j+1]:=r; end;
Writeln(‘Bubble Sort’);
For i:=1 to N do
Writeln(x[i]:4);
End.
Алгоритмы сортировки одномерного массива. Сортировка выбором максимального элемента.
Ищем Max элемент
Меняем местами с последним элементом
Повторяем операцию для всех элементов, кроме последнего
For j:=N downto 2 do begin
k:=1; for i:=1 to j do if x[k]<x[i] then k:=I;
R:=x[k]; x[k]:=x[j]; x[j]:=r;
End;
Алгоритмы сортировки одномерного массива. Сортировка простыми вставками. Сортировка бинарными вставками.
Сортировка простыми вставками.
При сортировке исходный массив разбивается на две части:
A[1], A[2],..., A[k-1] - отсортированную часть
A[k],...,A[n] - не отсортированную часть. s
На k - м шаге элемент A[k] включается в отсортированную часть, на соответствующее место. При этом часть элементов, больших A[k], (если таковые есть) сдвигаются на одну позицию правее, чтобы освободить место для элемента A[k]. Прежде чем производить сдвиг элементов необходимо сохранить значение A[k] во временной переменной B.
Так как массив из одного элемента можно считать отсортированным, алгоритм начинается с k=2.
for k:= 2 to n do
begin
B:= A[k]; j:= k-1;
while (A[j]> B) and (j>1) do
begin
A[j+1]:= A[j];
j:=j - 1;
end;
A[j+1]:= B;
end;
Бинарные
for j:=2 to N do
begin a:=1;b:=j; repeat
s:=(a+b) div 2;
If x[s]<x[j] then a:=s+1;else b:=s;
Until a=b;
r:=x[j];
for m:=j downto a+1 do x[m]:=x[m-1];
x[a]:=r;
end;
14.Алгоритмы численного интегрирования. Формула прямоугольников.
Var eps, r, r2,d:real;
N:integer;
Function f(x:real):real;
Begin
F:=sqr(arctan(x));
End;
Function Integral (a,b:real,n:integer):real;
Var h, s: real; i:integer;
Begin
h:=(b-a)/ n;
s:=0;
for i:=0 to n-1 do
s:=F(a+i*h)*h+s;
integral:=s;
end;
begin
readln(eps);n:=10;
r:= integral(1,2,n);
repeat
n:=n*2;
R2:=integral(1,2,n);
N:=abs(r-r2);
R:=r2;
Until n<=eps;
Writeln(r,n);
End.
15. Алгоритмы численного интегрирования. Алгоритм нахождения корня нелинейного уравнения.
F(x)=tgx-x=0
Var a,b,eps:real;
Function F(x:real):real;
Begin
F:=sin(x)/cos(x)-x;
End;
Function root (a,b,eps:real):real;
Var c:real; found: boolean;
Begin
Found:=false;
Repeat
C:=(a+b)/2;
If F(c)= 0 then found:=true else If F(c) * F(a) >0 then a:=c else b:=c;
Until found or ((b-a)<eps);
If found then root:=c else root:=(a+b)/2;
End;
16. Тип строковый. Процедуры и функции для работы со строками.
1. Значениями строкового типа (string) в Паскале являются последовательности символов длиной от 0 (пустая строка) до 255 символов. Можно описать строку, предельная длина которой меньше 255, эту длину в квадратных скобках. Примеры описания строк:
2. var
3. s1, s2: string; {Обычные строки длиной до 255 символов}
4. name: string[20]; {Строка длиной не более 20 символов}
5. group: string[3]; {Строка длиной не более 3 символов}
6. txt: array [0..99] of string[80]; {Массив из 100 строк
7. длиной не более 80 символов}
8. Строку можно рассматривать как массив символов, то есть обращаться из программы к отдельным символам строки:
9. s1[2] – второй символ строки s1;
s2[i] – i-й символ строки s2;
txt[3][10] – десятый символ третий строки из массива txt.
10. Нумерация символов в строке начинается с 1. В памяти строка занимает на 1 байт больше, чем это необходимо для хранения символов. Самый первый (нулевой) байт хранит длину строки. Поэтому присваивание вида: s1[10]:=’x’ приведет к желаемому результату, только если в строке десять или больше символов. Та же операция по отношению к более короткой строке не приведет к ее изменению.
11. Строки можно считывать и печатать обычными процедурами ввода/вывода: read, readln, write, writeln.
12. Для строк определена операция сложения. При этом складываемые строки объединяются в одну. Например:
13. s1:='abra';
14. s1[1]:=Upcase(s1[1]);
15. s2:='kadabra';
16. s1:=s1+' '+s2+'!';
17. writeln(s1);
18. Здесь первый символ строки s1 (строчная «a») был заменен на прописную «A». Затем к этой строке был добавлен пробел и строка s2. В итоге программа напечатает строку ‘Abra kadabra!’.
19. Переменную или выражение типа Char также можно прибавить к строке.
20. Отдельные символы строки (s1[1], s1[2] и т.д.) можно рассматривать как переменные типа Char. В примере мы воспользовались этим, заменив строчную букву заглавной.
21. Строка может быть пустой, то есть вовсе не содержать символов и иметь нулевую длину. Такая строка задается как две одинарные кавычки, между которым ничего нет:
22. S:= '';
23. Обратите внимание, что «ничего» в данном случае, значит совсем ничего. Часто, пытаясь задать пустую строку, ставят между кавычками пробел, что неправильно.
24. Некоторые процедуры и функции для работы со строками:
25. 1) Length(s) – получение длины строки.
26. 2) Pos(Substr, S) – функция, в качестве результата выдающая номер символа, начиная с которого в строке s начинается подстрока Substr. Если S не содержит подстроки Substr, то результат будет равен 0.
Например: Pos(‘ ‘, s) – найдет номер позиции, на которой в строке s находится пробел. Pos(‘Ivan’, s) найдет имя ‘Ivan’.
27. 3) Copy(s, i, n) – функция, выделяющая из строки s подстроку, начиная с символа за номером i, и включающую n символов. Например:
28. s1:='abracadabra';
29. s1:=Copy(s1, 5, 6);
30. В результате строка s1 будет равна ‘cadabr’.
31. 4) Delete(s, i,n) – процедура, удаляющая из строки s n символов, начиная с символа с номером i.
32. 5) val(s, n, code) – процедура, переводящая строку s в число n. Если преобразование произошло успешно, то code будет равна 0, если нет, то в эту переменную будет записан код ошибки.
33. 6) str(n, s) – процедура, переводящая число n в строку s.
34. 7) Для преобразования чисел в строки и обратно также удобно пользоваться функциями:
35. StrToInt(s) — функция, возвращающая целочисленное значение, записанное в строке s.
36. StrToFloat(s) — функция, возвращающая целочисленное значение, записанное в строке s.
37. IntToStr(x) — функция, возвращающая строковое значение, содержащее целое число x.
38. FloatToStr(x) — функция, возвращающая строковое значение, содержащее вещественное число x.
39. Заметим, что данные функции не будут работать, если вы программируете в среде Borland Pascal.