Конспект урока информатики по теме "Сортировка массива" для 9 класса

Тема урока информатики «Сортировка массива», 9 класс

Цель:

1. Рассмотрение актуальности сортировки массивов.

2. Разбор на примерах разнообразия алгоритмов сортировки.

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

4. Развитие творческого мыслительного потенциала.

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

Задача. Сформировать целочисленный массив М из 20 элементов. Вывести на экран не­сортированный массив М. Отсортировать массив по невозрастанию. Вывести отсортирован­ный массив.

Решение. Запишем общий вид решения этой задачи, не детализируя пока метод сортировки:

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

1. Линейная сортировка

а) Описание метода.

(Линейную сортировку в некоторой литературе называют также «сортировкой отбо­ром».) Идея линейной сортировки по невозрастанию заключается в том, чтобы, последова­тельно просматривая весь массив, отыскать наибольшее число и поместить его на первую позицию. Затем просматриваются все оставшиеся элементы массива и выполняется анало­гичная операция по отбору из рассматриваемой части массива максимального элемента и обмену местами этого элемента и первого в рассматриваемой части и т. д.

Рассмотрим подробнее работу этого метода на примере. Пусть требуется упорядочить по невозрастанию массив А из 4 элементов:

2. Сортировка методом пузырька

а) Описание метода.

«Пузырьковый» метод основан на том, что в процессе исполнения алгоритма более «легкие» (наименьшие по значению) элементы массива постепенно «всплывают». Особенно­стью данного метода является сравнение не каждого элемента со всеми, а сравнение в парах соседних элементов. Алгоритм пузырьковой сортировки по невозрастанию состоит в последовательных просмотрах снизу вверх (от начала к концу) массива М. Если соседние элементы таковы, что выполняется условие М[i] i+1], то выполняется обмен значениями этих элементов.

Рассмотрим подробнее работу этого метода на примере. Пусть требуется упорядочить по невозрастанию массив А из 4 элементов (условные обозначения те же):

3. Метод быстрой сортировки с разделением (дополнительно, на усмотрение преподавате­ля для хорошо успевающих учеников)

а) Описание метода.

Линейная и пузырьковая сортировки просты и наглядны, но не очень эффективны с точки зрения скорости работы алгоритма, т. к. для их реализации используются двойные циклы , т.е. независимо от вида массива каждая сортировка выполняется за одно и то же число шагов (свое для каждого метода) для массивов одинаковой длины. Значительно бы­стрее работает алгоритм сортировки с разделением или «быстрой сортировки», т. к. этот метод не использует цикл с параметром. В основе алгоритма лежит метод последователь­ного дробления массива на части. Количество шагов, которые выполняются при использо­вании этого метода, определяется видом массива (из каких элементов он состоит) и не яв­ляется фиксированным для массивов одинаковой длины, за счет чего достигается увели­чение скорости выполнения сортировки.

б) Схема алгоритма (для задачи).