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

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

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

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

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

27.03.2024
1578
0

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

 

План занятия

 

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

 

Цели занятия

 

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

 

Разминка

 

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

 

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

 

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

 

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

 

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

 

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


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

 

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

 

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

 

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


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

 

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

 

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

 

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


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

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


Рис. 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 целых чисел. 


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

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


Предыдущий урок
Конструирование алгоритмов
Алгоритмы и программирование
Следующий урок
Одномерные массивы целых чисел. Описание, заполнение, вывод массива
Алгоритмы и программирование
Урок подготовил(а)
teacher
Иван Андреевич
Учитель информатики
Опыт работы: 7 лет
Поделиться:
  • Химические свойства оснований как электролитов. Химические свойства солей как электролитов

    Химия

  • Лексика. Морфемика. Словообразование

    Русский язык

  • Ядерные реакции. Деление и синтез ядер. Ядерная энергетика. Источники энергии Солнца и звёзд

    Физика

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

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

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