1.2.3 Сортировка упорядоченным двоичным деревом. Алгоритм складывается из построения упорядоченного двоичного дерева и последующего его обхода. Если нет необходимости в построении всего линейного упорядоченного списка значений, то нет необходимости и в обходе дерева, в этом случае применяется поиск в упорядоченном двоичном дереве. Отметим, что порядок алгоритма - O(N*log2(N)), но в конкретных случаях все зависит от упорядоченности исходной последовательности, который влияет на степень сбалансированности дерева и в конечном счете - на эффективность поиска.

1.3 Сортировки распределением

1.3.1 Поразрядная цифровая сортировка. Алгоритм требует представления ключей сортируемой последовательности в виде чисел в некоторой системе счисления P. Число проходов сортировка равно максимальному числу значащих цифр в числе - D. В каждом проходе анализируется значащая цифра в очередном разряде ключа, начиная с младшего разряда. Все ключи с одинаковым значением этой цифры объединяются в одну группу. Ключи в группе располагаются в порядке их поступления. После того, как вся исходная последовательность распределена по группам, группы располагаются в порядке возрастания связанных с группами цифр. Процесс повторяется для второй цифры и т. д., пока не будут исчерпаны значащие цифры в ключе. Основание системы счисления P может быть любым. Для системы счисления с основанием P требуется P групп.

Порядок алгоритма качественно линейный - O(N), для сортировки требуется D*N операций анализа цифры. Однако, в такой оценке порядка не учитывается ряд обстоятельств.

НЕ нашли? Не то? Что вы ищете?

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

Во-вторых, в оценке алгоритма не учитываются расходы времени и памяти на создание и ведение групп. Размещение групп в статической рабочей памяти потребует памяти для P*N элементов, так как в предельном случае все элементы могут попасть в какую-то одну группу. Если же формировать группы внутри той же последовательности по принципу обменных алгоритмов, то возникает необходимость перераспределения последовательности между группами и все проблемы, присущие алгоритмам включения. Наиболее рациональным является формирование групп в виде связных списков с динамическим выделением памяти.

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

Область памяти, занимаемая массивом, перераспределяется между входным и выходным множествами. Выходное множество (оно размещается в начале массива) разбивается на группы. Разбиение отслеживается в массиве b. Элемент массива b[i] содержит индекс в массиве a, с которого начинается i+1-ая группа. Номер группы определяется значением анализируемой цифры числа. Когда очередное число выбирается из входного множества и должно быть занесено в i-ую группу выходного множества, оно будет записано в позицию, определяемую значением b[i]. Но предварительно эта позиция должна быть освобождена: участок массива от b[i] до конца выходного множества включительно сдвигается вправо. После записи числа в i-ую группу i-ое и все последующие значения в массиве b корректируются - увеличиваются на 1.

/*== Программный пример 8 – Поразрядная цифровая сортировка ==*/

const int D = 4; // максимальное количество цифр в числе

const int P = 10; // основание системы счисления

// Функция возвращает значение n-ой цифры в числе v

int Digit(int v, int n)

{

for (; n > 0; n--)

v = v / P;

return v % P;

}

// Функция поразрядной цифровой сортировки

void SortPlace(int[] a)

{

int[] b = new int[P]; // индекс элемента в массиве а, следующего за последним элементом из i-ой группы

int i, j, k, m, x;

int N = a. Length;

for (m = 0; m < D; m++) // перебор цифр, начиная с младшей

{

for (i = 0; i < P; i++)

b[i] = 0; // начальные значения индексов

for (i = 0; i < N; i++) // перебор массива

{

k = Digit(a[i], m); // определение m-ой цифры

x = a[i];

// сдвиг - освобождение места в конце k-ой группы

for (j = i; j >= b[k] + 1; j--)

a[j] = a[j - 1];

// запись в конец k-ой группы

a[b[k]] = x;

// модификация k-го индекса и всех больших

for (j = k; j < P; j++)

b[j] = b[j] + 1;

}

}

}

Результаты трассировки программного примера 8 при P=10 и D=4 представлены в таблице 5.

Таблица 5 – Трассировка поразрядной цифровой сортировки

Цифра

Содержимое массива а

Содержимое массива b

исх.

10 72 4

1

8
 

2
 

2
 

2
 

0
 
70 24 2

5,5,7,8,10,10,10,10,11,11

2

1
 

8
 

7
 

6
 

2
 
9510

9
 
44 83 8390

1,3,6,6,6,6,7,9,10,11

3

5
 

1
 
20 4

9
 
9

4
 

3
 

2
 

1,2,4,5,7,10,10,10,10,11

4

9
 

7
 

2
 

0
 
4 490 9

8
 

4
 

1
 

3,4,5,5,7,7,7,8,9,11

1.3.2 Быстрая сортировка Хоара. Данный алгоритм относится к распределительным и обеспечивает показатели эффективности O(N*log2(N)) даже при наихудшем исходном распределении.

Используются два индекса - i и j - с начальными значениями 0 и N-1 соответственно. Ключ K[i] сравнивается с ключом K[j]. Если ключи удовлетворяют критерию упорядоченности, то индекс j уменьшается на 1 и производится следующее сравнение. Если ключи не удовлетворяют критерию, то записи с номерами i и j меняются местами. При этом индекс j фиксируется и начинает меняться индекс i (увеличиваться на 1 после каждого сравнения). После следующей перестановки фиксируется i и начинает изменяться j и т. д. Проход заканчивается, когда индексы i и j становятся равными. Запись, находящаяся на позиции встречи индексов, стоит на своем месте в последовательности. Эта запись делит последовательность на два подмножества. Все записи, расположенные слева от нее имеют ключи, меньшие чем ключ этой записи, все записи справа - большие. Тот же самый алгоритм применяется к левому подмножеству, а затем к правому. Записи подмножества распределяются по двум еще меньшим подмножествам и т. д., и т. д. Распределение заканчивается, когда полученное подмножество будет состоять из единственного элемента - такое подмножество уже является упорядоченным.

Процедура сортировки в примере 9 рекурсивная. При ее вызове должны быть заданы значения границ сортируемого участка от 0 до N-1.

/*===== Программный пример 9 - Быстрая сортировка Хоара ==*/

void QuickSort(int[] a, int i0, int j0)

{ // i0, j0 - границы сортируемого участка

int i, j; // текущие индексы в массиве

bool flag; // признак меняющегося индекса: если flag=true -

// уменьшается j, иначе - увеличивается i

int x;

if (j0 <= i0) return; // подмножество пустое или из 1 эл-та

i = i0;

j = j0;

flag = true; // вначале будет изменяться j

while (i < j)

{

if (a[i] > a[j])

{ // перестановка

x = a[i];

a[i] = a[j];

a[j] = x;

// после перестановки меняется изменяемый индекс

flag = !flag;

}

if (flag) // изменение индекса (i или j)

j = j - 1;

else

i = i + 1;

}

QuickSort(a, i0, i - 1); // сортировка левого подмассива

QuickSort(a, i + 1, j0); // сортировка правого подмассива

}

Результаты трассировки примера приведены в таблице 6. В каждой строке таблицы показаны текущие положения индексов i и j, звездочками отмечены элементы, ставшие на свои места. Для каждого прохода показаны границы подмножества, в котором ведется сортировка.

Таблица 6 – Трассировка быстрой сортировки Хоара

Проход

Содержимое массива а

1

42i86j

37 79i95 25 42j

37 42i95 25j 79

37 25 39i42j 79

37ij 79

37ij 65 79

37ij

37i 60 29j

37i 42j

37ij

2

37ij 42*

39 25i 39 37j 42*

39 25 39i 37j 42*

39 25 37ij 39 42*

Окончание табл. 6

Проход

Содержимое массива а

3

39i 25j 37* 39 42*

25 39ij 37* 39 42*

4

39 25* 37* 39 42*

5

39* 25* 37* 39 42*

6

39* 25* 37* 39* 42* 60ij

39* 25* 37* 39* 42* 60ij 79

39* 25* 37* 39* 42* 60i 86 95j 65 79

39* 25* 37* 39* 42* 60i 86j

39* 25* 37* 39* 42* 60ij

7

39* 25* 37* 39* 42* 60* 86ij

39* 25* 37* 39* 42* 60* 79 95i 65 86j

39* 25* 37* 39* 42* 60* 79 86i 65j 95

39* 25* 37* 39* 42* 60*ij 95

8

39* 25* 37* 39* 42* 60* 79i 65j 86* 95

39* 25* 37* 39* 42* 60* 65 79ij 86* 95

9

39* 25* 37* 39* 42* 60* 65 79* 86* 95

10

39* 25* 37* 39* 42* 60* 65* 79* 86* 95

Результат

3965

1.4 Сортировки слиянием

Алгоритмы сортировки слиянием, как правило, имеют порядок O(N*log2(N)), но отличаются от других алгоритмов большей сложностью и требуют большого числа пересылок. Алгоритмы слияния применяются в основном, как составная часть внешней сортировки. Здесь же для понимания принципа слияния приводится простейший алгоритм слияния в оперативной памяти.

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

Важнейшей частью алгоритма является слияние двух упорядоченных множеств. Опишем эту часть алгоритма [1].

1. [Начальные установки]. Определить длины первого и второго исходных множеств - s1 и s2 соответственно. Установить индексы текущих элементов в исходных множествах i1 и i2 в 0. Установить индекс в выходном множестве j=0. (Нумерация элементов в множествах начинается с 0).

2. [Цикл слияния]. Выполнять шаг 3 до тех пор, пока i1<=s1 и i2<=s2.

3. [Сравнение]. Сравнить ключ i1-го элемента из 1-го исходного множества с ключом i2-го элемента из второго исходного множества. Если ключ элемента из 1-го множества меньше, то записать i1-ый элемент из 1-го множества на j-ое место в выходное множество и увеличить i1 на 1. Иначе - записать i2-ой элемент из 2-го множества на j-ое место в выходное множество и увеличить i2 на 1. Увеличить j на 1.

4. [Вывод остатка]. Если i1<=s1, то переписать часть 1-го исходного множества от i1 до s1 включительно в выходное множество. Иначе - переписать часть 2-го исходного множества от i2 до s2 включительно в выходное множество.

Программный пример 10 иллюстрирует сортировку попарным слиянием в ее обменном варианте - выходные множества формируются на месте входных.

/*===== Программный пример 10 - Сортировка слиянием ==*/

void SortConcatenation(int[] mas)

{

int i0, j0; //нач. индексы 1-го и 2-го мн-ва в общем массиве

int si, sj; //кол-во элементов в 1-м и 2-м сливаемых мн-вах

int i, j; //текущие индексы для 1-го и 2-го сливаемых мн-в

int k; // текущая верхняя граница слитого множества

int t;

int N = mas. Length; //длина исходного массива mas

si = 1; // начальный размер 1-го множества

while (si < N)

{ // цикл пока одно множество не составит весь массив

i0 = 0; // начальный индекс 1-го множества пары

while (i0 < N)

{ // цикл пока не пересмотрим весь массив

j0 = i0 + si; // начальный индекс 2-го множества пары

i = i0;

j = j0;

// размер 2-го мн-ва пары может ограничиваться концом массива

if (si >= N - j0)

sj = N - j0;

else

sj = si;

if (sj > 0)

{

k = i0; // начальный индекс слитого множества

//пока (i не дошел до верхней границы 1-го множества И

// j не дошел до верхней границы 2-го множества И

// 1-е множество не просмотрено полностью)

while ((i < i0 + si + sj) && (j < j0 + sj) && (i < j))

{ // если эл-т 1-го <= элемента 2-го, он остается на

// своем месте, но вых. множество расширяется иначе -

// освобождается место в вых. множестве и туда

// заносится элеиент из 2-го множества

if (mas[i] > mas[j])

{

t = mas[j];

for (int m = j; m > k; m--)

mas[m] = mas[m - 1];

mas[k] = t;

j++; // к следующему элемету во 2-м множестве

}

k++; // выходное множество увеличилось

i++; // если был перенос - за счет сдвига, если

// не было - за счет перехода эл-та в вых. мн-во

}

}

i0 = i0 + si * 2; // начало следующей пары

}

si = si * 2; // размер элементов пары увеличивается вдвое

}

}

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

Таблица 7 – Трассировка сортировки слиянием

Проход

Содержимое массива а

1

429

2

529

 

3

590

 

4

590

Результат

576

2 ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ

Задание 1 (6 баллов). Разобраться с примерами программной реализации алгоритмов сортировки, приведенными в проекте Sorting (пример реализации набора алгоритмов сортировки целых чисел). В частности, Вы должны быть способными объяснить методы сортировки соответствующими Вашему варианту, согласно таблице 8.

Задание 2 (+3 баллов). Составить программу, которая сортирует заданными методами массив, элементами которого являются объекты класса, заданного в соответствии с Вашим вариантом (см. таблицу 8).

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

Таблица 8 – Варианты заданий

Вариант

Прикладная область

Атрибуты информации

Алгоритм сортировки

1

Отдел кадров

фамилия сотрудника, имя, отчество, должность, стаж работы, оклад

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

Сортировка Шелла

2

Красная книга

вид животного, род, семейство, место обитания, численность популяции

Обменная сортировка простой выборкой,

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

3

Производство

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

Пузырьковая сортировка,

Пузырьковая сортировка вставками

4

Персональные ЭВМ

фирма-изготовитель, тип процессора, тактовая частота, емкость ОЗУ, емкость жесткого диска

Шейкер-сортировка,

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

5

Библиотека

автор книги, название, год издания, код УДК, цена, количество в библиотеке

Сортировка Шелла,

Поразрядная цифровая сортировка

6

Спутники

планет

название, название планеты-хозяина, год открытия, диаметр, период обращения

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

Сортировка упорядоченным двоичным деревом

7

Радиодетали

обозначение, тип, номинал, количество на схеме, обозначение возможного заменителя

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

Быстрая сортировка Хоара

8

Текстовые

редакторы

наименование, фирма-изготовитель, количество окон, количество шрифтов, стоимость

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

Шейкер-сортировка

9

Телефонная станция

номер абонента, фамилия, адрес, наличие блокиратора, задолженность

Обменная сортировка простой выборкой,

Сортировка упорядоченным двоичным деревом

10

Быт студентов

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

Пузырьковая сортировка,

Быстрая сортировка Хоара

11

Спортивные соревнования

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

Шейкер-сортировка,

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

Окончание табл. 8

Вариант

Прикладная область

Атрибуты информации

Алгоритм сортировки

12

Соревнование факультетов по успеваемости

факультет, количество студентов, средний балл по факультету, число отличников, число двоечников

Сортировка Шелла,

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

13

Занятость

студентов

фамилия студента, имя, отчество, факультет, вид работ, заработок

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

Сортировка Шелла

14

Сельскохозяйственные

работы

наименование с/х предприятия, вид собственности, число работающих, основной вид продукции, прибыль

Обменная сортировка простой выборкой,

Поразрядная цифровая сортировка

15

Сведения о

семье

фамилия студента, имя, отчество, факультет, специальность отца, специальность матери, количество братьев и сестер

Пузырьковая сортировка,

Пузырьковая сортировка вставками

Задание 2 (+3 балла). Провести анализ времени работы алгоритмов сортировки в зависимости от количества сортируемых данных и их изначальной упорядоченности. В качестве сортируемого массива используйте массив целых чисел.

Заполните массив случайными числами. Для этого следует использовать класс System::Random и его перегруженные методы Next(..). Например, для заполнения массива случайными числами из диапазона [0..1000) можно использовать следующий код

Random rnd = new Random();

for(i=0; i < N; i++)

mas[i] = rnd. Next(1000);

Для измерения времени используйте классы System::DateTime (описывает данные в формате «дата-время») и System::TimeSpan (описывает временной интервал). Для получения текущего времени (на момент начала сортировки и сразу по окончании сортировки) следует использовать статическое свойство Now класс DateTime.

DateTime begin= DateTime. Now;

// здесь делается сортировка элементов

// ...

DateTime end = DateTime. Now;

Если измерить значение времени перед вызовом сортировки, а затем после нее, то разность этих времен есть длительность сортировки. Для хранения длительности можно использовать объект класса TimeSpan.

TimeSpan dt = end - begin;

Интервал времени в классе TimeSpan хранится с точностью до «тиков» (1 «тик» = 100 наносекунд). Чтобы получить количество «тиков» у объекта класса TimeSpan следует использовать свойство Ticks, количество миллисекунд – свойство Milliseconds, количество секунд – свойство Seconds.

Console. WriteLine("Время выполнения {0} c {1} мс {2} мкс",

dt. Seconds, dt. Milliseconds,(dt. Ticks/10)%1000);

Примечание: для сортировки можно использовать массив, содержащий любое количество элементов. Главное условие, которое должно выполняться – время на сортировку, затрачиваемое любым из предложенных в лабораторной работе алгоритмов, поддается измерению (больше 0). Для небольших по размеру массивов (порядка 1 000 элементов) время сортировки на современных компьютерах очень маленькое, поэтому для таких массивов необходимо многократно повторить процесс сортировки (порядка 10 раз). При этом перед очередным вызовом функции сортировки необходимо восстановить исходный не отсортированный массив. Пример построения метода анализа алгоритма сортировки:

// 1. Заполнить массив для сортировки mas случайными значениями, используя System::Random и метод Next()

// 2. Сохранить копию не отсортиров. массива в переменную mas2

// 3. Зафиксировать время перед началом сортировки

DateTime begin= DateTime. Now;

// 4. Организовать цикл для многократной сортировки (повторять repeat раз)

for (i = 0; i < repeat; i++ )

{

// 4.1. Вызов функции сортировки для массива mas

// 4.2. Записать все элементы из не отсортированного массива mas2 в mas

}

// 5. Зафиксировать время после окончания сортировки

DateTime end = DateTime. Now;

// 6. Вычислить время, затраченное на сортировку

TimeSpan dt = end - begin;

// 7. Вывести это время на экран

Console. WriteLine("Время выполнения {0} c {1} мс {2} мкс", dt. Seconds, dt. Milliseconds,(dt. Ticks/10)%1000);

// 8. Повторить с 3 по 6 пункты для следующего алгоритма сортировки

Для того чтобы сравнение алгоритмов сортировки можно было считать корректным, каждый из них должен сортировать один и тот же массив значений!!!

Для исследования алгоритмов сортировки необходимо выполнить следующее:

1.  Определить массив из 1 000 целых чисел и заполнить его случайными значениями.

2.  Провести многократное выполнение сортировки массива всеми алгоритмами поочередно. Зафиксировать время, потраченное на сортировку.

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

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

5.  Повторить пункт 5 для массива изцелых чисел.

6.  Результаты полученных исследований оформите в виде таблицы 9 (можно в электронном виде).

Таблица 9 – Пример таблицы с результатами исследования алгоритмов сортировки


Алгоритм

сортировки

Размер массива

(1 000,

Упорядоченность

(случайная, обратная)

Время

сортировки

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

1 000

случайная

1 000

обратная

10 000

случайная

10 000

обратная

…

3 КОНТРОЛЬНЫЕ ВОПРОСЫ

1.  Сколько существует стратегий сортировок?

2.  Что нужно учитывать при выборе алгоритма сортировки?

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

4.  В чем заключается метод сортировки отбором?

5.  В чем заключается метод сортировки вставкой?

6.  В чем заключается метод сортировки разделением?

7.  В чем заключается метод быстрой сортировки?

8.  В чем заключается метод сортировки Шелла?

9.  Как зависит скорость сортировки от размера структуры данных для разных алгоритмов?

Литература

1.  Кнут, Д. Искусство программирования. В 3 т. Т. 3. Сортировка и поиск /Д. Кнут; 3-е изд.; пер. с англ. – М.: Издательский дом «Вильямс», 2000. – 800 с.

2.  Седжвик, Р. Фундаментальные алгоритмы на С++. Анализ. Структуры данных. Сортировка. Поиск: Пер. с англ. / Р. Седжвик. – К.: Издательство «ДиаСофт», 2001. – 688 с.

3.  Красиков, . Просто как дважды два / , . – М.: Эксмо, 2006. – 256 с.

4.  Далека, и структуры данных: учеб. пособие / , ­ко, , . – Харьков:ХГПУ, 2000. – 241 с.

5.  Портал «Информационно-коммуникационные технологии в образовании»: раздел «Структуры и алгоритмы обработки данных» [Электронный ресурс]. – 2010. – http:// www. ict. *****/lib/index. php? a=elib&c=getForm&r=resNode&d=mod&id_node=220.

СОДЕРЖАНИЕ

1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ.. 3

1.1 Сортировки выборкой. 4

1.2 Сортировки включением.. 10

1.3 Сортировки распределением.. 12

1.4 Сортировки слиянием.. 16

2 ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ.. 18

3 КОНТРОЛЬНЫЕ ВОПРОСЫ... 22

Литература. 22

Из за большого объема этот материал размещен на нескольких страницах:
1 2