ИЗУЧЕНИЕ СОРТИРОВКИ ПОДСЧЕТОМ В ШКОЛЬНОМ КУРСЕ ИНФОРМАТИКИ

Статья опубликована в рамках: Международной научно-практической интернет-конференции «Актуальные проблемы методики обучения информатике в современной школе» (Россия, г.Москва, МПГУ, 24-26 апреля 2018г.)

ИЗУЧЕНИЕ СОРТИРОВКИ ПОДСЧЕТОМ В ШКОЛЬНОМ КУРСЕ ИНФОРМАТИКИ

Тюшнякова Ирина Анатольевна
кандидат технических наук, доцент

Таганрогский институт имени А.П.Чехова (филиал)
«РГЭУ (РИНХ)»
Россия, e-mail: Solovyova_Irina@mail.ru

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

Авторские программы по информатике и ИКТ для среднего (полного) общего образования различных авторов предполагают изучение алгоритмов сортировок, как правило, в рамках раздела «Программирование».

Сортировка [2, 3] является одной из базовых процедур нечисловой обработки данных. Алгоритмы сортировок применяются в различных задачах, связанных с системами автоматизированного управления, с информационно-поисковыми системами и т.д. Сортировки используются для эффективной обработки (например, для поиска) в больших наборах данных; для представления массивов данных в удобной для анализа форме; с целью группировки элементов по определенному признаку и др. Использование алгоритмов сортировки для решения задач вычислительной математики  и распознавания изображений представлено в [4, 5].

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

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

Суть сортировки подсчетом состоит в определении номеров мест элементов массива, расстановка по которым даст отсортированный массив. Метод основан на том, что j- ключ упорядоченной последовательности больше (j-1)-ключа массива. Сортировка подсчетом представляется с помощью матрицы сравнений (МС). Данная модификация метода, характеризующаяся визуально понятным, наглядным представлением алгоритма разработана доктором технических наук, профессором Роммом Я.Е. [1].

Рассмотрим массив неупорядоченных чисел А=(1, -5, 7, -1, 4, -5), состоящий из  элементов, расположим его в первой строке и первом столбце МС (рис. 1).

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

Рис. 1. Матрица сравнений для массива  А=(1, -5, 7, -1, 4, -5).

Накопленная сумма запоминается в счетчик по k, значение k получается адресом вставки: А1[k]=А[j], при этом можно запомнить и входной индекс вставленного элемента e[k]=j. На выходе сортировки А1[k] и e[k] имеют равный номер k. На рисунке 1 подсчитанные номера элементов в отсортированном массиве представлены ниже таблицы цифрами рядом со стрелками.

Структурная схема алгоритма представлена на рис. 2.

Рис. 2. Структурная схема алгоритма сортировки подсчетом.

Фрагмент программы сортировки подсчетом на языке Pascal:
……
begin
for j:=1 to N do
   begin
          k:=0;
          for i:=1 to j do if А[j]>=А[i] then k:=k+1;
          for i:=j+1 to N do if А[j]>А[i] then k:=k+1;
          А1[k]:=А[j]; e[k]:= j;
end; end;

Изучение данной сортировки в рамках уроков информатики, либо факультативных или элективных курсов, дает возможность познакомить учащихся с основами параллельного программирования. Данная сортировка допускает эффективное распараллеливание [58-60] с оценкой временной сложности

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

время выполнения шага O(1), т.е. 

ЛИТЕРАТУРА:

  1. Romm Ya.E. Sorting-based calculation of zeros and extrema of functions as applied to search and recognition // Cybernetics and Systems Analysis. 2001. Т. 37. № 5. С. 693-709.
  2. Вирт Н. Алгоритмы и структуры данных. — М.: ДМК-Пресс, 2016. — 272 c.
  3. Кнут Д. Искусство программирования. Т.З. Сортировка и поиск (второе издание). – М.: Вильямс, 2017. – 824 с.
  4. Ромм Я.Е., Тюшнякова И.А. Применение сортировки для поиска нулей и особенностей функций с приложением к идентификации плоских изображений // Учебное пособие. – Таганрог, 2009.
  5. Тюшнякова И.А. Разработка и исследование схем применения сортировки для поиска нулей и особенностей функций с приложением к идентификации плоских изображений // Диссертация на соискание ученой степени кандидата технических наук. – Таганрог, 2006.

Отправить ответ

Уведомить о
avatar
Sort by:   newest | oldest | most voted
Александра Борисовна

Здравствуйте, Ирина Анатольевна! Возникают ли трудности у школьников в реализации сортировки подсчетом? В каком классе можно познакомить учащихся с таким методом?

wpDiscuz