Сравнительная характеристика методов сортировки

Вспомним один из простых методов - метод подсчета. Поскольку этот метод, несмотря на усовершенствование, требует сравнения всех пар элементов, то продолжительность сортировки массива из n элементов будет пропорциональна N².

Несколько лучшие показатели имеют методы сортировки вставками, обменом и выбором, однако и в них продолжительность работы процедур также пропорциональна n2. Вместе с тем можно показать, что время, затрачиваемое на упорядочивание массива такими методами, как, например, быстрая сортировка или пирамидальная сортировка, пропорционально n log2n, т.е. значительно меньше. Поэтому все рассмотренные методы сортировки подразделяют на простые (n²) и усовершенствованные, или "логарифмические" (n log2n).

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

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

Наилучшим среди простых методов является сортировка вставками, среди усовершенствованных - быстрая сортировка.

Пузырьковая сортировка является наихудшей среди всех сравниваемых методов. Ее улучшенный вариант — шейкер-сортировка — все-таки хуже, чем сортировка простыми вставками и сортировка выбором.

Следует добавить, что приведенные результаты были получены при сортировке числовых массивов. Если же значением элементов массива являются данные типа "запись", в которых сопутствующие поля (компоненты) занимают в 7 раз больше памяти, чем числовое поле, по которому проводится сортировка, то картина изменится.

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

 

 

Классификация задач с применением сортировок

Задачи заполнения

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

procedure Zapolnenie (n: integer; var a: Array of <тип>);

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

 

По методу решения задачи заполнения можно разделить на несколько групп. Главные из них — прямое заполнение и заполнение с поиском.

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

Конкретные методы и приемы прямого заполнения разберем с помощью серии последовательных примеров.

Пример 1. Заполнить таблицу последовательностью четных чисел.

Этот пример интересен тем, что допускает два решения: с использованием формулы и рекуррентное.

Первое решение использует общую формулу четного числа.

 

procedure <четность> (n: integer; var a: Array of integer);

var i: integer;

begin

for i:= 1 to n do a[i]=2*i;

end;

 

Второе решение основано на рекуррентном соотношении: каждое следующее четное число на 2 больше предыдущего.

procedure <четность> (n: integer; var a: Array of integer);

var i: integer;

begin

a[1]:= 2;

for i:= 1 to n do a[i]=a[i-1]+2;

end;

 

Пример 2. Заполнить массив значениями элементов последовательности Фибоначчи.

Здесь рекуррентное соотношение — наиболее естественный способ решения.

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

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

Пример 3. Робот стоит перед входом в коридор, уходящий очень далеко вправо. В коридоре много закрашенных клеток. Записать в таблицу уровни радиации в первых N закрашенных клетках.

Эту задачу можно решить двумя способами.

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

 

алг радиация (арг цел N, рез вещ таб рад[1:N])

 нач цел i

       нц для i от 1 до N

            нц пока клетка не закрашена

                | вправо

          кц

            рад[i]:=радиация

            вправо \\сойти с закрашенной клетки

       кц

 кон

 

При решении задачи вторым способом мы не станем сводить ее к уже известным. Робот идет по коридору, проверяя все клетки. Закрашенные клетки регистрируются, то есть уровень радиации в них заносится в таблицу.

 

алг радиация(арг цел N, рез вещ таб рад[1:N])

нач цел i

  i:=0 \\i - количество найденных закрашенных клеток   

нц пока i<N

   вправо \\i переход в следующую клетку

если клетка закрашена

  то i:=i+1 \\регистрация закрашенной клетки

     рад[i]:=радиация

все

кц

кон

 

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

 

 

Задачи анализа

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

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

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

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

 

 

Задачи поиска

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

Большинство задач поиска сводится к простейшей — найти в таблице элемент с заданным значением.

Предположим, что о расположении данных в таблице нет никаких сведений. Тогда проверка одного элемента не дает никакой информации об остальных. Самый разумный способ поиска в этом случае — последовательный перебор.

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

 

алг поиск(арг цел N, арг вещ таб a[1:n])

дано х \\ x - значение, которое нужно найти

надо k если a[k]=x  

          \\k - индекс элемента, значение которого равно х, k=0, если такого элемента нет

нач цел i

 k:=0

 нц для i от 1 до N

если а[i]=х

то k:=i

все

кц

кон

 

 

Задачи перестановки

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

 

алг циклический сдвиг вперед(арг цел n, арг рез вещ таб а[1:n])

 нач цел. i, вещ t

 ! t:=a[1]

 ! нц для i от 1 до n-1

 !! a[i]:=a[i+1]

! кц

!a[n]:=t

 кон

Здесь важно понять необходимость дополнительной переменной для временного хранения одного элемента и правильно организовать заголовок цикла (до n-1, а не до n).

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

 

алг циклический сдвиг назад (арг цел n, арг рез вещ таб а[1: n])

 нач цел i, веш t

!t:=a[n]

! нц для i от n до 2 шаг  -1

|! a[i]:=a[i-1]

! кц

!a[1]:=t

кон

 

Задача: Найти и переставить местами максимальное и минимальное значение среди элементов таблицы.

алг Обмен МАХ МIN(арг цел n, арг рез вещ таб а[1: n])

 нач цел i,d,l, веш МАХ,MIN

!MAX:=a[1]; d:=1

MIN:=a[1]; l:=1

! нц для i от 2 до n

!! если а[i ]>MAX

!! то. MAX:=a[i]; d:=i

!!все

!! если а[i ]<MIN

!! то. MIN:=a[i]; l:=i

!!все

! кц

!a[d]:=MIN

!a[l]:=MAX

кон

 

Главная задача перестановки, конечно же, сортировка.

Литература

1. Абрамов С.А; Гнездилова Г. Г., Капустина Е.Н. и др. Задачи по программированию, - М.: Наука, 1988.

2. Ахо Альфред В., Джон Э. Хопкрофт, Джеффри Д.Ульман. Структуры данных и алгоритмы: Пер. с англ.: Учеб.пос.-М.: Издательский дом «Вильямс», 2000.-384.

3. Брудно А.А; Каплан Л. И. Московские олимпиады по программированию. - М.: Наука, 1990.

4. Вирт Н. Алгоритмы + структуры данных = программы. - М.: Мир, 1985.

5. Волков И.А., Копюв В.М., Харипюновш А.И. Вариации на тему поиска. - Информатика и образование, 1996, № 1..

6. Джонс Ж., К.Харроу. Решение задач в системе Турбо Паскаль.- Москва "Финансы и статистика".

7. Зайдельман Я.Н. Однопроходные алгоритмы. - Информатика и образование, 1995, № 4.

8. Златопольский А.М. Рекурсия. - Информатика, 1996, № 8-9.

9. Златопольский Д.М. Методы сортировки массивов. - Информатика и образование, 1997, № 10,11,14,16,19,21,22.

10. Измайлов А.А. Задачи. - Информатика, 1995, № 34.

11. Кнут Д Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. - М.: Мир, 1978.

12. Коновалов А.. Из опыта преподавания темы "Табличные величины. Алгоритмы работы с табличными величинами". - Информатика и образование, 1988, № 1.

13. Кушниренко А.Г., Лебедев Г.В., Сворень Р.А. Основы информатики и вычислительной техники. - М.: Просвещение, 1991г.

14. Маркова О.И. Обработка массивов на языке Бейсик. - Информатика и образование, 1994, № 3.

15. Образовательные модули по курсу информатики и информационным технологиям в базисном учебном плане. - Информатика, 1996, № 34.

16. Региональный образовательный стандарт по информатике. Саратов. 1998.

17. Соколинский М.С. Цифровая сортировка и цепочки. - Информатика и образование, 1997, № 6.

18. Фаронов В. В. Программирование на персональных ЭВМ в среде Турбо-Паскаль. - М.: Изд-во МГТУ, 1992.

 

 

Задачи

1. Из стоимости проезда автобуса и стоимости проезда до города Волгограда поездом выбрать минимальную стоимость.

2. Из трех расстояний до трех пунктов назначения выбрать максимальное расстояние.

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

4. В журнал записали рост десяти девочек. Определить минимальный рост ученицы.

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

6. Температура воздуха измеряли в полдень в течении месяца. Определить диапазон изменения различных температур, т.е. максимальную и минимальную температуру и их разность.

7. Температура воздуха измеряли в полдень в течении месяца. В какие дни была минимальная температура месяца и в какие дни достигалась максимальная температура.

8. Температура воздуха измеряли в полдень в течении месяца. Определить среднее арифметическое максимальной и минимальное температур и количество дней в месяце, когда температура была выше этого среднего арифметического.

 

 

Задача поиска