Способ слияния двух упорядоченных массивов информации очень важен. Учащиеся осваивают его в ходе практической деятельности. Можно обсудить, сколько времени потребовалось бы одному человеку для того, чтобы упорядочить все 384 слова. Мы уже определили, что для нахождения только одного первого слова может понадобиться больше трёх уроков; значит, на упорядочение всех слов, если второе и все остальные слова искать по тем же правилам, что и первое, уйдёт больше учебной четверти. Нам же удалось методом слияния упорядоченных массивов и с использованием параллельной работы групп выполнить задачу гораздо быстрее. При поиске первого слова выигрыш во времени получался только благодаря параллельной работе многих учащихся. Попросите детей подумать, что происходит в случае упорядочения. Получится ли быстрее, если один человек будет упорядочивать не сразу все 384 слова, а попытается в одиночку повторить способ работы, объединяющий третий и четвёртый мини-проекты. Попробуйте сами ответить на этот вопрос.
Предложите учащимся провести эксперимент. Пусть один ученик упорядочивает 24 слова, находя сначала первое слово, затем второе, затем третье и т. д., а другой, разбив их на четыре кучки, упорядочивает каждую кучку, а затем сливает полученные цепочки слов по уже выработанным в проекте правилам. Интересно сравнить время выполнения работы и занести результаты в таблицу. Затем стоит поменяться стратегиями и заполнить таблицу ещё раз.
В силу разных случайностей у каждого конкретного ученика могут иногда получиться и результаты, не соответствующие эффективности выбранного способа сортировки, но в большинстве случаев всё должно быть правильно. Суммарное время будет больше при использовании первого способа.
Важно понять в процессе работы, что ускорение происходит не только за счёт правильного объединения усилий большого коллектива, но и благодаря выбору эффективного алгоритма. Даже если будет работать один человек (одна вычислительная машина), сортировка слиянием (разбиение мешка на части с последующей сортировкой и слиянием упорядоченных частей) окажется самой быстрой.
Мини-проект 5: сортировочное дерево. В предыдущем мини-проекте дети научились сливать упорядоченные массивы. Мы справились с задачей довольно быстро, но от этапа к этапу оставалось всё больше не участвующих в деле детей. Попробуем поставить дело так, чтобы возможности каждого в сортировке использовались наиболее эффективно. Дети уже при выполнении четвёртого мини-проекта могли заметить, что для продолжения слияния более длинных цепочек необязательно дожидаться окончания слияния её более коротких составных частей. Ведь слияние мы начинаем сверху, и к нему можно приступать, даже если работа «внизу» ещё не завершена. Давайте для решения задачи упорядочения всего мешка слов организуем деятельность так, чтобы каждый ученик выполнял свою часть задачи.
Попробуем нарисовать дерево слияний. Каждый ученик может сливать два массива, поэтому у каждой вершины (кроме листьев, конечно) будут ровно две следующие. Листьями этого дерева будут стопки слов. Число всех остальных вершин в этом дереве должно равняться числу учеников. Для 29 учеников дерево приведено на рисунке.
Каждая круглая бусина обозначает одного ученика, поэтому можно их подписать или пронумеровать (как это сделано на нашем дереве), а рядом записать, какой ученик относится к какому номеру. Следует обсудить, на чью долю в этой схеме выпадает больше всего работы. Исходя из опыта предыдущего мини-проекта, дети сообразят, что основная часть работы достанется тому, кто стоит в корне дерева. Поэтому лучше, если это будет наиболее сильный ученик, а возможно, и сам учитель.
Приведённое дерево достаточно просто перестроить для любого нечётного числа учеников от 15 до 31. Для 31-го ученика можно добавить две вершины на пятый уровень так, чтобы нижняя ветка дерева стала точно такой же, как верхняя. Если учеников в классе больше 31, то можно оставшихся детей назначить контролёрами на разные уровни. Они будут следить за правильным выполнением алгоритма. Кроме того, «корневому» ученику, возможно, просто понадобится помощь. Чтобы построить дерево для нечётного числа учеников, меньшего чем 29, можно убирать с пятого уровня по две вершины, следующие за некоторой вершиной четвёртого уровня, до тех пор, пока нужное число вершин не будет достигнуто. При этом следующие за убранными вершинами-учениками вершины-стопки, конечно, тоже убираются, а затем за каждой вновь появившейся вершиной-листом четвёртого уровня ставим по две вершины-стопки. Например, дерево для 25 учащихся приведено на следующем рисунке.
Если в классе число учеников чётное, можете либо сами поучаствовать в сортировочном дереве, либо одного ученика направить помощником к «корневому».
На первом этапе разобьём все слова на кучки по числу участвующих в мини-проекте учеников и попросим всех упорядочить свои слова в словарном порядке. Слов у каждого ученика будет немного, и такая задача не должна вызвать у учащихся затруднения — она знакома всем. Чтобы каждый ученик сливал ровно два массива, число стопок должно быть чётным. Поэтому если число учащихся в классе нечётное, то стопок следует заготовить на одну больше. Одну дополнительную кучку может упорядочить учитель.
Теперь надо придумать, как организовать работу. Возможен следующий вариант.
На столах выложены в ряд все упорядоченные массивы. Перед ними встаёт в два раза меньшее (чем число массивов) число учащихся. Далее учащиеся выстраиваются в соответствии с сортировочным деревом для вашего класса. Правила взаимодействия могут быть различными.
1. Каждый ученик занимается слиянием двух массивов (массива у левой руки и массива у правой руки), но складывает карточки со словами в стопку только «корневой» ученик, а остальные отдают первую из своих двух карточек ученику, стоящему у них за спиной, причём только после того, как этот ученик попросит (например, прикоснувшись к плечу).
2. У ученика в руках две карточки. Он выбирает из них первую и отдает её ученику, который стоит у него за спиной. Если первой была карточка в левой руке, то новую карточку надо попросить у ученика, который стоит слева (для ученика из первого ряда — взять карточку из левой кучки), а в противном случае — у ученика, который стоит справа.
Ускорение упорядочения происходит за счёт параллельности работы. Хотя при такой схеме, как мы уже выяснили с детьми, не все одинаково загружены работой, эффективность может быть очень высокой. Если «корневой» ученик (или учитель) работает быстро, а дети хорошо читают или быстро узнают слова, то процесс сортировки 384 слов потребует 15—25 минут. После окончания сортировки нужно ещё раз обсудить, кто больше был загружен и во сколько раз. Можно подсчитать, сколько сравнений сделал каждый ученик.
Алгоритм, описанный в данном мини-проекте, называется «алгоритмом пузырькового всплытия».
Мини-проект 6: сортировка через классификацию. Мини-проект даёт третий алгоритм выполнения той же задачи — сортировки большого массива слов (16 ? 24 слов) силами всего класса.
1. Разделите все карточки поровну на всех учащихся и попросите рассортировать их по мешкам (коробочкам, столам) так, чтобы в каждом мешке оказались слова на одну букву. При этом мы предварительно распределяем столы под мешки и подписываем эти столы с помощью большой таблички с буквой. Раскладывать слова могут все одновременно, перемещаясь по классу.
2. Затем каждый ученик садится за один стол (или берёт один ящик) со словами на определённую букву и наводит порядок в данных карточках. О том, кому какая буква достанется, вам надо подумать заранее. Количество слов в наборе на разные буквы различно. Есть очень «популярные» буквы, слов на которые больше 20 (В, К, Л, М, Н, П, С, Т). Ящики с такими буквами лучше поручить сильным учащимся. Есть буквы, на которые в наборе слов меньше 10 (А, Г, Е, Ё, З, И, Ф, Х, Ц, Э, Ю, Я). В соответствующих этим буквам ящиках смогут разобраться даже слабые и медлительные дети. При этом кому-то из ребят придётся заниматься сразу двумя ящиками. Все эти детали лучше продумать при подготовке к уроку.
3. Работы всех учеников собираются в алфавитном порядке первых букв. Обсудите с учениками, как проходила работа, и спросите, как они думают — всегда ли будет получаться так удачно? Они должны понять, что такой способ хорош лишь в определённых случаях. Продемонстрируйте это, предложив массив слов, у которых первые 2—3 буквы будут одинаковыми. В этом случае придётся по ходу действия менять алгоритм работы. Хорошо, если в результате последующих обсуждений дети усвоят, что данный алгоритм сортировки не универсальный (эффективность алгоритма зависит от конкретного набора слов), в отличие от универсального алгоритма сортировки слиянием упорядоченных массивов (эффективность не зависит от конкретного набора слов).
4. Стоит обсудить, нужны ли неуниверсальные алгоритмы. Если не возникнет никаких побочных проблем (например, неудобно стоящие столы), то при «хорошем» наборе слов (на каждую букву слов приблизительно одинаково) задача сортировки массива с помощью алгоритма упорядочения через классификацию будет выполнена значительно быстрее, чем посредством алгоритма пузырькового всплытия.
5. Важно обговорить роль каждого человека — маленького процессора, и координатора их работы — главного процессора (учителя или сильного ученика).
Список всех слов (в словарном порядке)
автор
алфавит
ангина
аппарат
аппетит
асфальт
афиша
балкон
баран
баранка
бег
бегемот
бесшумный
библиотека
болезнь
боль
больница
ботинок
вагон
вальс
варенье
варить
вежливый
верблюд
вертолёт
весёлый
весло
весна
весной
ветер
ветка
вечер
вещь
вид
видно
виноват
виноватый
виноград
вкусный
воротник
встреча
вторник
выход
газ
газета
глупость
голод
голодный
гроза
громко
грохот
двигаться
делать
дело
деловитый
деревня
диван
длина
длиннее
длинный
дождливый
дом
домашний
домино
домой
дорога
древний
дремучий
дуб
дубина
едва
единица
ель
ельник
ерунда
если
естественно
ехать
ёрш
жаворонок
жадный
жажда
жалеть
жара
жарить
жарко
жевать
желать
жених
женщина
жёлтый
жёлудь
животное
жизнь
журавль
журнал
завтра
завтрак
заноза
запас
запасной
запятая
затылок
зонтик
изгородь
издали
изюм
инструмент
испечь
истинный
кабачок
кабина
кабинет
календарь
каменный
камень
капуста
картон
картонный
картошка
катушка
квартира
кенгуру
кипяток
клей
клеймо
клетка
клёв
клён
клёст
клуб
клубника
ключ
кожура
кора
корабль
красота
крокодил
курица
лампочка
ландыш
ласточка
лаять
лекарство
ленивый
лентяй
лень
лес
леска
лестница
ливень
лишний
лопата
лопатка
луковица
лыжня
любопытство
люстра
лягушка
мак
макароны
макушка
мальчик
мартышка
маршрут
маслёнка
маслёнок
медведица
медведь
медвежонок
медленно
мелкий
метель
мёд
мёрзнуть
микроб
мокрый
мост
мостовая
мужской
муравей
муравейник
мыльница
мягкий
мясорубка
наверное
наверняка
наволочка
надо
надоесть
намочить
наоборот
насекомое
насморк
настроение
наугад
наука
наутро
научный
небо
некрасивый
нечаянно
нищий
новость
нож
ножницы
нужен
обед
обезьяна
одеяло
однажды
одуванчик
осенний
остановка
отведать
отвечать
отвёртка
отдых
отдыхать
охота
ошибка
палец
парикмахер
пасмурный
паук
переулок
перо
персик
петух
пещера
пёс
пёстрый
пища
пищать
платье
повязка
покупка
пол
полезно
полотенце
привычка
пряник
пылинка
радость
рассвет
расчёска
ремонт
рецепт
речка
родинка
родители
рыба
рыбалка
салки
салфетка
салют
свежий
свекольник
свет
свеча
свёкла
свёрток
серьёзный
сладкий
словарь
случайно
сметана
смех
собака
сорок
сорока
сосулька
ссадина
станция
стебель
стена
стёклышко
стол
столица
сухарь
съедобный
съестное
съёжиться
сыроежка
таблетка
такси
танцевать
тапочки
таракан
телега
телефон
телёнок
тень
тесто
тетрадь
тёплый
тёрка
тётя
тишина
товар
товарищ
тренировка
треугольник
трёпка
трёхэтажный
тротуар
труд
трудно
тюльпан
тяжело
удобный
улица
упрямый
уснуть
утка
утро
ученик
учёба
учёт
учитель
фамилия
фильм
фокус
фокусник
фонарь
форточка
характер
хозяйка
холодильник
хороший
храбрый
художник
царапина
цепочка
церковь
цыплёнок
чайник
чашка
чаща
через
черепаха
черешня
черёмуха
чеснок
честный
чехол
чёткий
чистить
чисто
чистота
чудесный
чулок
шапка
шар
шарф
шахматы
шашки
швабра
шелест
шея
шёпот
шишка
школьник
щавель
щекотка
щетина
щёлка
щётка
щи
щипать
щипцы
щука
щупальце
эвкалипт
электричка
эскалатор
юбка
юмор
ябеда
яблоня
ягода
язычок
яйцо
январь