ОТЧЕТ
По лабораторной работе №1
Факультет: ФКТИ
Группа: 1303
Выполнил: Феми-Оке Антони
Проверил:
Санкт-Петербург 2013
ü Цель лабораторной работы: Основной упор в задании делается на проведение экспериментального испытания (исследования) алгоритма (программной реализации). При этом оценивается эффективность алгоритма (его вариаций, разновидностей, модификаций)
ü Требование:
В каждой работе необходимо генерировать исходные данные, одним из подходящих способов:
Генерация: при случайной генерации задаются тип элементов, размер массива, диапазон значений элементов, наличие (или требование отсутствия) и доля совпадающих значений элементов, характеристика существующей упорядоченности (параметр упорядоченности); при генерации массива регулярной структуры также задаются соответствующие параметры (регулярная структура: уже упорядочен, обратно упорядочен)
· По результатам испытаний должны анализироваться:
1. зависимость времени выполнения и количества операций от размера массива,
2. соотношение измеренных и теоретически предсказанных значений,
3. сравнительные характеристики эффективности разных вариаций (модификаций) алгоритмов,
ü Содержание работы: Сортировка вставками (простые вставки (просмотр назад/вперед), бинарные вставки)
ü Анализ алгоритмов:
Сортировка простыми вставками (два варианта).
Пусть после нескольких шагов сортировки элементы x 0, x 1, …, xi -1 уже упорядочены (образуют сегмент): x 0< x 1 < …< xi-1.
Тогда на следующем шаге элемент xi вставляется в этот сегмент таким образом, что элементы x 0, x 1, …, xi оказываются упорядоченными (сегмент расширяется).
В конечном счете, получаем сегмент x 0, x 1, …, xn-1.
В первом варианте сортировки место вставки определяется последовательными сравнениями xi с xi-1, xi-2,…,во втором - последовательными сравнениями xi с x0, x1,…
ü Описание Алгоритма
Сортировка простыми вставками
На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. Приведенный ниже алгоритм использует именно эту стратегию выбора.
Этот процесс повторяется до тех пор, пока не будут вставлены все элементы. Например, при сортировке массива “ dcab” каждый проход алгоритма будет выглядеть следующим образом:
Начало dcab
Проход 1 cdab
Проход 2 acdb
Проход 3 abcd
· ПРОСМОТР ВПЕРЕД
| До | После | Описаниешага | ||
| Первый проход (проталкиваем второй элемент — 2 ) | ||||
| 5 2 4 3 1 | 2 5 4 3 1 | Алгоритм сравнивает второй элемент с первым и меняет их местами. | ||
| Второй проход (проталкиваем третий элемент — 4 ) | ||||
| 2 5 4 3 1 | 2 4 5 3 1 | Сравнивает третий со вторым и меняет местами | ||
| 2 4 5 3 1 | 2 4 5 3 1 | Второй и первый отсортированы, swap не требуется | ||
| Третийпроход (проталкиваемчетвертый — 3 ) | ||||
| 2 4 5 3 1 | 2 4 3 5 1 | Меняет четвертый и третий местами | ||
| 2 4 3 5 1 | 2 3 4 5 1 | Меняет третий и второй местами | ||
| 2 3 4 5 1 | 2 3 4 5 1 | Второй и первый отсортированы, swap не требуется | ||
| Четвертый проход (проталкиваем пятый элемент — 1 ) | ||||
| 2 3 4 5 1 | 2 3 4 1 5 | Меняет пятый и четвертый местами | ||
| 2 3 4 1 5 | 2 3 1 4 5 | Меняет четвертый и третий местами | ||
| 2 3 1 4 5 | 2 1 3 4 5 | Меняет третий и второй местами | ||
| 2 1 3 4 5 | 1 2 3 4 5 | Меняет второй и первый местами. Массивотсортирован. | ||
· ПРОСМОТР НАЗАД
| До | После | Описаниешага |
| Первый проход (проталкиваем второй элемент — 2 ) | ||
| 5 2 4 3 1 | 5 2 4 3 1 | Второй и первый отсортированы, swap не требуется. |
| Второй проход (проталкиваем третий элемент — 4 ) | ||
| 5 2 4 3 1 | 5 4 2 3 1 | Сравнивает третий со вторым и меняет местами |
| 542 3 1 | 542 3 1 | Второй и первый отсортированы, swap не требуется |
| Третийпроход (проталкиваемчетвертый — 3 ) | ||
| 5 4 2 3 1 | 5 4 3 21 | Меняет четвертый и третий местами |
| 5 432 1 | 5 432 1 | третий и второй отсортированы, swap не требуется |
Алгоритма бинарной вставкы
На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию с помощью понятияБинарного поиск, до тех пор, пока набор входных данных не будет исчерпан.Допутим у нас набор элементов(5,3,1,4),мы сортируем по частям и Мы работаем с тремя точками.Первая точка(low-это всегда позиция первого элемента),вторая точка(Mid-это позиция элемента в середине) и третья точка(high-это позиция последнего элемента в текующей частью с которой мы работаем). Сначало,берём второй элемент(3)и находим позицию элемента в середине(значит элемента междупервом и втором).В этом случае,позиция элемента в середине будет 0(5).сейчасlow=0,high=1, и mid=0.Дальше посмотрим если второй элемент меньше или больше первого.Если меньше мы концентрируем поиск на левой стороне(тогда high=midи Lowне меняется)и процесс рекурсивно продолжается до тех пор Low=highили набор отсортирован.Если больше мы концентрируем поиск на правой стороне(тогдо low=midи highне меняется) и процесс рекурсивно продолжается до тех пор Low=highили набор отсортирован.После того,как мы нашли правильную позицию вторго элемента мы положим его на этой позицию и берём следующий эелемент до тех пор, пока набор входных данных не будет исчерпан.
Текстпрограммы
Sort.cpp
#include<iostream>
#include"time.h"
#include<conio.h>
#include"sorting.h"
usingnamespacestd;
char B[500];
int E[100],F[100],G[100],H[100],I[100],J[100],K[100],L[100],M[100];
int j=0;
int s=0;
int v=0;
clock_t a;
int main(){
restart:
system("cls");
sort<char>sor;
sort<int> sor1;
int h=sor1.size1();
cout<<"MENU\n";
cout<<"1)SORTING AN ARRAY USING FORWARD INSERTION SORT\n";
cout<<"2)SORTING AN ARRAY USING BACKWARD INSERTION SORT\n";
cout<<"3)SORTING AN ARRAY USING BINARY INSERTION SORT\n";
cout<<"4)ANALYSIS\n";
cout<<"5)EXIT.\n";
cout<<"Pls enter your choice:\n";
char y;
cin>>y;
switch(y){
case'1':
cout<<"SORTING AN ARRAY USING FORWARD INSERTION SORT.\n";
cout<<"CREATE AN ARRAY BY:\n";
cout<<"a)RANDOM GENERATION.\n";
_getch();
int k;
srand (time(NULL));
k=rand() % 2 + 1;
if(k==1){
sor.random_generation_of_array1(B);
sor.output_Array(B);
cout<<endl;
cout<<"Sorting the array using insertion sort.\n";
sor.Forward_insertionsort(B);
cout<<"The array has been sorted!!\n";
sor.output_Array(B);
cout<<endl;
cout<<"Number of elemnts: "<<sor.size1()<<endl;
E[j]=sor.size1();
cout<<"Number of swaps: "<<sor.iteration<<endl;
F[j]=sor.iteration;
cout<<"Execution time: "<<sor1.t<<" ms"<<endl;
G[j]=sor1.t;
j++;
}else{
int L[500];
sor1.random_generation_of_array(L);
sor1.output_Array(L);
cout<<endl;
cout<<"Sorting the array using insertion sort.\n";
sor1.Forward_insertionsort(L);
cout<<"The array has been sorted!!\n";
sor1.output_Array(L);
cout<<endl;
cout<<"Number of elemnts: "<<sor1.size1()<<endl;
E[j]=sor1.size1();
cout<<"Number of swaps: "<<sor1.iteration<<endl;
F[j]=sor1.iteration;
cout<<"Execution time: "<<sor1.t<<" ms"<<endl;
G[j]=sor1.t;
j++;
}
break;
case'2':
cout<<"SORTING AN ARRAY USING BACKWARD INSERTION SORT.\n";
cout<<"CREATE AN ARRAY BY:\n";
cout<<"a)RANDOM GENERATION.\n";
_getch();
int p;
srand (time(NULL));
p=rand() % 2 + 1;
if(p==1){
sor.random_generation_of_array1(B);
sor.output_Array(B);
cout<<endl;
cout<<"Sorting the array using insertion sort.\n";
sor.backward_insertionsort(B);
cout<<"The array has been sorted!!\n";
sor.output_Array(B);cout<<endl;
cout<<"Number of elemnts: "<<sor.size1()<<endl;
H[s]=sor.size1();
cout<<"Number of swaps: "<<sor.iteration<<endl;
I[s]=sor.iteration;
cout<<"Execution time: "<<sor1.t<<" ms"<<endl;
J[s]=sor1.t;
s++;
}else{
int R[500];
sor1.random_generation_of_array(R);
sor1.output_Array(R);
cout<<endl;
cout<<"Sorting the array using insertion sort.\n";
sor1.backward_insertionsort(R);
cout<<"The array has been sorted!!\n";
sor1.output_Array(R);cout<<endl;
cout<<"Number of elemnts: "<<sor1.size1()<<endl;
H[s]=sor1.size1();
cout<<"Number of swaps: "<<sor1.iteration<<endl;
I[s]=sor1.iteration;
cout<<"Execution time: "<<sor1.t<<" ms"<<endl;
J[s]=sor1.t;
s++;
}
break;
case'3':
cout<<"sorting an array using binary insertion sort.\n";
int R[500];
sor1.random_generation_of_array(R);
sor1.output_Array(R);
cout<<endl;
cout<<"Sorting the array using binary insertion sort.\n";
sor1.BinaryInsertionSort(R);
cout<<"The array has been sorted!!\n";
sor1.output_Array(R);cout<<endl;
cout<<"Number of elemnts: "<<sor1.size1()<<endl;
K[v]=sor1.size1();
cout<<"Number of swaps: "<<sor1.iteration<<endl;
L[v]=sor1.iteration;
cout<<"Execution time:t: "<<sor1.t<<" ms"<<endl;
M[v]=sor1.t;
v++;
break;
case'4':
cout<<endl<<endl;
cout<<"Analysing for Forward insertion sort.\n\n";
tony<<"Analysing for Forward insertion sort.\n\n";
cout<<"Analysis:\n";
tony<<"Analysis:\n";
for(int y=0;y<j;y++){
cout<<"Size of array:"<<E[y]<<"\t|\t"<<"Number of swaps:\t"<<F[y]<<"\t|\t"<<"Execution time:"<<G[y]<<"\t|\t"<<"Number of swaps in the best case:"<<E[y]-1<<"\t|\t"<<"Number of swaps in the worse case:"<<E[y]*(E[y]-1)/2<<endl;
tony<<"Size of array:"<<E[y]<<"\t|\t"<<"Number of swaps:\t"<<F[y]<<"\t|\t"<<"Execution time:"<<G[y]<<"\t|\t"<<"Number of swaps in the best case:"<<E[y]-1<<"\t|\t"<<"Number of swaps in the worse case:"<<E[y]*(E[y]-1)/2<<endl;
}
cout<<endl<<endl;
cout<<"Analysing for Backward insertion sort.\n\n";
tony<<"Analysing for Backward insertion sort.\n\n";
cout<<"Analysis:\n";
tony<<"Analysis:\n";
for(int y=0;y<s;y++){
cout<<"Size of array:"<<H[y]<<"\t|\t"<<"Number of swaps:"<<I[y]<<"\t|\t"<<"Execution time:"<<J[y]<<"\t|\t"<<"Number of swaps in the best case:"<<H[y]-1<<"\t|\t"<<"Number of swaps in the worse case:"<<H[y]*(H[y]-1)/2<<endl;
tony<<"Size of array:"<<H[y]<<"\t|\t"<<"Number of swaps:"<<I[y]<<"\t|\t"<<"Execution time:"<<J[y]<<"\t|\t"<<"Number of swaps in the best case:"<<H[y]-1<<"\t|\t"<<"Number of swaps in the worse case:"<<H[y]*(H[y]-1)/2<<endl;
}
cout<<endl<<endl;
cout<<"Analysing for Binary insertion sort.\n\n";
tony<<"Analysing for Binary insertion sort.\n\n";
cout<<"Analysis:\n";
tony<<"Analysis:\n";
for(int y=0;y<v;y++){
cout<<"Size of array:"<<K[y]<<" \t|\t"<<"Number of swaps:"<<L[y]<<" \t|\t"<<"Execution time:"<<M[y]<<endl;
tony<<"Size of array:"<<K[y]<<" \t|\t"<<"Number of swaps:"<<L[y]<<" \t|\t"<<"Execution time:"<<M[y]<<endl;
}
Break;
case'5':
exit(0);
break;
default:
break;
}
cout<<endl;
_getch();
goto restart;
system("pause");
}
Sorting.h
#include<iostream>
#include<fstream>
usingnamespacestd;
ofstream tony("cool.txt");
template<class T>
class sort{
public:
int iteration;
sort(){
iteration=0;
}
double t;
int size;
T A[500];
int size1();
void swap1(T &a,T&b);
voidForward_insertionsort(T A[500]);
voidbackward_insertionsort(T A[500]);
voidrandom_generation_of_array(T A[500]);
void sort<T>::random_generation_of_array1(T A[500]);
voidoutput_Array(T A[500]);
intBinarySearch (T A[500], int low, int high, int key);
voidBinaryInsertionSort (T A[500]);
};
template<class T>
int sort<T>:: BinarySearch (T A[500], int low, int high, int key){
int mid;
if (low == high){
return low;
}
mid = low + ((high - low) / 2);
if (key > A[mid]){
returnBinarySearch (A, mid + 1, high, key);
}
elseif (key < A[mid]){
returnBinarySearch (A, low, mid, key);
}
return mid;
}
template<class T>
void sort<T>::BinaryInsertionSort (T A[500]){
a=clock();
int n;
n=size1();
int ins, i;
inttmp;
for (i = 1; i< n; i++) {
ins = BinarySearch (A, 0, i,A[i]);
if (ins <i) {
tmp = A[i];
memmove (A + ins + 1, A + ins, sizeof (int) * (i - ins));
A[ins] = tmp;
iteration++;
}
}
t=(double)(clock()-a);
}
template<class T>
int sort<T>:: size1(){
srand (time(NULL));
size=rand() % 50000 + 3;
return size;
}
template<class T>
void sort<T>::random_generation_of_array1(T A[500]){
size=size1();
for(inti=0;i<size;i++){
int n = rand() % 26;
char c = (char)(n+65);
A[i]=c;
}
}
template<class T>
void sort<T>::random_generation_of_array(T A[500]){
size=size1();
for(inti=0;i<size;i++){
A[i]=(rand()%100-size)+1;
}
}
template<class T>
void sort<T>::swap1(T &a,T&b){
T temp;
temp=a;
a=b;
b=temp;
}
template<class T>
void sort<T>::Forward_insertionsort(T A[500]){
a=clock();
for(inti=0;i<size;i++){
for(int j=i;j>=0;j--){
if(A[j]<A[j-1]){
swap1(A[j],A[j-1]);
iteration++;
}
}
}
t=(double)(clock()-a);
}
template<class T>
void sort<T>::backward_insertionsort(T A[500]){
a=clock();
for(inti=0;i<size;i++){
for(int j=i;j>=0;j--){
if(A[j]>A[j-1]){
swap1(A[j],A[j-1]);
iteration++;
}
}
}
t=(double)(clock()-a);
}
template<class T>
void sort<T>::output_Array(T A[500]){
cout<<"The elements of the array are:\n";
for(inti=0;i<size;++i){
cout<<A[i]<<"\t";
}
}
ü Пример Анализ
ü Блок схема:
ü ВЫВОД
Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время выполняется сортировка. Также на время выполнения влияет исходная упорядоченность массива.