«Метод сортировки вставками»

Цели урока:

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

Тип урока: комбинированный урок.

Ход работы:

Организационный момент 

Здравствуйте, ребята!

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

Актуализация знаний
      Тест  Приложение 1 с использованием системы интерактивного опроса InterWrite Response

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

Расскажите мне, пожалуйста, о методах сортировки, которые мы с вами уже изучили.

Какие вы знаете? (метод пузырька и метод последовательных минимумов)

Кто может рассказать нам, в чем суть метода пузырька? (сравниваются два рядом стоящих элемента массива)

Метод последовательных минимумов, что происходит в нем? (каждый раз находится самый маленький элемент и ставится на первое место)

Работа в группах.

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

Вам нужно исправить одну ошибку в программе и определить способ сортировки: как отсортирован массив по возрастанию или по убыванию.

Карточка 1 группы

Карточка 2 группы

CLS
INPUT " вв. размер массива"; n
DIM a(n)
FOR i = 1 TO n
a(i) = INT(RND * 100)

PRINT a(i);
NEXT i
PRINT
FOR j = 1 TO n - 1
min = a(j)
in = j
FOR y = j + 1 TO n
IF a(y) < min THEN
min = a(y)
in = y
END IF
NEXT y

NEXT j
FOR i = 1 TO n
PRINT a(i);
NEXT i
END

CLS
INPUT"вв. размер массива"; n
DIM a(n)
FOR i = 1 TO n
a(i) = INT(RND * 100)
PRINT a(i);
NEXT i
PRINT
PRINT "--------------------"
10 f = 1
FOR i = 1 TO n + 1
IF a(i) > a(i + 1) THEN
f = 0
SWAP a(i), a(i + 1)
END IF
NEXT i
IF f = 0 THEN GOTO 10
FOR i = 1 TO n
PRINT a(i);
NEXT i
END

Изучение нового материала 

Сортировка вставками — простой алгоритм сортировки.

У этого метода ряд преимуществ:

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

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

Алгоритмы сортировки Приложения: Метод сортировки вставками, SOR_VS1, SOR_VS2

Физкультминутка

Рисуй глазами треугольник. Теперь его переверни вершиной вниз. И вновь глазами ты по периметру веди. Рисуй восьмерку вертикально. Ты головою не крути, А лишь глазами осторожно ты вдоль по линиям води. И на бочок ее клади. Теперь следи горизонтально, И в центре ты остановись. Глазки крепко закрываем, Дружно до пяти считаем. Глаза открываем мы, наконец. Практическая работа

«Метод сортировки вставками»

Задание 1.

Реализовать на QBasic программу сортировки одномерного массива в порядке возрастания с помощью метода сортировки вставками.

Задание 2.

Переписать программу, используя подпрограмму вывода массива на экран.


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

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

Подведение итогов. Рефлексия. Приложение «Подведение итогов урока» с использованием системы интерактивного опроса InterWrite Response