Сортировка массивов
план-конспект урока по информатике и икт (11 класс) по теме

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

Клименкова Альбина Евгеньевна

Цель:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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