第六章スタックソートの「Young氏行列(Young tableau)」(思考問題6-3)

このプログラムはYoung氏行列を用いてn*nの配列を並べ替える.
ここでは,挿入法によりYoung氏行列を確立し,次いで「戻りスタック要素を除去する」関数を呼び出して小さいものから大きいものへの配列を得ることに関する.全時間複雑度はO(n^3)であった.
ここで、Young氏行列に「1つの要素を挿入する」時間的複雑度はO(m+n)、mはYoung氏行列の行数、nはYoung氏行列の列数であり、Young氏行列を確立するにはn*n個の要素を挿入するにはO((n^2)*2 n)=O(n^3)である.
「戻りスタックトップ要素の除去」は、「スタック調整」関数を使用してYoung氏行列の性質を維持するため、時間的複雑度はO(m+n)である.
ソート関数YoungSortでは検索関数YoungSearchも呼び出されているが、これは実はソートとは何の関係もない.ソート前にYoung氏マトリクスを作成したので、便乗し、Young氏マトリクスを作成するとすぐにYoungSearchを呼び出して3つの数を検索した.このように書くと誤解しやすいことを知っています.この探索関数YoungSearch()の考え方は関数定義において詳細に説明されている.
詳細は、次のコードを参照してください.

#include <string.h>
#include <time.h>

#define BUFFER_SIZE 3

//Young      
void YoungMinHeapIfy(int (*a)[BUFFER_SIZE+1],int i,int j,int m,int n)
{
	int x=0;
	int y=0;
	int tmp=0;
	int min_i=0;
	int min_j=0;
	
	if(j+1<=n&&a[i][j]>a[i][j+1])
	{
		min_i=i;
		min_j=j+1;
	}
	else
	{
		min_i=i;
		min_j=j;
	}
	if(i+1<=m&&a[min_i][min_j]>a[i+1][j])
	{
		min_i=i+1;
		min_j=j;
	}
	if(min_i!=i||min_j!=j)
	{
		tmp=a[i][j];
		a[i][j]=a[min_i][min_j];
		a[min_i][min_j]=tmp;
		
		YoungMinHeapIfy(a,min_i,min_j,m,n);
	}
}
//          
int YoungHeapExtractMin(int (*a)[BUFFER_SIZE+1],int *m,int *n)
{
	int tmp=a[1][1];
	a[1][1]=a[*m][*n];
	if((*n)>1)
	{
		(*n)--;
	}
	else if((*n)==1)
	{
		(*m)--;
		(*n)=BUFFER_SIZE;
	}
	YoungMinHeapIfy(a,1,1,*m,*n);
	return tmp;
} 

// Young        (i,j)       key，key   (i,j)         
void YoungHeapDecreaseKey(int (*a)[BUFFER_SIZE+1],int i,int j,int key)
{
	int min_i=0;
	int min_j=0;
	
	if(a[i][j]<=key)
	{
		return;
	}
	
	a[i][j]=key;
	
	if(j>1&&a[i][j]<a[i][j-1])
	{
		min_i=i;
		min_j=j-1;	
	}
	else
	{
		min_i=i;
		min_j=j;
	}
	if(i>1&&a[min_i][min_j]<a[i-1][j])
	{
		min_i=i-1;
		min_j=j; 
	}
	if(min_i!=i||min_j!=j)
	{
		a[i][j]=a[min_i][min_j];
		YoungHeapDecreaseKey(a,min_i,min_j,key);
	}
	
}

//      x   Young    
void YoungMinHeapInsert(int (*a)[BUFFER_SIZE+1],int *m,int *n,int x)
{
	if((*n)<BUFFER_SIZE) 
	{
		(*n)++;
	}
	else if((*n)==BUFFER_SIZE)
	{
		(*m)++;
		(*n)=1;
	}
	a[*m][*n]=x+1;
	YoungHeapDecreaseKey(a,*m,*n,x);
}


//           Young    
void YoungSearch(int (*a)[BUFFER_SIZE+1],int m,int n,int i,int j,int key)
{
	if(i>m||i<1||j>n||j<1)
	{//        ，      
		printf("%d Not Exist!
",key);
	}
	else if(a[i][j]==key)
	{//              ，       
		printf("%d is a[%d][%d]!
",key,i,j);
	}
	else if(a[i][j]>key)
	{//    ，           
		YoungSearch(a,m,n,i,j-1,key);
	}
	else if(a[i][j]<key)
	{//               
		YoungSearch(a,m,n,i+1,j,key);
	}
	
	//            ，  YoungMinHeapInsert   ，          ，     O（m+n） 
}

// Young    n*n     
void YoungSort(int (*a)[BUFFER_SIZE+1],int (*b)[BUFFER_SIZE+1],int *c)
{
	int m=1;//  m  1  ，  Young    0  0      
	int n=0;
	int i=0;
	int j=0;
	
	for(i=1;i<=BUFFER_SIZE;i++)
	{
		for(j=1;j<=BUFFER_SIZE;j++)
		{//        
			YoungMinHeapInsert(a,&m,&n,b[i][j]);
		}
	}

	printf("  Young   ：
");
	for(i=1;i<BUFFER_SIZE+1;i++)
	{
		for(j=1;j<BUFFER_SIZE+1;j++)
		{
			printf("%d\t",a[i][j]);
		}
		printf("
");
	} 
	
	
	printf("
       :
");
	YoungSearch(a,BUFFER_SIZE,BUFFER_SIZE,1,BUFFER_SIZE,-1000); 
	YoungSearch(a,BUFFER_SIZE,BUFFER_SIZE,1,BUFFER_SIZE,1000);
	YoungSearch(a,BUFFER_SIZE,BUFFER_SIZE,1,BUFFER_SIZE,a[1][1]);

	
	for(i=0;i<BUFFER_SIZE*BUFFER_SIZE;i++)
	{//                          
		c[i]=YoungHeapExtractMin(a,&m,&n);
	}
}

int main()
{
	int i=0;
	int j=0;
	int a[BUFFER_SIZE+1][BUFFER_SIZE+1];
	int b[BUFFER_SIZE+1][BUFFER_SIZE+1];
	int c[BUFFER_SIZE*BUFFER_SIZE];
	//      
	srand((unsigned)time(NULL));
	for(i=1;i<BUFFER_SIZE+1;i++)
	{
		for(j=1;j<BUFFER_SIZE+1;j++)
		{
			b[i][j]=rand()%100;
		}
	} 
	printf("     n*n  ：
");
	for(i=1;i<BUFFER_SIZE+1;i++)
	{
		for(j=1;j<BUFFER_SIZE+1;j++)
		{
			printf("%d\t",b[i][j]);
		}
		printf("
");
	} 
	
	
	YoungSort(a,b,c);
	printf(" n*n      ：
"); 
	for(i=0;i<BUFFER_SIZE*BUFFER_SIZE;i++)
	{
		printf("%d ",c[i]);
	}
	
	system("pause");
	return 0;
}