Уроки 58 - 61
Сортировка массива
(§ 21. Сортировка массива)
Составление программы на Паскале сортировки массива
Тест по теме «Программное управление работой компьютера»
Содержание урока
§ 21. Сортировка массива. Алгоритм сортировки методом пузырька
§ 21. Сортировка массива. Программа на Паскале сортировки методом пузырька
Компьютерный практикум ЦОР. Сортировка массива (Задание 1 - 4)
Компьютерный практикум ЦОР. Сортировка массива (Задание 5 - 8)
Тест по теме «Программное управление работой компьютера»
§ 21. Сортировка массива
Программа на Паскале сортировки методом пузырька
Теперь запишем программу на Паскале. Но мы ее немного усложним по сравнению с построенным алгоритмом. По условию исходной задачи нам нужно получить список команд в порядке занятых ими мест и число очков, полученных каждой командой. Следовательно, сортировать нужно не только массив В, но и массив Team. Делается это очень просто: в массиве Team параллельно с массивом В производятся те же самые перестановки. В конце работы программы на экран выводятся одновременно элементы обоих отсортированных массивов.
Поясним новые средства Паскаля, которые применены в этой программе. Обмен значениями между элементами строкового массива Team должен происходить через переменную строкового типа. Для этого в программе используется переменная St.
Вывод результатов на экран организован так, чтобы на экране номера мест, занятых командами, названия команд и набранные очки выводились в три ровных столбца. Названия разных команд имеют разную длину. Самое длинное название у команды ТОРПЕДО-МЕТАЛЛУРГ состоит из 17 символов. Для выравнивания длин строк каждое название дополняется пробелами до 18 символов. Число добавляемых пробелов вычисляется так:
18-length(Team[I])
Здесь length ( ) — это стандартная функция, вычисляющая длину строки (число символов), указанной в скобках. Например, для ЦСКА длина строки равна 4, а для ТОРПЕДО-МЕТАЛЛУРГ длина равна 17. Значит, к ЦСКА добавится 14 пробелов, а к ТОРПЕДО-МЕТАЛЛУРГ — 1 пробел.
В операторе Team [I] : = Team [I] + ' '; используется операция «+» присоединения символов. В данном случае присоединяется пробел. К строке Team [l] добавится столько пробелов, сколько раз повторится присоединение. После этого по команде
Writeln(1:2,' ',Team[I]:18, B[I]:2)
в ровные колонки выведутся места, названия команд и очки. Результаты будут иметь на экране следующий вид:
Демонстрации к уроку
1. Демонстрация на тему:
"Сортировка методом выбора"
2. Демонстрация на тему:
"Сортировка методом обмена"
3. Демонстрация на тему:
"Сортировка методом обмена"
(Улучшенный алгоритм)
Коротко о главном
Метод пузырька — алгоритм сортировки числового массива.
Структура алгоритма метода пузырька — два вложенных цикла с переменной длиной внутреннего цикла.
length() — функция определения длины строковой переменной.
В Паскале существует операция присоединения строк. Ее знак — «+».
Вопросы и задания
1. Как пояснить название метода сортировки массива — «метод пузырька»?
2. Сколько проходов с перестановками элементов потребуется при сортировке массива из 100 чисел?
3. Введите в компьютер программу Premier_liga_2.
а) Выполните ее, получите результаты. Сравните с результатами, приведенными в параграфе.
б) Внесите изменения в программу для того, чтобы получить список в обратном порядке (по возрастанию очков). Выполните программу.
в) Возможно, что массив окажется отсортированным до завершения всех проходов. В таком случае число повторений внешнего цикла можно сократить, и программа будет выполняться быстрее. Попробуйте усовершенствовать приведенную программу с учетом этого факта. Проверьте результат на тестах.
4. Если несколько команд набрали одинаковое количество очков, то места между ними распределяются по разнице забитых и пропущенных мячей: чем разница больше, тем место выше. Попробуйте усовершенствовать программу, учитывая это правило. Для этого в программу надо добавить массив с разницами мячей. Придумайте тест, на котором можно проверить работу программы.
5. Условие то же, что и в предыдущем задании. Но в качестве исходных данных вводится еще два массива: с числом забитых и пропущенных мячей каждой командой.
