Уроки 34 - 36
§ 20. Обработка массивов

Содержание урока

Введение

Перестановка элементов массива

Реверс массива

Линейный поиск в массиве

Сортировка массивов

Выводы

Вопросы и задания

Практическая работа № 15 «Перестановка элементов массива»

Практическая работа № 16 «Линейный поиск в массиве»

Практическая работа № 17 «Сортировка»

Сортировка массивов

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

Возникает естественный вопрос: зачем сортировать данные? На него легко ответить, вспомнив, например, работу со словарями: сортировка слов по алфавиту облегчает поиск нужной информации.

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

Математики и программисты изобрели множество способов сортировки. В целом их можно разделить на две группы: 1) простые, но медленно работающие (на больших массивах), и 2) сложные, но быстрые.

Мы изучим один из простых методов, который называется методом выбора. Для примера будем рассматривать сортировку по возрастанию (неубыванию).

Предположим, что мы нашли минимальный элемент массива. Где он должен размещаться в отсортированном массиве?

Запишите в тетради фрагмент программы для поиска номера минимального элемента массива.

Для того чтобы поставить на место минимальный элемент, мы просто поменяем его местами с первым элементом массива.

Запишите в тетради фрагмент программы, который меняет местами элементы А[1] и A[nMin]. Используйте вспомогательную переменную с.

После того как мы установили на место первый (минимальный) элемент, находим минимальный из оставшихся и ставим его на второе место и т. д. Полный алгоритм записывается в виде вложенного цикла:

На первом шаге внешнего цикла значение i равно 1, и мы ставим на первое место минимальный элемент. На следующем шаге i = 2, мы ищем минимальный элемент среди всех, кроме первого, и т. д.

Обратите внимание, что внешний цикл выполняется N-1 раз (а не N). Этого достаточно, потому что если N-1 элементов стоят на своих местах, то последний тоже стоит на своём месте (другого свободного места для него нет).

Решение на языке Паскаль выглядит так:

Что получится, если внешний цикл (по переменной i) выполнить только 1 раз? Только 3 раза?

Следующая страница Выводы

Cкачать материалы урока