TURBO PASCAL:Учебное пособие. Терёхин В.В. - 63 стр.

которых изначально определено отношение порядка. Во-
прос о возрастании или убывании упорядоченного массива для
нас не принципиален. Как правило, программы, сортирующие
массив по возрастанию, легко изменяются для сортировки по
убыванию.
        Существует множество алгоритмов сортировки (пу-
зырьковая сортировка, сортировка по дереву, быстрая сорти-
ровка, сортировка слиянием, сортировка Шелла и т. д.), они
имеют большую практическую значимость, являются фунда-
ментальными в некоторых областях информатики.
        В данном пособии мы приводим не самый лучший, но,
безусловно, самый распространенный и очень понятный алго-
ритм пузырьковой сортировки.
        Название «Пузырьковая сортировка» происходит от об-
разной интерпретации, по которой алгоритм заставляет «лег-
кие» элементы мало-помалу всплывать на «поверхность».
        Суть алгоритма такова. Начиная с первого, сравнивают-
ся два соседних элемента массива A[i] и A[i+l], если A[i] >
A[i+1], то элементы меняются местами. В первый раз мы про-
ходим массив начиная с индекса 1, до индекса n - 1, во второй -
с 1 до n - 2 и т. д. Любой массив будет отсортирован за n про-
ходов. Таким образом, порядок сложности данного алгоритма
(максимальное количество операций проверок и перестановок
                                        2
элементов массива) пропорционален n /2, что характерно для
многих алгоритмов сортировки, хотя массив может быть от-
сортирован уже после первого прохода. Наиболее очевидное
усовершенствование данного алгоритма состоит в том, что
можно следить за перестановками: если при очередном прохо-
де не было перестановок, значит массив уже упорядочен и тре-
буется завершить сортировку.

program p20;
const
   n= 10;
var
                                                             63