Сортировка подсчетом

Обменная сортировка

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

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

1.2 Сортировка подсчетом

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

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

Метод пузырька - наиболее наглядный метод обменной сортировки, при котором последовательно выполняются сравнения соседних записей и в случае если ключ первого больше ключа второго, эти записи переставляются местами. Затем сравниваются и так далее, до тех пор, пока все записи не будут упорядочены. Алгоритм метода обменной сортировки с выбором (С) представлен ниже:

С_1 установить индекс верхнего элемента B = N

C_2 [цикл по j] установить t = 0. если В = 0 то перейти к шагу С_4, иначе выполнить шаг С_3 при j = 1 .. (B-1), затем перейти к шагу С_4.

C_3 сравнить если , то поменять местами установить t =j

C_4 если t = 0, то завершить алгоритм, иначе установить В = t и перейти к шагу С_2.

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

 (1.4)

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

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

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

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

Вновь возвращаемся к алгоритму D, рассмотренному в разделе 1.5:

D_1. [цикл по j] Выполнить шаги D_2, D_3 при j = 1 .. N

D_2. Найти наименьший из ключей , пусть это будет

D_3. Взаимозаменить и

Очевидно, время выполнения этого алгоритма зависит от числа элементов N, числа сравнений C, и числа «правосторонних минимумов» MИсследование алгоритма простого выбора «Сортировка и выбор» Д. Кнут [1].. Число сравнений в данном алгоритме не зависит от значений ключей и равно:

(2.1)

Число М будет переменной величиной:

(2.2)

Исходя из этого среднее время выполнения такого алгоритма:

(2.3)

Иначе можно ссылаться на порядок числа пересылокМетод выбора «Методы сортировки и поиска» С.Д. Кузнецов [2]. . В худшем случае оно равно , в то время как средний порядок числа пересылок равен, что соответствует формуле (1.1). Это показывает, что метод простого выбора выгоден, несмотря на свою неизысканность, что выделяет его из ряда прочих методов внутренней сортировки.

Далее рассмотрим способы усовершенствования метода простого выбора. Обратимся снова к алгоритму D. Рассмотрим для начала его второй шаг. Можно ли каким-либо образом усовершенствовать способ поиска минимума? В общем - нет. В любом алгоритме поиска минимума, основанном на сравнении пар, необходимо выполнить как минимум n-1 сравнений. Значит ли это, что скорость выполнения алгоритма, основанного на сравнении пар, будет пропорциональна ? В общем - нет. По крайней мере, в нашем алгоритме имеется еще и вторая часть. И даже простое ее усовершенствование приведет к ощутимому результату. Рассмотрим, например последовательность из 16 чисел, которую необходимо отсортировать (рис. 1).

Рисунок 1 Пример сортировки улучшенным методом выбора

алгоритм сортировка шаблон функция

Проведем довольно простое усовершенствование: разобьем 16 чисел на четыре группы, по четыре числа в каждой. Теперь поиск минимума будет производиться для каждой группы. После этого поиск минимума происходит среди минимальных элементов каждой из групп. На следующем шаге цикла требуется повторить поиск минимума уже только в одной группе и сравнить его с уже имеющимися элементами из других групп; и так далее до того, пока не останется элементов для сравнения. Конечно, этот способ требует более сложного алгоритма и дополнительной памяти для области вывода. Но, если N - точный квадрат, то массив разбивается на vN групп, по vN элементов в каждой. Таким образом, каждый выбор (кроме первого) требует vN-1 сравнений, плюс vN-1 сравнений среди наименьших элементов групп. Тогда скорость работы алгоритма получается порядка O(NvN), что в сравнении с гораздо предпочтительней.

Такой метод был назван метод квадратичного выбора и впервые был опубликован в 1956 году Э.Х. Френдом. Автор обобщил эту идею и описал возможность создания метода кубического выбора (массив делится на групп, по подгрупп с элементами), выбора четвертой степени и т. д. Итак, Френд пришел к выбору n-ой степени, который отражается в методе выбора из бинарного дерева.

Этот весьма любопытный метод напоминает систему турнира на выбывание. Для определения минимального элемента при представлении сортировки в виде дерева происходит за сравнений. А для определений минимума из оставшихся с каждым шагом требуется не более сравнений. Итого суммарная скорость выполнения алгоритма будет равна приблизительно . Но с другой стороны для реализации такого метода потребуется дополнительный массив с индексами вышедших вверх элементов после каждого круга сравнений, так как та запись, в которой он располагался до этого, будет заменена на бесконечность; к тому же потребуется и дополнительная область вывода. Таким образом, встает вопрос: можно ли обойтись без замены элементов на бесконечности и тем самым избежать довольно больших затрат памяти? Решением этого вопроса является метод, представленный ниже.

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

, (2.4)

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

2.2 Реализация алгоритма

Для реализации алгоритма сортировки посредством простого выбора (алгоритм D) мы будем использовать язык программирования C++. Для этого составим блок-схему нашего алгоритма с использованием цикла с заданным числом повторений (рис 2). Данный алгоритм будет сортировать массив array, размера size в порядке неубывания. Для реализации алгоритма потребуется использовать один вложенный цикл, реализующий поиск минимума. Как видно на схеме этот цикл (блок 5) производит поиск минимума только среди элементов, которые еще не были выбраны - это позволяет избежать замены выбранных элементов на бесконечность. Блок 7 реализует перестановку выбранного минимума с первым элементом рассматриваемого подмассива. На следующем шаге главного цикла происходит установка счетчика count на элемент вперед и инициализация переменной min значением из подмассива, огражденного слева элементом массива с индексом, соответствующим значению счетчика.

Рисунок 2 - Блок-схема алгоритма сортировки посредством простого выбора

Теперь перейдем непосредственно к кодированию этого алгоритма на языке C++ с помощью компилятора C++Builder 6. Для реализации тестирования нашего алгоритма необходимо использовать шаблон функции С++. Реализация такого шаблона представлена в программе 1.

Программа 1.

#include <stdio.h> // подключение модулей

#include <dos.h> // ……………..

#include <time.h> // ……………..

template < class Type, int size > // объявление шаблона

int sort( Type (&array)[size] ) // объявление функции

{

struct time t; // объявление переменной типа time

int t1, t2, ti; // объявление переменных для расчета времени

работы цикла 1

gettime( &t ); // возвращение системного времени

t1 = t.ti_hund; // запись сотых долей секунды системного времени в

переменную t1

int k = 0, j = 0; // объявление счетчика

Type min = array[0], buf; // объявление переменных для поиска

минимума и перестановки элементов

for( int x = 0; x < size; ++x ){ // цикл 1

k = x; // установка счетчика

min = array[x]; // установка нового значения минимума

for( int i = x+1; i < size; ++i ) // цикл 2 для поиска минимума в

массиве

if( min >= array[i] ){

min = array[i];

j = i; // запоминание позиции минимума в массиве

}

buf = array[k]; // перестановка минимума на позицию k

array[k] = array[j]; //

array[j] = buf; //

}

gettime( &t ); // получение системного времени

t2 = t.ti_hund; // запись сотых долей секунды

системного времени в переменную t2

ti = abs( t2 -t1 ); // вычисление времени выполнения цикла 1

return ti;

}

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

Наша функция sort будет не только сортировать массив, но и возвращать время сортировки в формате сотых долей секунды. Поэтому для проведения тестирования нашего алгоритма далее в программе 2 с помощью функции main мы будем конкретизировать наш шаблон.

Программа 2.

#include <iostream.h>

#include <string.h>

#include <math.h>

int main()

{

// задание переменных для вычисления среднего времени

int inttime[15];

float avtime = 0;

// задание размера сортируемого массива

const int size = 100;

// заполнение массива целых чисел

int ia[size];

for(int x = 0; x < size; ++x ){

randomize();

ia[x] = random( 100 );

}

// конкретизация шаблона для массива типа int

cout << "sort time for ia[" << size << "] { ";

for(int x = 0; x < 15; ++x ){

inttime[x] = sort( ia );

cout << inttime[x] << " ";

avtime = avtime + inttime[x];

}

cout << "} average time: " << avtime/15 << endl;

float fa[size];

for(int x = 0; x < size; ++x ){

randomize();

fa[x] = log( random( 100 ) + 1 );

}

// конкретизация шаблона для массива типа float

avtime = 0;

cout << "sort time for fa[" << size << "] { ";

for (int x = 0; x < 15; ++x ){

inttime[x] = sort( fa );

cout << inttime[x] << " ";

avtime = avtime + inttime[x];

}

cout << "} average time: " << avtime/15 << endl;

char ca[size];

for (int x = 0; x < size; ++x ){

randomize();

ca[x] = random( 64 ) + 62;

}

// конкретизация шаблона для массива типа char

avtime = 0;

cout << "sort time for ca[" << size << "] { ";

for (int x = 0; x < 15; ++x ){

inttime[x] = sort( ca );

cout << inttime[x] << " ";

avtime = avtime + inttime[x];

}

cout << "} average time: " << avtime/15 << endl;

string sa[size];

string samp = "deathisjustanotherpathonethatweallhavetotake";

int bag, fag;

string dag = "int";

for ( int x = 0; x < size; ++x ) {

bag = random( 44 );

fag = random( 44 );

sa[x] = dag + samp[bag] + samp[fag];

}

// конкретизация шаблона для массива типа string

avtime = 0;

cout << "sort time for sa[" << size << "] { ";

for (int x = 0; x < 15; ++x ){

inttime[x] = sort( sa );

cout << inttime[x] << " ";

avtime = avtime + inttime[x];

}

cout << "} average time: " << avtime/15 << endl;

cin.get();

return 0;

}

//---------------------------------------------------------------------------

2.3 Тестирование алгоритма

В данном разделе мы приступим к тому, для чего непосредственно создавалась наша программа - мы будем тестировать наш алгоритм. Для этого вновь обратимся к уже полученным формулам скорости выполнения алгоритма и попытаемся сопоставить полученные путем эксперимента данные с теоретическим обоснованием нашего алгоритма.

Будем уверены, что наша программа соответствует оптимизированному варианту алгоритма сортировки посредством простого выбора. Как мы отмечали, среднее время выполнения такого алгоритма составляет порядка . Также мы ссылались на число пересылок и отмечали, что его максимальное значение может быть порядка . И будем опираться на то, что зависимость скорости выполнения практически всех простых алгоритмов внутренней сортировки, которые можно считать рациональными, при большом количестве сортируемых элементов стремиться к порядку . Теперь вернемся к нашей программе. Путем варьирования константы size мы будем получать различные значения функции sort. Определив константу size значение 100, мы получим выведенное на консоль среднее из пятнадцати значений время сортировки для массивов различного типа (рис 4).

Рисунок 3 - Консоль вывода времени сортировки

Как видно 100 это слишком малое количество записей в массиве, поэтому в дальнейшем мы будем увеличивать это значение, начиная с 0 с шагом в 500. Запуская программу для каждого размера массива и выбирая среднее из полученных значений времени, мы получили следующую таблицу данных.

Таблица 1 - Время сортировки массива

3. Итоги анализа алгоритма

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

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

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

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

Заключение

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

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

Среднее время выполнения алгоритма

Наибольшее значение времени выполнения алгоритма

Объем занимаемой оперативной памяти

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

Специфичность области и среды применения алгоритма

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

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

Список используемых источников