Информатика

Тема: Основы объектно-ориентированного программирования

Урок: Сортировка и поиск данных в массиве

 

1. Поиск максимального элемента в массиве

Задача поиска и сортировки является весьма и весьма практичной. Более того, эта задача настолько популярна, что, наверное, имеет самое большое и разнообразное количество решений, которое только можно себе представить. Дело в том, что в любой базе данных очень часто необходимо найти тот или иной элемент или же упорядочить его. Поэтому задача упорядочивания и поиска необходимого элемента является весьма популярной. Вместе с тем популярность естественно привела к большому количеству различных решений. С некоторыми из них мы сегодня и познакомимся.

Для сортировки массива или поиска какого-то элемента массива очень часто используются операторы цикла. Давайте с вами рассмотрим пример программы, в которой оператор цикла используется для поиска максимального элемента массива.

Рис. 1

Итак, для начала определим, что arraytype – это у нас массив из пяти элементов и каждый элемент является целым числом (рис. 1).

Рис. 2

2. Варианты заполнения массива значениями

В этом блоке мы используем оператор цикла for, где на каждой итерации мы просим с помощью команды writeln ввести i-ый элемент, а потом сохраняем этот элемент на i-ое место в нашем массиве. Таким образом мы заполняем массив (рис. 2).

Рис. 3

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

Давайте посмотрим, как будет работать данная программа на практике.

Рис. 4

Мы можем увидеть, что мы поочередно ввели 5 целых чисел, и программа правильно нашла максимальный элемент (рис. 4).

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

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

3. Методы сортировок

Рассмотрим два наиболее простых и наиболее известных способа сортировки. Это линейная сортировка и пузырьковая.

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

Одну из перестановок можно увидеть на данной картинке (рис. 5).

 

Рис. 5

Мы можем увидеть, что мы выбираем второй элемент со значением 3 и двигаемся вдоль массива, пока не найдем элемент с меньшим значением. В данной ситуации таким элементом будет 5-ый элемент со значением 2. Как только мы нашли необходимый элемент, то меняем их местами, что и показано на двух картинках.

Второй метод – это метод пузырька или пузырьковая сортировка. Она является более быстрой, так как учитывает текущую упорядоченность массива. Увеличение скорости выполнения достигается за счет уменьшения количества операций сравнения и перестановки. Таким образом, при больших размерах массива это преимущество может оказаться весьма и весьма важным. Итак, рассмотрим, в чем же заключается суть этой сортировки.

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

Посмотрим, как же работает данная сортировка на примере одной итерации цикла.

Вот наш исходный массив (рис. 6)

Рис. 6

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

Рис. 7

Затем, берем следующий элемент (т. е. второй) и сравниваем его с соседним, так как 4 меньше 5, то ничего не делаем, а переходим к следующему элементу. В данном случае получается, что 5 больше 1, следует нам нужно поменять их местами (рис. 8).

Рис. 8

И на последнем этапе первой итерации цикла сравниваем 5-ку с 2-кой, тоже необходима перестановка, что мы и выполняем. (рис. 9)

Рис. 9

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

4. Программная реализация вышеописанных методов

Давайте теперь рассмотрим компьютерную реализацию рассмотренных нами методов и сравним их эффективность.

Вот текст программы линейной сортировки (рис. 10).

Рис. 10

Т. е. вначале мы вводим массив с клавиатуры, а далее выполняем на языке программирования все те действия, которые мы обсуждали ранее. Отметим, что переменная j в цикле всегда на 1 больше, чем i. Это сделано, чтобы мы могли сравнивать соседние элементы, что мы и делаем в условном операторе if. В конце мы благополучно выводим отсортированный массив на экран.

Теперь посмотрим на программу, которая реализует пузырьковый метод сортировки (рис. 11).

Рис. 11

Отметим, что здесь массив заполняется случайными числами, выполняется стандартная функция random. Также мы используем логическую переменную switch, которая несет в себе информацию про то, были ли выполнены перестановки в текущей итерации. Ну и еще одним основным отличием от предыдущей программы является использование цикла с постусловием repeat, который будет выполняться, пока переменная switch не примет значение false. Остальные же действия полностью соответствуют вышеописанному алгоритму.

Теперь проверим, будут ли работать наши программы на компьютере. Для этого запустим их.

Вот результат выполнения первой программы, т. е. линейной сортировки (рис. 12).

Рис. 12

Мы ввели пять чисел и видим, что программа правильно отсортировала данные.

Вот результат выполнения второй программы (рис. 13).

Рис. 13

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

5. Заключение

Список литературы

1. Угринович Н.Д. Информатика-9. – М.: БИНОМ. Лаборатория знаний, 2012.
2. Гейн А.Г., Юнерман Н.А. Информатика-9. – М.: Просвещение, 2012.
3. Соловьёва Л.Ф. Информатика и ИКТ. Учебник для 9 класса. – СПб.: БХВ-Петербург, 2007.

 

Дополнительные рекомендованные ссылки на ресурсы сети Интернет

1. Программирование для школьников (Источник).
2. Википедия (Источник).
3. Язык Паскаль (Источник).

 

Домашнее задание

1. Каким способом осуществляется обычный поиск в одномерном массиве?
2. Какая сортировка из рассмотренных является более быстрой?
3. Какой оператор соответствует циклу с пост условием?
4. Являются ли числа, сгенерированные функцией random, случайными?