Конспект урока: Одномерные массивы. Сортировка массива

• Введение в тему
• Сортировка массива

• научиться осуществлять сортировку данных в массиве

• Как найти сумму элементов в массиве?
• Как найти наибольший (наименьший) элемент массива?

Введение в тему 

Любую информацию, чтобы в ней разобраться, необходимо упорядочивать определённым образом. Например, информация в книгах упорядочивается по содержанию, а информация об обучающихся в конкретном классе упорядочивается в алфавитном порядке. Чтобы понять и/или выучить определённую информацию, необходимо её расставить в понятной для себя последовательности. 

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

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

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

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

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

Самыми распространённым методом сортировки массива является сортировка массива методом простого выбора.

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

Рис. 1. Алгоритм сортировки методом простого выбора

Чтобы описанный выше массив стал упорядоченным, необходимо проделать n − 1 просмотров массива.

 

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

 

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

 

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

Пример 1

 

Дан одномерный целочисленный массив А. Вывести элементы массива в порядке возрастания.

 

Решение

 

Рис. 2. Раздел описания переменных

     1. Создадим программу sort_vibor. В разделе описания переменных создадим массив А на 1 000 значений, а также 4 переменных: i — для внешнего цикла, который показывает длину массива; j — для внутреннего цикла, который используется для поиска максимального элемента массива; index — для временного хранения индекса элемента; znachenie — для временного хранения значения элемента (рис. 2).

Рис. 3. Первая часть программного блока

     2. В программном блоке обозначим просьбы к пользователю сначала ввести количество элементов в массиве, а затем и значения элементов, организуем считывание элементов в массив (рис. 3).

Рис. 4. Вторая часть программного блока

     3. Затем в цикле for i:=1 to 
kol_vo – 1 в операторных скобках присвоим переменной index индекс первой переменной массива (i), а переменной znachenie — значение переменной массива А (рис. 4).

Рис. 5. Третья часть программного блока

     4. Используем переменную j для создания внутреннего цикла (начинаем со второго элемента). Внутри цикла сравниваем значения массива со значением, хранящимся в переменной znachenie. Если значение элемента массива меньше значения, хранящегося в переменной znachenie, то осуществляем замену (рис. 5).

Рис. 6. Завершающая часть программного блока

Выведем упорядоченный массив в окно вывода (рис. 6)

Рис. 7. Готовая программа к задаче 1

Готовая программа к задаче 1 показана на рис. 7.

Рис. 8. Пример работы программы к задаче 1

Пример работы программы отображён на рис. 8

 

В результате получилась программа, в которой можно отсортировать в порядке возрастания 1 000 целых чисел.