【程式設計之美】一摞烙餅的排序

#include<stdio.h>
#include<assert.h>
class CPrefixSorting
{
public:
	CPrefixSorting()
	{
		m_nCakeCnt = 0;
		m_nMaxSwap = 0;
	}
	//計算烙餅翻轉資訊 
	//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:
	void Init(int* pCakeArray, int pCakeCnt)
	{
		assert(pCakeArray != NULL);
		assert(pCakeCnt > 0);
		m_nCakeCnt = pCakeCnt;

		//初始化烙餅數組
		m_CakeArray = new int[m_nCakeCnt];
		assert(m_CakeArray != NULL);
		for(int i = 0; i < m_nCakeCnt; i++)
		{
			m_CakeArray[i] = pCakeArray[i];
		}

		//設定更多交換次數資訊
		m_nMaxSwap = UpBound(m_nCakeCnt);

		//初始化交換結果數組
		m_SwapArray = new int[m_nMaxSwap];
		assert(m_SwapArray != NULL);

		//初始化中間交換結果資訊
		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 UpBound(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;
				for(i = 0; i < m_nMaxSwap; i++)
					m_SwapArray[i] = m_ReverseCakeArraySwap[i];
			}
		    return;
		}

		//遞歸進行翻轉
		for(i = 1;i < m_nCakeCnt; i++)
		{
			Revert(0, i);
			m_ReverseCakeArraySwap[step] = i;
			Search(step + 1);
			Revert(0, i);
		}
	}

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

	//翻轉烙餅資訊
	void Revert(int nBegin, int nEnd)
	{
		assert(nEnd > nBegin);
		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;
		}
	}

private:
	int* m_CakeArray; //烙餅資訊數組
	int m_nCakeCnt;  //烙餅個數
	int m_nMaxSwap;  //最多交換次數
	int* m_SwapArray;//交換結果數組
	int* m_ReverseCakeArray;//目前翻轉烙餅資訊數組
	int* m_ReverseCakeArraySwap;//目前翻轉烙餅交換結果數組
	int m_nSearch;//目前搜尋次數資訊
};

int main()  
{   
    CPrefixSorting *l=new CPrefixSorting();  
    int aa[10]={ 3,2,1,6,5,4,9,8,7,0};  
      
    l->Run(aa,10);  
    l->Output();  
 
    return 0;  
} 
           

結果在編譯時存在以下問題：

1） Assert 應該是 assert

2） m_arrSwap 未被定義，應該改為m_SwapArray

3 ）Init函數兩個for循環，後一個沒定義變量i，應該将i 改為 int i

另外，每運作一次Run函數，就會調用Init函數，就會申請新的記憶體，但卻沒有釋放原來的記憶體，會造成記憶體洩漏。if(step + nEstimate > m_nMaxSwap) 這句還會造成後面對m_ReverseCakeArraySwap數組的越界通路，使程式不能正常運作。

書上程式的低效主要是由于進行剪枝判斷時，沒有考慮好邊界條件，可進行如下修改：

1 ） if(step + nEstimate > m_nMaxSwap)  >改為 >=。

2 ） 判斷下界時，如果最大的烙餅不在最後一個位置，則要多翻轉一次，因而在LowerBound函數return ret; 前插入行：

                if (pCakeArray[nCakeCnt-1] != nCakeCnt-1)

                                        ret++;

3 ） n個烙餅，翻轉最大的n-2烙餅最多需要2*(n-2)次，剩下的2個最多1次，因而上限值為2*n-3，是以，m_nMaxSwap初始值可以取2*n-3+1=2*n-2，這樣每步與m_nMaxSwap的判斷就可以取大等于号。

4 ）采用書上提到的确定“上限值”的方法，直接建構一個初始解，取其翻轉次數為m_nMaxSwap的初始值。

         1和2任改一處，都能使搜尋次數從172126降到兩萬多，兩處都改，搜尋次數降到3475。若再改動第3處，搜尋次數降到2989；若采用4的方法（此時初始值為10），搜尋次數可降到1045。