Конспект урока Сортировка массива. Информатика. 9-10 класс
план-конспект урока на тему

Сортировка массивов.

Макарова Анастасия Валерьевна

Цель:

1. Рассмотрение актуальности сортировки массивов.
2. Разбор на примерах разнообразия алгоритмов сортировки.
3. Воспитание умения воспринимать достаточно сложные алгоритмические конструкции.
4. Развитие творческого мыслительного потенциала.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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