mozok.click » Інформатика » Алгоритмы сортировки элементов массива
Інформація про новину
  • Переглядів: 2439
  • Автор: admin
  • Дата: 2-10-2017, 17:22
2-10-2017, 17:22

Алгоритмы сортировки элементов массива

Категорія: Інформатика

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

Сортировка элементов массива — это упорядочивание их по некоторому признаку.

Рассмотрим два простейших метода сортировки массива. Пусть нужно упорядочить массив X:

Сортировка выбором максимального элемента

Этот метод основан на том, что при каждом проходе цикла пересматривается часть массива длиной К элементов. Например, для массива X[1..10] при первом проходе К = 10.

Алгоритм сортировки по возрастанию (рис. 36.1):

• найти максимальный из элементов X[1]..X[10];

• максимальный элемент поменять местами с X[10];

• найти максимальный элемент из части массива X[1]..X[9];

• максимальный элемент из этой части поменять местами с X[9];

<...>

• максимальный элемент из части массива X[1]..X[2] поменять местами

с X[2].



Вид массива X[1 ..10] на каждом шагу сортировки по неубыванию выбором максимального элемента изображен на рис. 36.1.

Сортировка обменом (метод пузырька)

Метод пузырька основан на сравнении и перестановке соседних чисел. Алгоритм сортировки по возрастанию:

1) последовательно сравнивать пары соседних элементов X[i] i X[i + 1] (i:1..N - 1), и, если X[i] > X[i + 1], то поменять их местами и логической переменной Prap задать значение True. В результате первого просмотра элементов массива на N-м месте будет самый большой из всех элементов, то есть он, как пузырек, «всплывет» вверх;

2) выполнить те же действия с элементами от 1 до (N - 2): на (N - 1)-м месте появится наибольший среди (N - 1) элементов и т. д.

Переменная Prap: Boolean выполняет роль

флажка. Она получает значение True при условии, что состоялась хотя бы одна перестановка соседних элементов. Если значение Prap не изменилось, это означает, что элементы массива уже упорядочены и последующий просмотр последовательности значений не требуется (рис. 36.2):

Дан массив А[1..10], значения которого заданы случайным образом и находятся в диапазоне от 0 до 19. Упорядочить массив по убыванию (А[1] > А[2] > ... > А[10]) методом пузырька.


Для пошагового анализа хода сортировки добавим на форму компонент StringGrid и настроим его свойства следующим образом:

Вывод заголовков столбцов запрограммируем в процедуре обработки события OnCreate (см. § 35). Алгоритм сортировки массива реализуем в процедуре обработки события onclick командной кнопки Button1.

Описание величин. Опишем переменные, необходимые для реализации алгоритма:

Упорядочение массива A[1..10] по убыванию методом пузырька.

К телу цикла Repeat добавим операторы для вывода элементов массива А на каждом шагу сортировки:

Проверка работы программы. Запустим программу на выполнение и проанализируем ход сортировки.

Для разных наборов значений элементов массива А может понадобиться разное количество шагов сортировки (на рис. 36.3 — 7 шагов).

Вопросы для самопроверки

1. В чем сущность сортировки массива методом выбора максимального элемента?

2. В чем сущность сортировки массива методом пузырька?

3. На каком месте в массиве может находиться его наибольший элемент, если массив не упорядочен?

4. На каком месте в массиве может находиться его наименьший элемент, если массив упорядочен по возрастанию; по убыванию?

5. Для каждой пары соседних элементов массива А выполняется операция S := S + Byte (A [i]> = A [i + 1]); { Byte (True) = 1; Byte (False) = 0 } Начальное значение S равно 0. Определите, чему равно конечное значение S, если входной массив:

а) был упорядочен по возрастанию;

б) был упорядочен по убыванию;

в) не был упорядочен.

6. Дан список результатов забега на 100 м восьми спортсменов. Составьте программу для определения трех лучших результатов.


Упражнение 36

Дан одномерный массив из 6 элементов. Определить, является ли массив упорядоченным по возрастанию или убыванию. Если массив не упорядочен, вывести ответ «Неупорядоченная последовательность». Блок-схема алгоритма решения задачи приведена на рис. 1.

1) Создайте новый проект. Измените значение свойства Caption формы, добавьте на форму компонент Label для вывода ответа на вопрос задачи и компоненты Button согласно рис. 2.

2) Разместите на форме компонент StringGrid и настройте его свойства следующим образом:

В процедуре обработки события OnCreate для формы запрограммируйте вывод индексов элементов массива в зафиксированную строку заголовков столбцов.

3) Опишите массив A: array[1..6] of Integer как глобальный. В процедуре обработки события onclick для кнопки Ввести значение запрограммируйте ввод элементов массива с клавиатуры в ходе выполнения программы.

4) Создайте процедуру обработки события onclick для кнопки Упорядочен ли массив?. Опишите переменные, которые будут необходимы для решения задачи:

var i: Integer; Prap: Boolean;

Проверьте, является ли массив упорядоченным по неубыванию. Алгоритм решения задачи: перебрать все элементы со второго до последнего. Если текущий элемент меньше предыдущего, то переменной Prap присвоить значение False. Если после просмотра массива эта переменная имеет значение False, это означает, что последовательность не была неубывающей.

5) Пользуясь рис. 1, добавьте к оператору If, который проверяет состояние переменной Prap, ветвь Else для проверки последовательности на невозрастание.

6) Проверьте работу программы для последовательности, упорядоченной по неубыванию; по невозрастанию; неупорядоченной последовательности. Сохраните проект в папке Упражнение 36. Завершите работу за компьютером.

Компьютерное тестирование

Выполните тестовое задание 36 с автоматической проверкой

на сайте interactive.ranok.com.ua.

Практическая работа 12

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

Задание: создать проект для решения задачи.

Дана таблица количества осадков в течение года по месяцам:

Определить:

а) количество осадков за год;

б) месяц, в котором количество осадков было наименьшим;

в) месяц, в котором количество осадков было наибольшим;

г) месяцы, в которые количество осадков было меньше 40, и количество таких месяцев.

Оборудование: компьютер с установленной средой программирования Lazarus.

Ход работы

Во время работы за компьютером соблюдайте правила безопасности.

I. Расположение элементов управления на форме

1. Создайте новый проект. Разработайте интерфейс программы (см. рисунок). Поле списка ListBoxI предназначено для вывода ответов.

2. Настройте свойства элементов управления (см. рисунок).

II. Разработка программного кода

3. Опишите массивы-константы для сохранения названий месяцев и количества осадков в интерфейсном блоке как глобальные:

4. В процедуре обработки события OnCreate для формы запрограммируйте вывод названий месяцев в строку заголовков столбцов, а значения элементов массива количества осадков — в первую строку таблицы.

5. Создайте процедуру обработки события onclick для командной кнопки Количество осадков за год, мм, пользуясь алгоритмом нахождения суммы элементов массива.

6. Создайте процедуру обработки события onclick для командной кнопки Самый сухой месяц, пользуясь алгоритмом определения наименьшего элемента массива.

7. Создайте процедуру обработки события onclick для командной кнопки Самый влажный месяц, пользуясь алгоритмом определения наибольшего элемента массива.

8. Создайте процедуру обработки события для кнопки месяцы, в которые количество осадков меньше 40 мм, пользуясь алгоритмом определения количества элементов с заданным свойством.

9. Добавьте к процедуре обработки события для кнопки месяцы, в которые количество осадков меньше 40 мм операторы для вычисления К — количества элементов массива mas, удовлетворяющих условию, и вывода значения К в поле списка ListBox1.

10. Добавьте к процедуре обработки события для кнопки Количество осадков за год, мм операторы для вычисления среднего арифметического элементов массива mas и вывода этого значения в поле списка ListBox1.

III. Тестирование проекта

11. Проверьте работу программы.

12. Сохраните проект в папке Практическая работа 12. Завершите работу за компьютером.

Сделайте вывод: как применять типовые алгоритмы обработки одномерных массивов для решения задач.

 

Это материал из учебника Информатика 9 класс Бондаренко

 






^