Несколько слов о сортировке информации

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

Рассмотрим это на примере списка учеников класса. В журнале список приводится в словарном порядке. Чтобы такой список появился, классный руководитель и секретарь школы проделали некоторые манипуляции: может быть, просто нажимали кнопки на компьютере, а возможно, раскладывали личные дела. На линейке 1 сентября и на уроках физкультуры во многих школах принято выстраивать детей по росту, а чтобы не забыть поздравить ребёнка с днём рождения, удобно иметь список детей в порядке их дат рождения. Во всех приведённых случаях наводился определённый порядок по заранее выбранному правилу. Операцию по наведению порядка будем называть упорядочением. В терминологии курса можно говорить, что при упорядочении объекты выстраиваются в цепочку.

В процессе выполнения проектов мы постарались разобраться в способах упорядочения информации. При упорядочении все элементы списка выстраиваются в цепочку друг за другом в соответствии с заранее выбранным правилом. Но часто нужно не расставлять учеников в каком-то порядке, а объединить их в некоторые группы опять же по заранее установленным правилам (признакам): мальчики — девочки, отличники — хорошисты — троечники — двоечники, дети из полных семей — дети из неполных семей, общее любимое блюдо, близко живущие дети, болельщики одной команды и т. д. Операцию по объединению в группы будем называть группировкой. В терминологии курса можно говорить, что при группировке объекты раскладываются в мешки по определённым правилам.

На первый взгляд между упорядочением и группировкой мало общего, но на самом деле это не так. В большинстве случаев нас действительно не интересует порядок, в котором мы рассматриваем результаты группировки. Не имеет значения, кто стоит впереди — мальчики или девочки — и в каком порядке рассматривать отличников, троечников и хорошистов. Важно только, что они объединены в группы. Но попробуем проследить, как мы группируем учеников. Мы обязательно вырабатываем для себя некоторый порядок. Например, в левый столбик выписываем фамилии отличников, правее — хорошистов, ещё правее — учеников с одной тройкой и т. д. Затем начинаем в столбики вписывать фамилии. Зрительно у нас снова получаются цепочки (ведь в каждом столбике слова идут друг за другом), но здесь порядок слов нам неважен.

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

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

В математике понятие «сортировка» объединяет понятия «упорядочение» и «группировка». Мы также используем только термин «сортировка», иногда уточняя: «Сортировать в алфавитном порядке».

Описание проекта

Умение ориентироваться в больших массивах информации является важнейшим в век информационных технологий. Прежде всего нужно иметь возможность легко находить информацию, соответствующую определённым критериям, сортировать и группировать её по определённым правилам. В современной повседневной жизни основную черновую работу по обработке больших массивов информации проводят компьютеры. Выполнять её вместо компьютера в реальной жизни нам не надо, но чтобы правильно интерпретировать результаты работы компьютеров и должным образом подготовить запрос для компьютера (правильно поставить задачу поиска и обработки информации), важно понимать, как они это делают. Знакомству с алгоритмом сортировки и посвящён настоящий проект. Часто в жизни бывают моменты, когда требуется расставить или разложить в заданном порядке различные предметы (книги, тетрадки). Такую работу не удастся передать компьютеру.

При выполнении предыдущего проекта учащиеся познакомились с устройством «настоящих» словарей, иначе говоря — с сущностью словарного (лексикографического) порядка. Дети уже умеют расставить в алфавитном порядке небольшое количество слов и объяснить, почему слово АРБУЗ идёт перед словом ВОРОТА, а слово ВОРОТА идёт после слова ВОРОНА. Вы с детьми, скорее всего, ещё не обсуждали стратегию, используя которую можно быстро и безошибочно расположить все слова в словарном порядке. Обычно достаточно просто просмотреть все слова, выбрать первое по алфавиту, из оставшихся слов выбрать второе и т. д. Способ, каким выбирается очередное слово, тоже, как правило, раньше не обсуждался, потому что для маленького списка слов не возникало такой проблемы. Обычно дети, проговаривая про себя или тихо вслух алфавит (а может быть, и со зрительной опорой на напечатанный алфавит), пробегают глазами все слова и ищут, нет ли среди них слова на очередную букву. Если такое слово есть, его ставят в цепочку. Постепенно формируется упорядоченная по алфавиту цепочка слов. Если на очередную букву будет больше одного слова, начинают разбираться с ними по второй букве.

Теперь усложним задачу. Попросим расположить в алфавитном порядке весьма значительный массив слов: 16 листов по 24 карточки — это 384 слова. Количественное увеличение слов в данном случае приводит к качественным изменениям (попробуйте подумать, к каким именно, прежде чем продолжите читать текст). Из 384 слов уже нельзя увидеть сразу все и даже найти первое из них — непростая задача. Методика, интуитивно используемая детьми при сортировке небольшого числа слов, здесь неприменима.

Приступая к выполнению проекта, выньте листы вкладыша из одной тетради проектов и вырежите из них отдельные карточки. Каждый ребёнок имеет в тетради проектов полный список всех слов, что позволит ему заняться их сортировкой и дома вместе с родителями; в классе же на первых порах рекомендуется использовать только один набор слов. Можно попробовать поставить задачу сортировки, не давая сначала никаких руководящих указаний, и понаблюдать, что и как ребята будут делать.

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

При сортировке большого массива возникают два вопроса:

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

2. Как правильно распределить работу? Когда на долю человека выпадает очень много работы, он зовет себе на помощь других людей и они делают её вместе. Но, работая вместе, нужно уметь договориться о том, кто что будет делать. Ведь может получиться так, что люди будут не помогать, а только мешать друг другу. Не исключено, что работать будут только один или два человека, а остальные — наблюдать. Обучаясь при выполнении этого проекта организации совместной параллельной работы людей над общей задачей (что само по себе очень важно), мы познаем и то, как это делают компьютеры.

Прежде чем приступить собственно к выполнению проекта, следует провести подготовительную работу:

1. Повторить с детьми алфавит.

2. Поиграть всем классом в игру со словами, например в такую: узнать, какое слово из пары идёт раньше в словаре: ВОРОТА или СОБАКА, ВОРОТА или ВОРОНА, ЧАШКА или ШАПКА. Наибольшие затруднения у детей обычно вызывают буквы второй половины алфавита.

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

Повторение алфавита

Фронтальная работа. На доске написан русский алфавит, но некоторые буквы пропущены. Пропуск обозначен многоточием, причём число пропущенных букв соответствует числу многоточий. Нужно назвать пропущенные буквы (надпись на доске вначале закрыта, учитель открывает её в нужный момент).

 

А...... Г... Е Ё...... И Й... Л... Н... П Р...... У... Х Ц Ч... Щ Ъ...... Э... Я

 

Учитель. Закройте глаза и представьте расположение букв в алфавите. Может быть, кто-то из вас про себя проговорит, как расположены буквы в алфавите. Откройте глаза и посмотрите на доску. Что вы видите?

Дети. Буквы русского алфавита. Они стоят в алфавитном порядке, но некоторые буквы пропущены.

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

Учитель. Я написал алфавит, а затем часть букв стёр. От каждой стёртой буквы остались только точки. Кто может назвать пропущенные буквы в том порядке, в котором они должны идти в алфавите?

Дети. Б, В, Д, Ж, З, К, М, О, С, Т, Ф, Щ, Ы, Ь, Ю.

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

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

 

Б Д Ж З К М О С Т Ф Ш Ы Ю

 

Учитель. Посоветуйтесь с соседом и примите решение, какие буквы пропущены.

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

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

Работа в группах. Перемешанные буквы (из магнитной азбуки, из конструктора, вырезанные из картона) раскладываются в алфавитном порядке. Делается это так. Учитель высыпает в беспорядке буквы алфавита (по одному экземпляру каждой буквы). Каждый ребёнок в группе из 12 — 15 детей берёт себе по 2—3 буквы (в произвольном порядке). Затем по команде учителя дети в каждой группе начинают раскладывать все буквы в алфавитном порядке. В этой игре дети должны одновременно решать несколько важных задач как содержательного (повторение алфавита), так и коммуникативного характера (умение услышать друг друга и договориться). Проверять данную работу может либо учитель, либо другая группа детей.

Задача окажется более сложной, если учитель положит на столе некоторые буквы не в одном экземпляре. Сложной не столько по содержанию (с этим дети справятся быстро), сколько в коммуникативном плане: при обнаружении повторяющейся буквы чью букву оставить, а чью убрать.

Повторить расположение букв в алфавитном порядке обязательно следует перед началом выполнения проекта по сортировке массивов слов. Объём и количество упражнений, связанных с повторением, зависят от подготовленности класса и желания учителя. Эту деятельность можно либо оформить как мини-проект в один-два урока, либо разбить на серию упражнений и включать фрагментами в различные по тематике уроки.

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

Основной проект

Разобьём наш большой проект «Сортировка слиянием» на шесть более мелких мини-проектов, каждый из которых имеет свою содержательную цель. Эти мини-проекты выстроены в цепочку, каждый последующий элемент в ней продолжает предыдущий. Их обязательно надо выполнять по порядку. Правильнее считать все мини-проекты частями одного большого проекта. Мы выделяем их, так как каждый из них, являясь частью целого, имеет и свою законченную цель.

Мини-проект 1: найти слово, которое идёт раньше всех из небольшого массива слов. Выполнять этот мини-проект лучше всего в небольших группах по 2—4 человека. Возьмите один комплект карточек (16 листов по 24 карточки). Раздайте каждой группе по одному листу с карточками (24 слова), лучше предварительно разрезав его на карточки. Каждую группу попросите из своих слов найти первое слово — слово, идущее раньше всех других. В процессе поиска учащиеся должны постараться объяснить друг другу, как и что они делают. Им надо ответить на два вопроса:

1. Как они нашли это слово?

2. Почему они уверены, что это слово первое?

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

1. Взять два первых попавшихся слова.

2. Из них выбрать то, которое стоит раньше, а второе отложить в сторону.

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

4. Когда в исходной кучке карточек не останется слов, у нас в руках будет самое первое слово.

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

Мини-проект 2: найти слово, идущее раньше всех из нескольких массивов слов. Этот проект очень короткий, но его выполнение и последующее обсуждение имеют большое значение для понимания оптимального, наиболее быстро приводящего к достижению результата алгоритма слияния нескольких массивов слов. После завершения мини-проекта 1 обычно кто-то довольно быстро догадывается, что первое из всех слов надо искать среди первых слов каждой группы. Поскольку таких слов немного, то нужное слово увидеть нетрудно — так же как в мини-проекте 1, даже ещё быстрее. Но стоит проговорить ещё раз необходимость сравнения выбранного слова со всеми остальными первыми словами из групп и косвенного (по транзитивности) сравнения со всеми 384 словами.

Можно предложить такой порядок действий:

1. Все группы поднимают своё первое слово на всеобщее обозрение. Теперь каждая группа имеет возможность сравнить своё первое слово с первыми словами остальных групп.

2. Далее все считающие, что их слово не первое, опускают его. Через некоторое время поднятым останется одно слово, которое и будет самым первым среди всех. Дети могут ошибаться, поэтому надо попросить каждого опускающего слово объяснить, почему он это делает. Например: «У нас слово ВОРОТА, а у Саши — БАРАБАН. Слово БАРАБАН стоит раньше, чем ВОРОТА, значит, мы можем опустить своё слово». Не сразу все понимают, что они могут опустить своё слово, если увидели хотя бы одно слово, которое стоит раньше его.

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