loser tree.cpp

外排序 对于海量数据进行快速排序 然后利用败者树进行归并的算法的一个模板

#include "funtion.h" 
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "iostream.h"
#include "time.h"
#define k 4 
#include "stack.h"



#define M 10 
 

FILE *fp[k + 1],*fx[k]; 

typedef int LoserTree[k]; 
 
typedef int ExNode, External[k+1]; 
 

External b; 
 

int input(int i, KeyType *a){
    int j = fscanf(fp[i], "%d ", a);
    if(j > 0){
      
        return 1;
    }else{
        return 0;
    }
}
 

void output(int i){
    fprintf(fp[k], "%d ", b[i]);
}

 

void Adjust(LoserTree ls, int s){ 
    int i, t;
     
 
    t = (s + k) / 2; 
    while(t > 0){
       
        if(b[s] > b[ls[t]]){
            i = s;
            s = ls[t]; 
            ls[t] = i;
        }
        t = t / 2;
    }
    ls[0] = s;
}
 

void CreateLoserTree(LoserTree ls){ 
    int i;
    b[k] = MINKEY;
     
   
    for(i = 0; i < k; ++i){
        ls[i] = k; 
    }
     
   
    for(i = k - 1; i >= 0; --i){
        Adjust(ls, i);
    }
}
 

void K_Merge(LoserTree ls, External b){ 
    int i, q;
     

    for(i = 0; i < k; ++i) {
        input(i, &b[i]);
    }
     
 
    CreateLoserTree(ls); 
     
    while(b[ls[0]] != MAXKEY){
      
        q = ls[0]; 
         
     
        output(q); 
         
     
        if(input(q, &b[q]) > 0){
          
            Adjust(ls,q); 
        } 
    }
     

    output(ls[0]); 
}
 

 
void main(){
    FILE *ip; 

    KeyType r;
    int i, j;
    char fname[k][8], fout[9] = "out.txt", s[3],fin[11]="input.txt";
    

	srand(time(0));
     
	int xx,num[4][200];  
   i=0;
    ip= fopen(fin, "w");

   for(int www=0;www<4;www++){
   for(int ww=0;ww<199;ww++)
   {
   num[www][ww]=rand()%100;
     fprintf(ip, "%d ", num[www][ww]);
   }
   num[www][199]=100;
    fprintf(ip, "%d ", num[www][ww]);
   }
 
  
  fclose(ip);

  





    for(i = 0; i < k; i++){ 
    
        itoa(i, s, 10); 
        strcpy(fname[i], "f");
        strcat(fname[i], s);
		strcat(fname[i], ".txt");
 }
		//ip = fopen("f11.txt", "w"); 
	//for(int i11=0;i11<200;i11++){

	
 
	//	fprintf(ip, "%d ", num[0][i11]); 

	//}







  /*for(i = 0; i < 2*k; i++){ 
    
        itoa(i, s, 10); 
        strcpy(fname1[i], "f");
        strcat(fname1[i], s);
		strcat(fname1[i], s);
	strcat(fname1[i], ".txt");}*/

// for(i = 0; i < k; i++){ 
	//  fp[i] = fopen(fname[i], "w");}
  //for(i= 0;i<2*k;i++){
  
   

 /* for(int u11=0;u11<200;u11++)
	   
		   {
	 // cout<<num[0][u11]<<endl;
		   fprintf(ip, "%d ", num[0][u11]);
		  cout<<endl;
	   
		   }*/
	   

   /*int u2=0,u11=0;
   for(i=0;i<2*k;i++)
   {

   
	   for(u2=0;u2<4;u2++)
   
   
	   {
	   
		   for(u11=0;u11<199;u11++)
	   
		   {
		   fprintf(ptr[i], "%d ", num[u2][u11]);
		   if(i==99) i++;
	   
		   }
	   
	   }

   }*/



	int j1,r1,p=0;
     

	LoserTree ls;

	Stack<int> stack1;

    for(int shit=0;shit<4;shit++){ 
	r1=199;
	p=0;
		
	stack1.push(r1);

	stack1.push(p); 
	while(!stack1.empty())

	{

		p=stack1.getTop();

        stack1.pop();
		r1=stack1.getTop();
         stack1.pop();
		j1=quicksort(num[shit],p,r1);

		if(j1+1<r1&&j1!=0)

		{

			stack1.push(r1);

			stack1.push(j1+1);

		}

		if(p<j1)

		{

			stack1.push(j1);

			stack1.push(p);

		}

	}
	}
//	stack1.~Stack();
/*int abc=0,bcd=0;
    for(;abc<k;abc++)
		for(;bcd<200;bcd++){
			cout<<num[abc][bcd];
		if(bcd%10==0)cout<<endl;}*/

		
		
		/*for(i = 0; i < k; i++){                        //0000000000000
		  fp[i] = fopen(fname[i], "w"); }
cout<<"1"<<endl;
for(i = 0; i < k; i++){  
    for(int ix = 0; ix < k; ix++)
	for(int ixx = 0; ixx <200; ixx++){  
		fprintf(fp[i], "%d ", num[ix][ixx]);}
	

	
	}*/

fx[0]= fopen("f0.txt", "w");
	for(int ixx = 0; ixx <200; ixx++){  
		fprintf(fx[0], "%d ", num[0][ixx]);}

	fx[1]= fopen("f1.txt", "w");
	for(ixx = 0; ixx <200; ixx++){  
		fprintf(fx[1], "%d ", num[1][ixx]);}
	
	fx[2]= fopen("f2.txt", "w");
	for(ixx = 0; ixx <200; ixx++){  
		fprintf(fx[2], "%d ", num[2][ixx]);}
	
	fx[3]= fopen("f3.txt", "w");
	for(ixx = 0; ixx <200; ixx++){  
		fprintf(fx[3], "%d ", num[3][ixx]);}

 for(i = 0; i < k; i++){
        fclose(fx[i]); 
    }



   for(i = 0; i < k; i++){                        //0000000000000
		  fp[i] = fopen(fname[i], "r"); //}
    
        //  for(i = 0; i < k; i++){  
      
        do{
            j = fscanf(fp[i], "%d ", &r);
         
        }while(j == 1);
    
         
      
        rewind(fp[i]); 
    }
     
  
    fp[k] = fopen(fout, "w"); 
     
   
    K_Merge(ls, b); 
     
 
    for(i = 0; i <= k; i++){
        fclose(fp[i]); 
    }
    // char aa;
   cout<<"ok"<<endl;
   //cin>>aa;
}