Как поступить
в Онлайн-школу и получить аттестат?

Подробно расскажем о том, как перевестись на дистанционный формат обучения, как устроены онлайн-уроки и учебный процесс, как улучшить успеваемость и повысить мотивацию!

Нажимая на кнопку, я соглашаюсь на обработку персональных данных

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

Алгоритмы и программирование

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

 

План занятия

 

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

 

Цели занятия

 

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

 

Разминка

 

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

 

 

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

 

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

 

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

 

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

 

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


Сортировка – это упорядочивание информации в определенном порядке.

 

Цель сортировки – облегчить поиск необходимых элементов массива.

 

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

 

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


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

 

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

 

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

 

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


Алгоритм сортировки массива методом простого выбора для поиска:

 

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


Рис. 1. Алгоритм сортировки методом простого выбора Рис. 1. Алгоритм сортировки методом простого выбора
Чтобы описанный выше массив стал упорядоченным необходимо проделать n-1 просмотров массива.

 

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

 

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

 

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


Пример 1

 

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

 

Решение:

 

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

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

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

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

Рис. 6. Завершающая часть программного блока Рис. 6. Завершающая часть программного блока
Выведем упорядоченный массив в окно вывода (Рис. 6)

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

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

 

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


Контрольные вопросы

 

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


Предыдущий урок
Запись вспомогательных алгоритмов на языке Паскаль
Алгоритмы и программирование
Следующий урок
Алгоритмы управления
Алгоритмы и программирование
  • Координаты вектора

    Геометрия

  • Средства анализа и визуализации данных. Сортировка и поиск данных

    Информатика

  • Describing food. Описание еды

    Английский язык

Зарегистрируйся, чтобы присоединиться к обсуждению урока

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

Отзывы об уроке:
Пока никто не оставил отзыв об этом уроке