Файл: Анализ алгоритмов сортировок методом слияния.pdf

Пример продемонстрирован ниже

Пример. Исходный массив:

7 -2 0 -6 3 1 -5

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

1)после фазы слияния длина серии не меньше количества элементов в массиве;

2)на фазе слияния осталась ровно одна серия;

3)второй по счёту вспомогательный массив для однофазной сортировки остался пустым.

//Описание функции сортировки простым слиянием

void p_sort(int *Mas, int first, int last)

{

{

if (first<last)

{

p_sort(Mas, first, (first+last)/2);

//сортировка левой части

p_sort(Mas, (first+last)/2+1, last);

//сортировка правой части

sliv_mass(Mas, first, last);

//слияние двух частей

}

}

}

Листинг 1.Алгоритм сортировки простым слиянием

1.3 Алгоритм сортировки естественным слиянием

При использовании метода прямого слияния не принимается во внимание то, что исходный файл может быть частично отсортированным, т.е. содержать упорядоченные подпоследовательности записей. Серией называется подпоследовательность записей ai, a(i+1), ..., aj такая, что ak <= a(k+1) для всех i <= k < j, ai < a(i-1) и aj > a(j+1). Метод естественного слияния основывается на распознавании серий при распределении и их использовании при последующем слиянии.

Как и в случае прямого слияния, сортировка выполняется за несколько шагов, в каждом из которых сначала выполняется распределение файла A по файлам B и C, а потом слияние B и C в файл A. При распределении распознается первая серия записей и переписывается в файл B, вторая - в файл C и т.д. При слиянии первая серия записей файла B сливается с первой серией файла C, вторая серия B со второй серией C и т.д. Если просмотр одного файла заканчивается раньше, чем просмотр другого (по причине разного числа серий), то остаток недопросмотренного файла целиком копируется в конец файла A. Процесс завершается, когда в файле A остается только одна серия. Пример сортировки файла показан на рисунках 2 и 3.

Рис. 2 Первый шаг

Рис. 3 Второй шаг

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

1 3 14 | 6 8 9 | 2 4 5 7 11 | 10 16

Естественное слияние заканчивается тогда, когда:

1)на фазе слияния осталась ровно одна серия;

2)второй по счёту вспомогательный массив для однофазной сортировки после распределения серии остался пустым.

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

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

//Описание функции сортировки естественным слиянием

void sort (int q, int x[])

{

int k1, k2, st, u, fl;

int* tm1 = new int[q];

// временный массив 1

int* tm2 = new int[q];

// временный массив 2

int pos;

k1=0;

std::sort(x, x + q - 1);

while (k1 < q-1)

{

st=1;

fl=1;

pos=0;

while (fl==1)

{

u=0;

while ((x[u+st-1]<=x[u+st]) &&(u+st-1 < q)) // выбираем возрастающие цепочки элементов.

{

tm1[u]=x[u+st-1];

u++;

}

if ((x[u+st-1]>= x[u+st]) || (u+st-1 == q-1))

{

tm1[u]=x[u+st-1]; u++;

}

k1=u;

st=st+k1;

u=0;

while ((x[u+st-1]<=x[u+st]) &&(u+st-1 < q))

// аналогичным образом формируем второй массив

{

tm2[u]=x[u+st-1];

u++;

}

if ((x[u+st-1]>= x[u+st]) || (u+st-1 == q-1))

{

tm2[u]=x[u+st-1]; u++;

}

k2=u;

st=st+k2;

if (u > 0)

merge(k1, k2, tm1, tm2, x);

// сливаем эти два массива в один

if (st >= q) fl=0;

}

}

delete [] tm1;

delete [] tm2;

Листинг 2.Алгоритм сортировки естественным слиянием

1.4 Оценка сложности алгоритма

Единственного эффективнейшего алгоритма сортировки нет, ввиду множества параметров оценки эффективности:

• Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n²). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в O(n log n) сравнениях в среднем;
• Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.
• Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов.
• Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

2. Реализация алгоритмов сортировки слияниями

2.1 Программная реализация простого слияния

#include <stdio.h>

#include <iostream>

using namespace std;

void sliv_mass(int *Mas, int first, int last) //функция, сливающая массивы

{

int middle, start, final, j;//переменные целого типа

int *mas=new int[100];// описан указатель mas и ему присвоен адрес начала непрерывной области динамической памяти, выделенной с помощью оператора new:

middle=(first+last)/2; //вычисление среднего элемента

start=first;//начало левой части

final=middle+1;//начало правой части

for(j=first; j<=last; j++)//выполнять от начала до конца

if ((start<=middle)&&((final>last) || (Mas[start]<Mas[final])))

{

mas[j]=Mas[start];

start++;//увеличить start на 1

}

else

{

mas[j]=Mas[final];

final++;//увеличить final на 1

}

for (j=first; j<=last; j++)

Mas[j]=mas[j];//возвращение результата в список

delete[]mas;

};

void p_sort(int *Mas, int first, int last)//рекурсивная процедура сортировки

{

{

if (first<last)

{

p_sort(Mas, first, (first+last)/2);//сортировка левой части

p_sort(Mas, (first+last)/2+1, last);//сортировка правой части

sliv_mass(Mas, first, last);//слияние двух частей

}

}

}

void main()//главная функция

{

setlocale(LC_ALL, "Rus");

int i, n;

int *Mas=new int[100];

cout<<"Введите размер массива: ";

cin>>n;//вводим n с клавиатуры

for (i=1; i<=n; i++)

{

cout<<i<<" элемент: ";

cin>>Mas[i];

}

p_sort(Mas, 1, n);//вызов сортирующей процедуры

cout<<"Упорядоченный массив: ";//вывод упорядоченного массива

for (i=1; i<=n; i++)

cout<<Mas[i]<<" ";

delete []Mas;//освобождение памяти

system("pause");

}

Листинг 3. Исходный код модуля простое слияние.cpp

Скриншот данной программы приведен в приложении 2.

2.2 Программная реализация естественного слияния

#include <stdlib.h>

#include <iostream>

#include <stdio.h>

#include <time.h>

#include <algorithm>

#include <fstream>//подключаем библиотеку для работы с файлами

using namespace std;

int size=5;

ifstream r;

void merge(int k1, int k2, int *mass1, int *mass2, int *x) // слияние 2 массивов

{

int z1 = 0; int z2 = 0; int i;// счетчики позиций на временных массивах и в результирующем

for (unsigned int i = 0; i < k1 + k2; ++i)

{

if (z1 >= k1)

{

x[i] = mass2[z2++]; // сливаем по возрастанию элементов

} else if (z2 >= k2) {

x[i] = mass1[z1++];

} else {

if (mass1[z1] <= mass2[z2]) {

x[i] = mass1[z1++];

} else {

x[i] = mass2[z2++];

}

}

}

}

void sort (int q, int x[])

{

int k1, k2, st, u, fl;

int* tm1 = new int[q]; // временный массив 1

int* tm2 = new int[q]; // временный массив 2

int pos;

k1=0;

sort(x, x + q - 1);

while (k1 < q-1)

{

st=1;

fl=1;

pos=0;

while (fl==1)

{

u=0;

while ((x[u+st-1]<=x[u+st]) &&(u+st-1 < q)) // выбираем возрастающие цепочки элементов.

{

tm1[u]=x[u+st-1];

u++;

}

if ((x[u+st-1]>= x[u+st]) || (u+st-1 == q-1))

{

tm1[u]=x[u+st-1]; u++;

}

k1=u;

st=st+k1;

u=0;

while ((x[u+st-1]<=x[u+st]) &&(u+st-1 < q)) // аналогичным образом формируем второй массив

{

tm2[u]=x[u+st-1];

u++;

}

if ((x[u+st-1]>= x[u+st]) || (u+st-1 == q-1))

{

tm2[u]=x[u+st-1]; u++;

}

k2=u;

st=st+k2;

if (u > 0)

merge(k1, k2, tm1, tm2, x); // сливаем эти два массива в один

if (st >= q) fl=0;

}

}

delete [] tm1;

delete [] tm2;

}

int main()

{

setlocale(LC_ALL, "RUS");

cout<<"Размерность массива = "<<size<<endl;

int *x = new int [size];

int i;

r.open("D:\111\Естественное слияние\Естественное слияние\fail.txt");//открыли файл

cout<<"Исходный массив: ";

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

{

r>>x[i];

}

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

{

cout<<x[i]<<" ";

}

sort(size, x); // сортируем

cout<<endl;

cout<<"Отсортированный массив: ";

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

{

cout<<x[i]<<" ";

}// и ещё раз выводим

cout<<endl;

system("pause");

r.close();//закрыли файл

return 0;

}

Листинг 3. Исходный код модуля естественное слияние.cpp

Скриншот данной программы приведен в приложении 2.

3. Тестирование

3.1 Тестирование меню на корректность входных данных

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

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

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

По объекту тестирования:

• Функциональное тестирование;
• Тестирование производительности;
• Юзабилити-тестирование;
• Тестирование интерфейса пользователя;
• Тестирование безопасности;
• Тестирование локализации;
• Тестирование совместимости.

По знанию системы:

• Тестирование чёрного ящика;
• Тестирование белого ящика;
• Тестирование серого ящика

По степени автоматизации:

• Ручное тестирование;
• Автоматизированное тестирование;
• Полуавтоматизированное тестирование.

По степени изолированности компонентов:

• Компонентное (модульное) тестирование;
• Интеграционное тестирование;
• Системное тестирование.

По времени проведения тестирования:

• Альфа-тестирование;
• Бета-тестирование.

По признаку позитивности сценариев:

• Позитивное тестирование;
• Негативное тестирование.

По степени подготовленности к тестированию:

• Тестирование по документации;
• Тестирование ad hoc или интуитивное тестирование.

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

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

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

Данный вид пригодится при сравнении алгоритмов и выявлении наименее затратного по времени.

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

Таблица 1. Результаты корректности входных данных