Сортировка простым выбором

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение

Высшего профессионального образования

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ»

 

Кафедра информатики и методики преподавания математики

Учебно-методический комплект дисциплины: Методы разработки программ

 

Специальность 030100Информатика

УТВЕРЖДАЮ   Заведующий кафедрой   Потапов А.С.   «___» _____________ 2009 г.

Конспект лекций

Для студентов заочного отделения

Ведущий лектор:

Чулюков Владимир Алексеевич, профессор, к.ф.-м.н., доцент

 

Одобрен на заседании кафедры

«__» _________ 200 __ г. протокол № _________

Воронеж

 

 

СТРУКТУРА

конспекта лекций по дисциплине «Методы разработки программ»

 

Лекция № 1.

Тема: Понятия сортировки. Простые методы сортировки массивов.

Основные вопросы, рассматриваемые на лекции:

 

1. Понятия и цели сортировки.
2. Сортировки массивов и сортировки файлов.
3. Требования к методам сортировки массивов.
4. Меры эффективности.
5. Сортировка простыми включениями.
6. Сортировка бинарными включениями.
7. Сортировка простым выбором.
8. Метод «пузырька».
9. Шейкер-сортировка.

 

Краткое содержание лекционного материала

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

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

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

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

 

 

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

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

 

Рис.1.2. Сортировка файла

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

Сортировка означает перестановку этих элементов в таком порядке:

.

что при заданной функции упорядочения f справедливо решение

(1)

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

type item = record key: integer;

{ описание других компонентов } (2)

end

«Прочие компоненты» - это все существенные данные об элементе; поле key - ключ служит лишь для идентификации элементов. Однако, когда мы говорим об алгоритмах сортировки, ключ для нас – единственная существенная компонента, и нет необходимости как-то определять остальные. Выбор в качестве типа ключа целого типа достаточно произволен; ясно, что точно так же можно использовать и любой тип, на котором задано отношение всеобщего порядка.

Метод сортировки называется устойчивым, если относительный порядок элементов с одинаковыми ключами не меняется при сортировке. Устойчивость сортировки часто бывает правильна, если элементы упорядочены (рассортированы) по каким-то вторичным ключам, т. е. по свойствам, не отраженным в первичном ключе.

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

Основное требование к методам сортировки массивов – экономное использование памяти. Это означает, что переупорядочение элементов нужно выполнять in situ (на том же месте) и что методы, которые пересылают элементы из массива a в массив b, не представляет для нас интереса. Таким образом, выбирая метод сортировки, руководствуясь критерием экономии памяти, классификацию алгоритмов мы проводим в соответствии сих эффективностью, т. е. экономией времени или быстродействием. Удобная мера эффективности получается при подсчете числа С – необходимых сравнений ключей и М – пересылок элементов. Эти числа определяются некоторыми функциями от числа n сортируемых элементов. Хотя хорошие алгоритмы сортировки требуют порядка n log n сравнений, мы обсудим несколько несложных и очевидных способов сортировки, называемых простыми методами, которые требуют порядка n² сравнений ключей. Рассмотрим простые методы по следующим трем причинам:

1. Простые методы особенно хорошо подходят для разъяснения свойств большинства принципов сортировки.

2. Программы, основанные на этих методах, легки для понимания и коротки. Следует помнить, что программы также занимают память!

3. Хотя сложные методы требуют меньшего числа операций, эти операции более сложны; поэтому при достаточно малых n простые методы работают быстрее, но их не следует использовать при больших n.

 

Методы, сортирующие элементы in situ, можно разбить на три основных класса в зависимости от лежащего в их основе приема:

Сортировка включениями.

Сортировка выбором.

Сортировка обменом.

Рассмотрим и сравним эти три принципа. Программы работают с переменной-массивом а, который нужно рассортировать in situ. В этих программах используются типы данных item (2) и index, определенные так:

type index = 0.. n;

var a: array [1.. n] of item (3)

 

Сортировка простыми включениями

Этот метод обычно используют игроки в карты. Элементы (карты) условно разделяются на готовую последовательность и входную последовательность . На каждом шаге, начиная с i = 2 и увеличивая i на единицу, берут i–й элемент входной последовательности и передают в готовую последовательность, вставляя его на подходящее место.

 

Таблица 1.1. Пример сортировки простыми включениями

Начальные ключи 44 55 12 42 94 18 06 67

i = 2 44 55 12 42 94 18 06 67

i = 3 12 44 55 42 94 18 06 67

i = 4 12 42 44 55 94 18 06 67

i = 5 12 42 44 55 94 18 06 67

i = 6 12 18 42 44 55 94 06 67

i = 7 06 12 18 42 44 55 94 67

i = 8 06 12 18 42 44 55 67 94

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

for i:= 1 to n do

begin x:= a[ i ];

«вставить x на подходящее место в »

end

При поиске подходящего места удобно чередовать сравнения и пересылки, т. е. как бы «просеивать» x, сравнивая с очередным элементом и либо вставляя x, либо передается вправо и продвигаясь налево. Заметим, что «процесс просеивания » закончится при двух различных условиях:

1. Найден элемент с ключом меньшим, чем ключ у x.

2. Достигнут левый конец.

Такой повтор процесса с двумя условиями позволяет нам воспользоваться хорошо известным приемом фиктивного элемента («барьера»). Его можно легко приметить в этом случае. Установив барьер = x. (Заметим, что для этого нужно расширить диапазон индексов в описании a до 0, …, n.) Окончательно алгоритм представлен в виде программы 1.

 

procedure straightinsertion;

var i, j: index; x: item;

begin

for i:=2 to n do

begin x:= a [ i ]; a [0]:= x; j:= i -1;

while x.key < a [ j ]. key do

begin a [ j+ 1]:= a [ j ]; j:= j - 1;

end;

a [ j +1]:= x

end;

end;

Программа 1.1. Сортировка простыми включениями

Анализ сортировки простыми включениями. Общее число сравнений С и пересылок М есть

(4)

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

 

Сортировка бинарными включениями

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

procedure binaryinsertion;

var i, j, l, r, m: index; x: item;

begin

for i:= 2 to n do

begin x:= a [ i ]; l:= 1; r:= i;

while l < r do

begin m:= (l + r) div 2;

if x.key >= a [ m ]. key then l:= m + 1 else r:= m

end;

for j:= i downto r +1 do a [ j ]:= a [ j- 1];

a [ r ]:= x;

end;

end;

Программа 1.2. Сортировка бинарными включениями

Анализ сортировки бинарными включениями.

Количество сравнений не зависит от исходного порядка элементов. Но из-за округления при делении интервала поиска пополам действительное число сравнений для i элементов может быть на 1 больше ожидаемого. Природа этого «перекоса» такова, что в результате места включения в нижней части находятся в среднем несколько быстрее, чем в верхней части. Это дает преимущество в тех случаях, когда элементы изначально далеки от правильного порядка. На самом же деле минимальное число сравнений требуется, если элементы вначале расположены в обратном порядке, а максимальное – если они уже упорядочены. Следовательно, это случай неестественного поведения алгоритма сортировки:

К сожалению, улучшение, которое мы получаем, используя метод бинарного поиска, касается только числа сравнений, а не числа необходимых пересылок. В действительности поскольку пересылка элементов, т. е. ключей и сопутствующей информации, обычно требует значительно больше времени, чем сравнение двух ключей, то это улучшение ни в коей мере не является решающим: важный показатель М по-прежнему остается порядка n². И в самом деле, пересортировка уже рассортированного массива занимает больше времени, чем при сортировке простыми включениями с последовательным поиском! Этот пример показывает, что «очевидное улучшение» часто оказывается намного менее существенным, чем кажется в начале, и в некоторых случаях (которые действительно встречаются) может на самом деле оказаться ухудшением. В конечном счете сортировка включениями оказывается не очень подходящим методом для цифровых вычислительных машин: включение элемента с последующим сдвигом всего ряда элементов на одну позицию неэкономна. Лучших результатов можно ожидать от метода, при котором пересылки элементов выполняются только для отдельных элементов и на большие расстояния. Эта мысль приводит к сортировке выбором.

Сортировка простым выбором

Этот метод основан на следующем правиле:

1. Выбирается элемент с наименьшим ключом.

2. Он меняется местами с первым элементом a₁.

Эти операции затем повторяются с оставшимися n - 1 элементами, затем с n - 2 элементами, пока не останется только один элемент – наибольший. Этот метод продемонстрирован на тех же восьми ключах в табл. 2.

Таблица 1.2. Пример сортировки простым выбором

Начальные ключи 44 55 12 42 94 18 06 67

06 55 12 42 94 18 44 67

06 12 55 42 94 18 44 67

06 12 18 42 94 55 44 67

06 12 18 42 94 55 44 67

06 12 18 42 44 55 94 67

06 12 18 42 44 55 94 67

06 12 18 42 44 55 67 94

 

Программу можно представить следующим образом:

for i:= 1 to n -1 do

begin «присвоить k индекс наименьшего элемента из a [ i ]... a [ n ] »;

«поменять местами a_i и a_k »

End

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

procedure straightselection;

var i, j, k: index; x: item;

begin for i:=1 to n - 1 do

begin k:= i; x:= a [ i ];

for j:= i + 1 to n do

if a [ j ]. key < x.key then

begin k:= j; x:= a [ j ]

end;

a [ k ]:= a [ i ]; a [ i ]:= x;

End

End

Программа 1.3. Сортировка простым выбором

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

. (5)

Минимальное число пересылок равно

(6)

в случае изначально упорядоченных ключей и принимает наибольшее значение:

, (7)

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

(8)

где – эйлерова константа.

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