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

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

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

Теоретическая часть

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

Важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:

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

· Внешняя сортировка оперирует запоминающими устройствами большого объёма, но не с произвольным доступом, а последовательным (упорядочение файлов), то есть в данный момент "виден" только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным во внешней памяти производится намного медленнее, чем операции с оперативной памятью. Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим; объём данных не позволяет им разместиться в ОЗУ.

Рассмотрим методы сортировки:

· пузырек;

· отбор;

· вставка;

· Шелл;

· быстрая.

Сортировка "пузырьком"

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

void SORT :: bubble()

{

long a,b;

short int t;

if(!KeMas){

ErrorCode=4;

ShowMsg();

return;

}

for(a=1; a<KeMas; a++)

for(b=KeMas-1; b>=a; b--)

if(Mas[b-1] > Mas[b]){t=Mas[b-1]; Mas[b-1]=Mas[b]; Mas[b]=t;}

return;

}

Сортировка "вставкой"

void SORT :: insert()

{

long a,b;

short int t;

if(!KeMas){

ErrorCode=7;

ShowMsg();

return;

}

for(a=1; a<KeMas; a++){

t=Mas[a];

for(b=a-1;b>=0 && t<Mas[b]; b--)Mas[b+1]=Mas[b];

Mas[b+1]=t;

}

return;

}

Сортировка "отбором"

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

Просматривая всю последовательность, отбираем минимальный элемент и если на i-ом шаге этот элемент расположен в позиции отличной от i, то меняем i-ый элемент с минимальным местами.

void SORT :: select()

{

long a,b,c;

bool flag;

short int t;

if(!KeMas){

ErrorCode=6;

ShowMsg();

return;

}

for(a=0; a<KeMas-1; a++){

flag=false;

c=a;

t=Mas[a];

for(b=a+1; b<KeMas; b++)

if(Mas[b] < t){c=b; t=Mas[b]; flag=true;}

if(flag){Mas[c]=Mas[a]; Mas[a]=t;}

}

return;

}

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

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

Доказано, что наихудшая временная сходимость - степень двойки.

void SORT :: Shell()

{

long gap,i,j;

short int t;

if(!KeMas){

ErrorCode=8;

ShowMsg();

return;

}

for(gap=KeMas/2; gap>0; gap/=2)

for(i=gap; i<KeMas; i++)

for(j=i-gap; j>=0 && Mas[j]>Mas[j+gap]; j-=gap){

t=Mas[j]; Mas[j]=Mas[j+gap]; Mas[j+gap]=t;

}

}

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

"Быстрая" сортировка является самым быстрым алгоритмом из всех рассмотренных; относится к классу перестановочных.

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

Идея - изначально массив делится на 2 части. Компаранд может выбираться случайно, или осреднением некоторой части сортируемого, или берётся экстремум из массива (наихудший случай). Оптимально выбрать компаранд, как значение расположенное точно в середине диапазона значений. Если выбирается срединный элемент, то временная сложность log2 N алгоритм бинарный компаранд

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

void SORT :: quick()

{

if(!KeMas){

ErrorCode=9;

ShowMsg();

return;

}

qs(Mas,0,KeMas-1);

}

void SORT :: qs(short int *A, long left, long right)

{

long i,j;

int x,y;

i=left; j=right;

x=A[(left+right)/2];

do

{

while(A[i] < x && i<right) i++;

while(x< A[j] && j > left)j--;

if(i <= j){

y=A[i];

A[i]=A[j];

A[j]=y;

i++; j--;

}

}while(i<=j);

if(left < j) qs(A,left,j);

if(i < right) qs(A,i,right);

}

Постановка задачи

Написать программу на языке C++, в которой будут описываться классы сортировок. Провести сравнительный анализ времен сортировки, проведенной различными методами над целочисленной последовательностью данных длиной N, в зависимости от N.

Описание классов

Класс обеспечивает автоматический выбор seed-значения, если параметром конструкции выступает пустота и пользователь получает независимые друг от друга псевдослучайные последовательности. Если же в качестве параметра задавать одно и то же значение, то при каждом обращении случайная последовательность повторяется.

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

Объявление класса RandomNumber:

#ifndef CL_RANDOM_H

#define CL_RANDOM_H

typedef unsigned long UL;

class RandomNumber {

public:

RandomNumber(UL S = 0); //ГСЧ в диапазоне от 0 до n-1

unsigned short int Random(UL n); //ГСЧ в диапазоне [0..1]

double fRandom(void);

public: // constants

static const UL maxshort = 65535L;

static const UL multipier = 1194211693L;

static const UL adder = 12345L;

private:

UL randSeed;

};

#endif

Класс сортировки

Класс SORT имеет следующие методы

SORT(unsigned long seed);

~SORT(void);

long ShowKeIsxMax(void);

void ShowMsg(void);

short int GetErrorCode(void);

void InitMas(long N);

void ProvSort(void);

void bubble(void);

void select(void);

void insert(void);

void Shell(void);

void quick(void);

void qs(short int *A, long left, long right);

SORT(unsigned long seed) - конструктор класса

long ShowKeIsxMax(void) - возвращает в качестве своего значения максимальное количество элементов массива для сортировки.

void ShowMsg(void) - метод в качестве значений выдает текст ошибки по ее коду (коду ошибки)

short int GetErrorCode(void) - методо возвращает в качестве своего значения код ошибки.

void InitMas(long N) - заполнение массива выборки N элементов из массива генеральной совокупности.

void ProvSort(void) - проверка массивов на 2 ошибки, ошибку захвата памяти и ошибку сортировки.

void bubble(void) - метод реализующий метод сортировки пузырьком.

void select(void) - метод реализующий метод сортировки выборкой

void insert(void) - метод реализующий метод сортировки вставкой

void shell(void) - метод реализующий метод сортировки Шелла.

void qs(void) - метод реализующий метод быстрой сортировки

void quick() - метод в котором происходит проверка массива данных для метода qs.

Анализ времен сортировок