x := aj-1 aj-1 := aj aj := x

Конец сортировки

Рис. 9. Алгоритм сортировки методом

«пузырьков»

aj-1 >aj

–

+

i:=1,n–1,1

i:=n,i+1,–1

Начало сортировки

Сравнив операторы, которые реализуют данные алгоритмические структуры, можно сделать вывод о том, что на известных языках программирования написание этих операторов почти одинаково.

5.4. Важнейшие невычислительные алгоритмы (поиск и сортировка)

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

по возрастанию или убыванию значений какого-либо признака.

В общем случае задача сортировки ставится так. Пусть имеется набор элементов а1, а2, …, аn, где аi могут быть числами, символами, строками и т.д.

Сортировка есть перестановка этих элементов в массив ai1 ,ai2 ,...,ain , где при некоторой упорядочивающей функции f выполняется отношение f(ai1 ) ≤ f(ai2 )

≤ … ≤ f(ain ). Обычно упорядочивающая функция не хранится по какому-либо

правилу, а хранится как явная компонента (т.е. поле) каждого элемента. Ее значение называют ключом элемента.

Имеется много различных алгоритмов сортировки массивов. Самым простым и самым популярным является метод «пузырьков».

Данный алгоритм основан на последовательных просмотрах от конца к началу и в сравнении и смене мест пары соседних элементов. Этот процесс продолжается до тех пор, пока не будут упорядочены все элементы. При

каждом просмотре массива наименьший элемент оставшейся последовательности сдвигается к левому концу

массива. Алгоритм сортировки методом

пузырьков имеет следующий вид (рис. 9).

В алгоритме массив просматривается от конца к началу, и если в n-

мерном массиве an–1 > an элементы меняются местами, далее an–2 сравнивается с an–1 и т.д., пока самый малень-

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

— это прямой метод сортировки. Он достаточно длительный, требует порядка n2 сравнений. Тогда как

хорошие методы сортировки требуют порядка n ln n сравнений.

48

Этот алгоритм можно улучшить: а именно, если в ходе очередного просмотра не было перестановок, то сортировку завершить. Улучшенный алгоритм называется модифицированным методом «пузырьков».

Пусть р — признак наличия или отсутствия перестановки: p=false — нет перестановки, p=true — есть. Заменим внешний цикл с параметром на цикл с постусловием, т.е. первый просмотр обязателен. Условием окончания работы алгоритма является отсутствие перестановок во внутреннем цикле или i=n–1 — выполнены все просмотры.

Задача поиска — одна из наиболее встречающихся в информатике. Поиск

Начало сортировки
i:=0	]- - - - - i – номер просмотра
i:=i+1
p:=false	]- - - - - перестановки нет
j:=n,i+1,-1
_	+
Kaj-1 > Kaj
	x := aj-1
	aj-1 := aj		]- - - - - перестановка
	a := x
	p:= true		]- - - - - перестановка есть
_		]- - - - - условие окончания цикла
p = false или i = n - 1
+
Конец сортировки

Рис. 10. Алгоритм сортировки модифицированным методом «пузырьков»

производится в последовательности однотипных данных и заключается в выявлении одного или нескольких данных, обладающих некоторым свойством К. В общем виде задача поиска ставится так. Пусть имеется набор элементов а1, а2, …, аn с ключами Kа1, Kа2, …, Kаn и пусть имеется некоторое значение К. Простейшие задачи поиска можно сформулировать так:

49

1.Требуется определить по крайней мере один элемент, имеющий К своим свойством.

2.Требуется определить все элементы, имеющие К своим свойством.

Кназывают аргументом поиска или запросом. Поиск по запросу К может быть безрезультативным.

Иногда поиск организуется не по совпадению со значением К, а по выполнению некоторых условий, например, поиск по интервалу значений.

Линейный поиск — это простой последовательный просмотр элементов массива с проверкой условия К. Условиями окончания поиска являются:

1.Элемент ai, обладающий свойством К, найден.

2.Весь массив просмотрен, но элемент, обладающий свойством К, не найден.

Ниже приведен алгоритм поиска первого элемента массива, обладающего свойством К (рис. 11). Здесь р — признак того, обладает или нет элемент массива свойством К: р = true — есть элемент со свойством К, р= false — нет элемента со свойством К.

							Начало поиска
								p:=false
								i := 0
								i := i + 1
	+						_
								Kai=K
		p := true
	_
								р или i=n
							+
+							_
								p
Есть элемент со								Нет элемента со
свойством К								свойством К

Конец поиска

Рис. 11. Линейный поиск первого элемента массива, обладающего свойством К

50

На рисунке 12 приведен алгоритм поиска всех элементов, обладающих
свойством К.
Начало поиска
p:=false
i := 1, n, 1
+	_
Kai	= K
Вывод i, ai
p:=true
+	_
not(p)
Нет элементов
со свойством К

Конец поиска

Рис. 12. Линейный поиск всех элементов со свойством К

5.5. Понятие о языках программирования

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

Любой язык, в том числе и язык программирования, имеет три составляющие: алфавит, синтаксис и семантику.

Алфавит — это упорядоченное конечное множество взаимно различных символов (букв, цифр, специальных и служебных символов), допускаемых для составления текста программы на этом языке.

51