Reversing top m cakes every time to sort a bunch of cakes.

cake_reverse.cpp

#include "stdio.h"  
#include "iostream"  
using namespace std;  
#pragma once  
class CPrefixSorting  
{  
public:  
  ~CPrefixSorting()
	{
		if (m_CakeArray != NULL)
		{
			delete m_CakeArray;
		}
		if (m_SwapArray != NULL)
		{
			delete m_SwapArray;
		}
		if (m_ReverseCakeArray != NULL)
		{
			delete m_ReverseCakeArray;
		}
		if (m_ReverseCakeArraySwap != NULL)
		{
			delete m_ReverseCakeArraySwap;
		}
	}
	CPrefixSorting()  
	{  
		m_nCakeCnt=0;  
		m_nMaxSwap=0;  
	}  

	// 计算烙饼翻转信息  
	// @param  
	// pCakeArray  存储烙饼索引数组  
	// nCakeCnt    烙饼个数  
	//   
	void Run(int* pCakeArray, int nCakeCnt)  
	{  
		Init(pCakeArray,nCakeCnt);  
		m_nSearch=0;  
		Search(0);  
	}  

	// 输出烙饼的翻转次数，翻转信息  
	void Output()  
	{  
		for(int i=0;i<m_nMaxSwap;i++)  
		{  
			printf("%d",m_SwapArray[i]);  
		}  
		printf("\n |Search Times|:%d\n",m_nSearch);  
		printf("Total Swap times=%d\n",m_nMaxSwap);  
	}  

private:  
	int* m_CakeArray;    // 烙饼信息数组  
	int m_nCakeCnt;      // 烙饼的个数  
	int m_nMaxSwap;      // 最多交换次数，根据前面的推断，最多为m_nCakeCnt*2  
	int* m_SwapArray;    // 交换结果数组  
	int* m_ReverseCakeArray;     // 当前翻转烙饼信息数组  
	int* m_ReverseCakeArraySwap; // 当前翻转烙饼交换结果数组  
	int m_nSearch;               // 当前搜索次数信息  

	// 初始化数组信息  
	// @param  
	// pCakeArray   存储烙饼索引数组  
	// nCakeCnt     烙饼个数  
	//  
	void Init(int* pCakeArray,int nCakeCnt)  
	{  
		m_nCakeCnt=nCakeCnt;  

		// 初始化烙饼数组  
		m_CakeArray=new int[m_nCakeCnt];  
		for(int i=0;i<m_nCakeCnt;i++)  
		{  
			m_CakeArray[i]=pCakeArray[i];  
		}  

		// 设置最多交换次数信息  
		m_nMaxSwap=UpperBound(m_nCakeCnt);  

		// 初始化交换结果数组  
		m_SwapArray=new int[m_nMaxSwap+1];  

		// 初始化中间交换结果信息  
		m_ReverseCakeArray=new int[m_nCakeCnt];  
		for(int i=0;i<m_nCakeCnt;i++)  
		{  
			m_ReverseCakeArray[i]=m_CakeArray[i];  
		}  
		m_ReverseCakeArraySwap=new int[m_nMaxSwap];  
	}  

	// 翻转上届  
	int UpperBound(int nCakeCnt)  
	{  
		return nCakeCnt*2;  
	}  

	// 当前翻转的下届  
	int LowerBound(int* pCakeArray, int nCakeCnt)  
	{  
		int t,ret=0;  
		// 根据当前数组的排序信息情况来判断最少需要交换多少次  
		for(int i=1;i<nCakeCnt;i++)  
		{  
			// 判断位置相邻的两个烙饼是否为尺寸排序上相等的  
			t=pCakeArray[i]-pCakeArray[i-1];  
			if((t==1)||(t==-1))  
			{}  
			else  
			{  
				ret++;  
			}  
		}  

		return ret;  
	}  

	// 排序的主函数  
	void Search(int step)  
	{  
		int i, nEstimate;  
		m_nSearch++;  

		// 估算当前搜索所需要的最小的交换次数  
		nEstimate=LowerBound(m_ReverseCakeArray,m_nCakeCnt);  
		if(step+nEstimate>=m_nMaxSwap)  
		{  
			return;  
		}  

		// 如果已经排好序，即翻转完成后，输出结果  
		if(IsSorted(m_ReverseCakeArray, m_nCakeCnt))  
		{  
			if(step<m_nMaxSwap)  
			{  
				m_nMaxSwap=step;// 修改最大的翻转次数，让m_nMaxSwap记录最小的翻转次数  
				for(i=0;i<m_nMaxSwap;i++)  
				{  
					m_SwapArray[i]=m_ReverseCakeArraySwap[i];  
				}  
			}  
			return;  
		}  

		// 递归进行翻转  
		for(i=1;i<m_nCakeCnt;i++)  
		{  
			if (step > 0)
			{
				if (m_ReverseCakeArraySwap[step-1] == i)
				{
					continue;
				}
			}
			
			Reverse(0,i);  
			m_ReverseCakeArraySwap[step]=i;
			Search(step+1);  
			Reverse(0,i);  
		}  
		return;
	}  

	// 判断是否已经排好序  
	bool IsSorted(int* pCakeArray, int nCakeCnt)  
	{  
		for(int i=1;i<nCakeCnt;i++)  
		{  
			if(pCakeArray[i-1]>pCakeArray[i])  
			{  
				return false;  
			}  
		}  
		return true;  
	}  

	// 翻转烙饼信息  
	// 非常经典的数组翻转算法  
	void Reverse(int nBegin,int nEnd)  
	{  
		int i,j,t;  
		for(i=nBegin,j=nEnd;i<j;i++,j--)  
		{  
			t=m_ReverseCakeArray[i];  
			m_ReverseCakeArray[i]=m_ReverseCakeArray[j];  
			m_ReverseCakeArray[j]=t;  
		}  
	}  
};


int main()
{  
	cout<<"--->begin"<<endl;  
	CPrefixSorting panCakeSort;  
	int panCake[10]={3,2,1,6,5,4,9,8,7,0};//{3,5,1,4,2};  
	panCakeSort.Run(panCake,10);  
	panCakeSort.Output();  
	return 0;  
}