Программа исследует эффективность сортировки слиянием Все работает правильно, вот только не получается сделать счетчики: В template <class T> void Vector<T>::Merge(int l,int m,int r)//слияние двух частей массива без обнуления kol_oper он отсчитывается от - 858993460, при его обнулении он выводит количество сортируемых элементов compare должно быть меньше, чем kol_oper, но принимает те же значения, а при обнулении так же равно количеству элементов | Код |
template <class T>
class Vector //класс-коллекция
{
template <class T>
class Elem //класс элемент данных коллекции
{
T *itm; //данное коллекции
public:
Elem(T *_imt) //конструктор
{
itm=_imt;
}
~Elem() //деструктор
{
delete itm; //удаление объекта из памяти
}
bool operator < (Elem <T>&anothElem) //операция сравнения двух объектов данных
{
if (*itm<*anothElem.itm) return true;
else return false;
}
bool operator > (Elem &anothElem) //операция сравнения двух объектов данных
{
if (*itm>*anothElem.itm) return true;
else return false;
}
friend class Vector; //разрешить классу Vector доступ к данным
};
private: //защищенная часть коллекции
Elem <T>**Array; //массив данных
int size0; //начальный размер массива
int size; //текущий размер массива
int amnt; //количество данных в массиве
int kol_oper;
int compare;
public:
Vector (int _size0); //конструктор класса (начальный размер массива)
Vector (const Vector <T> &anotVector); //конструктор копирования
~Vector (); //деструктор
int GetAmnt(); //получение текущего количества элементов
bool Resize(int newsize); //изменение размера массива на newsize
T &operator [](int i); //оператор доступа к данным по индексу
void Add(T *obj); //добавление объекта в конец массива
bool Insert(T *obj,int pos); //вставка объекта в массив по номеру
bool Delete(int pos); //удаление объекта из массива по номеру
void Show(); //вывод объектов массива на экран
void Merge(int l,int m,int r); //слияние двух частей массива
void SortSlianVosh(int l,int r); //восходящая сортировка слиянием
void SortSlianNish(int l,int r); //нисходящая сортировка слиянием
void Random(int kol); //заполнение случ. числами
void UnRandom(int kol); //заполнение упорядоченными числами
void Elem_Sort();
int get_kol_oper()
{
return kol_oper;
};
int get_compare()
{
return compare;
};
inline int min(int A,int B) //получение минимального из двух чисел
{
return (A<B) ? A:B; //вернуть минимальное
}
};
/////////////////////////////////////////////////////////////////////////////////////
/////////////////////////реализация методов класса Vector////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////
template <class T>
Vector<T>::Vector(int _size=10)//конструктор класса (начальный размер массива)
{
if(_size<=0) _size=10; //если введено отрицательное число
size=size0=_size;
amnt=0;
Array=new Elem<T>*[size]; //выделение памяти
}
/////////////////////////////////////////////////////////////////////////////////////
template <class T>
Vector <T>::Vector (const Vector <T> &anotVector)//конструктор копирования
{
delete Array; //удаление существующего массива
size=anotVector.size; //копирование переменных
size0=anotVector.size0;
amnt=anotVector.amnt;
Array=new Elem<T>*[size]; //выделение памяти под новый массив
for(int i=0;i<amnt;i++) //копирование объектов данных
Array[i]=new Elem<T>(anotVector.Array[i]->itm);
}
/////////////////////////////////////////////////////////////////////////////////////
template <class T>
void Vector <T>::Random(int kol) //заполнение случ. числами
{
T *buf;
amnt=0;
for(int i=0;i<kol;i++)
{
buf=new T;
*buf=rand();
Array[amnt++]=new Elem<T>(buf); //текущее случ. число
if(amnt==size) Resize((size*=2)); //если массив заполнился
}
}
/////////////////////////////////////////////////////////////////////////////////////
template <class T>
void Vector <T>::UnRandom(int kol) //заполнение числами от 1 до kol
{
T *buf;
amnt=0;
for(int i=0;i<kol;i++)
{
buf=new T;
*buf=i+1;
Array[amnt++]=new Elem<T>(buf); //текущее число
if(amnt==size) Resize((size*=2)); //если массив заполнился
}
}
/////////////////////////////////////////////////////////////////////////////////////
template <class T>
void Vector <T>::Elem_Sort() //элементарная сортировка
{
int fl=1; //флажок
while(fl==1) //если были перестановки
{
fl=0;
for(int i=0;i<amnt-1;i++) //пробег по массиву
{
Elem <T>*uk;
if(*Array[i]>*Array[i+1]) //след.элемент больше
{
//переставить элементы местами
fl=1;
uk=Array[i+1];
Array[i+1]=Array[i];
Array[i]=uk;
}
}
}
}
/////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////
template <class T>
Vector <T>::~Vector () //деструктор
{
delete Array; //удаление массива
}
/////////////////////////////////////////////////////////////////////////////////////
template <class T>
int Vector<T>::GetAmnt() //получение текущего количества элементов
{
return amnt; //возврат текущего количества элементов
}
/////////////////////////////////////////////////////////////////////////////////////
template <class T>
bool Vector<T>::Resize(int newsize)//изменение размера массива на newsize
{
if(newsize<=0) return false; //если размер отрицательный
int i;
Elem <T>**NewArray=new Elem<T>*[(size=newsize)]; //новый массив нужного размера
for(i=0;i<newsize&&i<amnt;i++) //копирование объектов
{
NewArray[i]=Array[i];
Array[i]=NULL;
}
amnt=i; //текущее количество элементов
delete Array; //удаление ненужного массива
Array=NewArray; //новый массив теперь - текущий
return true;
}
/////////////////////////////////////////////////////////////////////////////////////
template <class T>
T& Vector<T>::operator [](int i)//оператор доступа к данным по индексу
{
return *Array[i]->itm; //вернуть ссылку на нужный элемент
}
/////////////////////////////////////////////////////////////////////////////////////
template <class T>
void Vector<T>::Add(T *obj)//добавление объекта в конец массива
{
if(amnt==size) Resize(size*=2); //если в массиве нет места, увеличить его в два раза
Array[amnt++]=new Elem<T>(obj); //добавление объекта в конец массива
}
/////////////////////////////////////////////////////////////////////////////////////
template <class T>
bool Vector<T>::Insert(T *obj,int pos)//вставка объекта в массив по номеру
{
if(pos<=0||pos>amnt) return false;//если номер несуществующий
if(amnt==size) Resize(size*=2);//если в массиве нет места, увеличить его в два раза
for(int i=amnt;i>pos-1;i--) //освобождение нужной "ячейки" массива
Array[i]=Array[i-1];
Array[pos-1]=new Elem<T>(obj); //вставка на нужную (освободившуюся) позицию
amnt++;
return true;
}
/////////////////////////////////////////////////////////////////////////////////////
template <class T>
bool Vector<T>::Delete(int pos)//удаление объекта из массива по номеру
{
if(pos<=0||pos>amnt) return false;//если номер несуществующий
delete Array[pos-1]; //удаление объекта из памяти
for(int i=pos-1;i<amnt;i++) //сдвиг элементов массива на освободившуюся "ячейку"
Array[i]=Array[i+1];
amnt--;
return true;
}
/////////////////////////////////////////////////////////////////////////////////////
template <class T>
void Vector<T>::Show()//вывод объектов массива на экран
{
for(int i=0;i<amnt;i++)
cout<<*Array[i]->itm<<endl; //вывод объекта на экран
}
/////////////////////////////////////////////////////////////////////////////////////
template <class T>
void Vector<T>::SortSlianNish(int l,int r) //нисходящая сортировка слиянием
{
if (r<=l) return; //если пройден весь массив
int m=(r+l)/2; //деление текущего массива пополам
SortSlianNish(l,m); //рекурсивный вызов для первой половины
SortSlianNish(m+1,r);//рекурсивный вызов для второй половины
Vector<T>::Merge(l,m,r);//слияние половин массива
}
/////////////////////////////////////////////////////////////////////////////////////
template <class T>
void Vector<T>::Merge(int l,int m,int r)//слияние двух частей массива
{
int i,j;
//kol_oper=0;
//compare=0;
Elem <T>**arr=new Elem<T>*[amnt]; //временный массив
for(i=m+1;i>l;i--) arr[i-1]=Array[i-1]; //копирование первой половины
for(j=m;j<r;j++) arr[r+m-j]=Array[j+1]; //копирование второй половины
for(int k=l;k<=r;k++) //слияние половин массива
{
kol_oper++;
cout<<"K="<<kol_oper<<endl;
if(*arr[j]<*arr[i])
{
Array[k]=arr[j--];
compare++;
//cout<<"C="<<compare<<endl;
}
else
{
Array[k]=arr[i++];
compare++;
}
}
}
/////////////////////////////////////////////////////////////////////////////////////
template <class T>
void Vector<T>::SortSlianVosh(int l,int r)//восходящая сортировка слиянием
{
for(int m=1; m<=r-l; m=m+m) //размер сливаемых блоков (1..2..4..8..)
for(int i=l;i<r-m;i+=m+m) //размер упорядочиваемого блока
Merge(i,i+m-1,min(i+m+m-1,r)); //сливание соседних блоков
}
/////////////////////////////////////////////////////////////////////////////////////
|
управляющая подкреплена Помогите, пожалуйста, кто чем может 
Присоединённый файл ( Кол-во скачиваний: 5 )
Sort_6.cpp 2,24 Kb |
Проблема со счетчиками 
Загрузка ...
