SHARE
TWEET

Untitled

a guest May 6th, 2015 210 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cmath>
  4. #include <cstdlib>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. // Слияние упорядоченных частей массива в буфер temp
  10. int Merge(string *array, int left,int middle,int right){
  11.   int compare_count=0;
  12.  
  13.   int pos_left=left;// текущая позиция чтения из первой последовательности
  14.   int pos_right=middle+1;  // текущая позиция чтения из второй последовательности
  15.   int pos_temp=0;  // текущая позиция записи в temp
  16.  
  17.   int size = right-left+1; //размер доп.массива
  18.   string *temp = new string[size];
  19.  
  20.   // идет слияние, пока есть хоть один элемент в каждой последовательности
  21.   while (pos_left <= middle && pos_right <= right) {
  22.    
  23.     if ( array[pos_left]>array[pos_right] ){
  24.        temp[pos_temp] = array[pos_left];
  25.        pos_temp++;
  26.            pos_left++;
  27.  
  28.     }else{
  29.       temp[pos_temp] = array[pos_right];
  30.       pos_temp++;
  31.           pos_right++;
  32.  
  33.         }
  34.         compare_count++;
  35.   }
  36.   // одна последовательность закончилась
  37.   // копировать остаток другой в конец буфера
  38.   while (pos_right <= right){   // пока вторая последовательность непуста
  39.     temp[pos_temp] = array[pos_right];
  40.     pos_temp++;
  41.     pos_right++;
  42.   }
  43.  
  44.   while (pos_left <= middle){  // пока первая последовательность непуста
  45.     temp[pos_temp] = array[pos_left];
  46.     pos_temp++;
  47.     pos_left++;
  48.         }
  49.  
  50.   // скопировать буфер temp в array
  51.   for (pos_temp = 0; pos_temp < size; pos_temp++)
  52.     array[left+pos_temp] = temp[pos_temp];
  53.  
  54.   delete[] temp;
  55.  
  56.   return compare_count;
  57. }
  58.  
  59.  
  60. int NaturalMergeSort(string* array,int start,int end){
  61.         int count=0;
  62.  
  63.         if(start>=end)
  64.                 return 0;
  65.  
  66.                 for(int i=0;i<end-start;i++){
  67.                                         int middle = start;
  68.                                         int right = start;
  69.                                         //ищем первую группу
  70.                                         for (middle; middle < end-1; ++middle){
  71.                                                 count++;
  72.                                                 if(array[middle] < array[middle+1])
  73.                                                                 break;
  74.                                         }
  75.  
  76.                                         if(middle+1==end) //если прошли до конца - то сортирован
  77.                                                 break;
  78.                                         //ищем вторую группу
  79.                                         right = middle+1;
  80.                                         for (right; right < end-1; ++right){
  81.                                                 count++;
  82.                                                 if(array[right]<array[right+1])
  83.                                                         break;
  84.                                         }
  85.                                         //сливаем вторую группу
  86.                                         count+=Merge(array,start,middle,right);
  87.                                         //рекурсивно проходим оставщийся конец
  88.                                         count+=NaturalMergeSort(array,right,end);
  89.  
  90.                 }
  91.  
  92.         return count;
  93.        
  94. }
  95.  
  96.  
  97. void GenerateDataset(const char* filename,int num){
  98.         ofstream out(filename);
  99.         char n3[4]="";
  100.  
  101.         if(!out){
  102.                 cerr<<"File "<<filename<<" not create"<<endl;
  103.                 return;
  104.         }
  105.  
  106.         srand(time(0)*num);//что бы случайнее было
  107.  
  108.          for(int i=0;i<num;i++){// генерируем и записываем
  109.                 n3[0] = (char) (rand()%26+'A');
  110.                 n3[1] = (char) (rand()%26+'A');
  111.                 n3[2] = (char) (rand()%26+'A');
  112.                 out<<n3<<endl;
  113.         }
  114.         out.close();
  115. }
  116.  
  117. int SortDataset(const char *filename){
  118.  
  119.         vector<string> temp; //Временно, так как мы не знаем длину файла.
  120.        
  121.         int size = 0;
  122.  
  123.         ifstream in(filename); //открываем файл
  124.         int ret = 0;
  125.  
  126.         if(!in){//ошибка, если не открывается
  127.                 cerr<<"File "<<filename<<" not open!"<<endl;
  128.                 return -1;
  129.         }
  130.          while(!in.eof()){// загружаем в вектор
  131.                 string s;
  132.                 in>>s;
  133.                 temp.push_back(s);
  134.         }
  135.         in.close();//закрываем
  136.  
  137.         string *array = &temp[0]; //получаем ссылку из массива vector'а для передачи в метод
  138.         size = temp.size();
  139.         //sorting
  140.         ret = NaturalMergeSort(array,0,size-1);
  141.         //end sorting
  142.        
  143.         //gen new filename
  144.         string fname(filename);
  145.         fname+=".sort";
  146.         ofstream out(fname.c_str());
  147.  
  148.         if(!out){
  149.                 cerr<<"File "<<fname<<" not open!"<<endl;
  150.                 return -1;
  151.         }
  152.         //Записываем сортированный массив
  153.         for(int i=0;i<size;i++)
  154.                 out<<array[i]<<endl;
  155.  
  156.         out.close();
  157.         temp.clear();//ощищаем вектор и память
  158.        
  159.         return ret;
  160. }
  161. //для логарифма
  162. double Log2( double n )  
  163. {  
  164.     return log( n ) / log( 2 );  
  165. }
  166.  
  167. const int nums[10] = {8,16,32,64,128,256,512,1024,2048,4096};
  168.  
  169.  
  170. int main(){
  171.  
  172.         ofstream test_table("test_table.txt");
  173.         test_table<<"num\tTe\tT1\tT2\tTe/T1\tTe/T2"<<endl;
  174.  
  175.         char name[40];
  176.         double Te=0,T1=0,T2=0;
  177.        
  178.         for(int i=0;i<10;i++){
  179.                
  180.                 sprintf(name,"test/test_%d.txt",nums[i]);
  181.                 GenerateDataset(name,nums[i]);
  182.        
  183.                 Te = (double) SortDataset(name);
  184.                 T1 = nums[i]*nums[i];
  185.                 T2 = round(log2(nums[i])*nums[i]);
  186.                 test_table.precision(4);
  187.                 test_table<<nums[i]<<"\t"<<Te<<"\t"<<T1<<"\t"<<T2<<"\t"<<Te/T1<<"\t"<<Te/T2<<endl;
  188.         }
  189.        
  190.         test_table.close();
  191.  
  192.         return 0;
  193. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top