//
// File: [TestSort.cpp]
// Description:[This file illustrate the sort methods. Make sure the length of the sequence consistent with its contents!]?
// Author:[SoRoMan]
// Date:[07/31/2006]
// Version:[1.0]
// History: []
//?
// INCLUDES ///////////////////////////////////////////////
#include "stdio.h"
// DEFINES ////////////////////////////////////////////////
#define N 11
// PROTOTYPES /////////////////////////////////////////////
void QuickSort(int *seq, int lenght);
void InsertSort(int *seq, int lenght);
void InsertSort2(int *seq, int lenght);
void ShellSort(int *seq, int lenght);
void IncrementInsertSort(int *seq, int length, int increment);
void HeapSort(int *seq, int length);
void SelectionSort(int *seq, int length);
void BubbleSort(int *seq, int length);
void BiBubbleSort(int *seq, int length);
void AdjustHeap(int *seq, int startIndex, int endIndex);
// GLOBALS ////////////////////////////////////////////////
int nAssignmentOperation = 0; // assignment counter
int nComparsionOperation = 0; // comparsion counter
// FUNCTIONS //////////////////////////////////////////////
int main(int argc, char* argv[])
{
?printf("0: Original Sequence\n");
?printf("1: Quick Sort\n");
?printf("2: Insert Sort\n");
?printf("3: Shell Sort\n");
?printf("4: Insert Sort2\n");
?printf("5: Heap Sort\n");
?printf("6: Selection Sort\n");
?printf("7: Bubble Sort\n");
?printf("8: Bi-Bubble Sort\n");
?printf("-1: Exit\n");?
?int cat = 0;?
?while (cat != -1)
?{
??// clear counter
??nAssignmentOperation = 0;
??nComparsionOperation = 0;
??//int array[N] = {600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,
??//600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1};
??int array[N] = {600, 64,6,78,246,445,345,445,7745,4885,1};
??printf("\nPlease select sort method:");
??scanf("%d", &cat);
??printf("-------------------------------------------------\n");
??switch(cat)
??{
???case 0:printf("No Sort. The Original Sequence is\n");
????break;
???case 1:printf("Quick Sort\n"); QuickSort(array, N);
????break;
???case 2:printf("Insert Sort\n"); InsertSort(array, N);
????break;
???case 3:printf("Shell Sort\n"); ShellSort(array, N);
????break;
???case 4:printf("Insert Sort2\n"); InsertSort2(array, N);
????break;
???case 5:printf("Heap Sort\n"); HeapSort(array, N);
????break;
???case 6:printf("Selection Sort\n"); SelectionSort(array, N);
????break;
???case 7:printf("Bubble Sort\n"); BubbleSort(array, N);
????break;
???case 8:printf("Bi-Bubble Sort\n"); BiBubbleSort(array, N);
????break;
???default:printf("Exit...\n");
????return 0;
??}
??for(int i = 0; i < N; i++)
??{
???printf("int = %d\n", array[i]);
??}
??printf("Count of comparsion operation? = %d\n", nComparsionOperation);
??printf("Count of assignment operation? = %d\n", nAssignmentOperation);
??printf("-------------------------------------------------\n");
?}
?return 0;
}
inline void Swap(int *pCurrPost, int *pCurrKey)
{
?nAssignmentOperation += 3;
?int temp;
?//swap value
?temp = *pCurrPost;
?*pCurrPost = *pCurrKey;
?*pCurrKey = temp;
}
////////////////////////////////////////////////////////////////////////////////
// Quick Sort algorithm.? (By SoRoMan, 2006.7.31)
// 快速排序的基本思想是基于分治策略的。對于輸入的子序列L[p..r]，如果規模足夠小則直接進行排序（比如用前述的冒泡、選擇、插入排序均可），否則分三步處理：
// 1.分解(Divide)：將待排序列L[p..r]劃分為兩個非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。具體可通過這樣的途徑實現：在序列L[p..r]中選擇數據元素L[q]，經比較和移動后，L[q]將處于L[p..r]中間的適當位置，使得數據元素L[q]的值小于L[q+1..r]中任一元素的值。
// 2.遞歸求解(Conquer)：通過遞歸調用快速排序算法，分別對L[p..q]和L[q+1..r]進行排序。
// 3.合并(Merge)：由于對分解出的兩個子序列的排序是就地進行的，所以在L[p..q]和L[q+1..r]都排好序后不需要執行任何計算L[p..r]就已排好序，即自然合并。
// 這個解決流程是符合分治法的基本步驟的。因此，快速排序法是分治法的經典應用實例之一。
// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void QuickSort(int *seq, int length)
{
?if(length <= 1)
?{
??return;
?}
?else
?{
??int post = *seq; // set post
??int *pCurrPost = seq; // set current position of post
??int *pCurrKey; // current position of key
??for(int j = length - 1, i = 1; i <= j;)
??{
???// handle the right sub-sequence
???while(i <= j)
???{
????pCurrKey = seq + j;
????if(*pCurrKey < post)
????{
?????Swap(pCurrPost, pCurrKey);
?????pCurrPost = pCurrKey;
?????break;
????}
????else
????{
?????j--;
????}
????nComparsionOperation ++;
???}
???// handle the left sub-sequence
???while(i <= j)
???{
????pCurrKey = seq + i;
????if(*pCurrKey > post)
????{
?????Swap(pCurrPost, pCurrKey);
?????pCurrPost = pCurrKey;
?????break;
????}
????else
????{
?????i++;
????}
????nComparsionOperation ++;
???}
??}
??// handle two sub sequences recursively
??int lleng = pCurrPost - seq; // left sub sequence
??int rleng = length - lleng - 1; // right sub sequence
??QuickSort(seq, lleng);
??QuickSort(seq + lleng + 1, rleng);
?}
}
////////////////////////////////////////////////////////////////////////////////
// Insert Sort algorithm (A special increment insert sort, increment = 1).? (By SoRoMan, 2006.7.31)
//插入排序的基本思想是，經過i-1遍處理后,L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當位置，使得L[1..i]又是排好序的序列。要達到這個目的，我們可以用順序比較的方法。首先比較L[i]和L[i-1]，如果L[i-1]≤ L[i]，則L[1..i]已排好序，第i遍處理就結束了；否則交換L[i]與L[i-1]的位置，繼續比較L[i-1]和L[i-2]，直到找到某一個位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]時為止。
//簡言之,插入排序就是每一步都將一個待排數據按其大小插入到已經排序的數據中的適當位置，直到全部插入完畢。插入排序方法分直接插入排序和折半插入排序兩種，這里只介紹直接插入排序，折半插入排序留到“查找”內容中進行
// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void InsertSort(int *seq, int length)
{
?IncrementInsertSort(seq, length, 1);
}
void InsertSort2(int *seq, int length)
{
?for(int i = 1; i < length; i++)
?{
??for (int j = 0; j < i; j++)
??{
???if(*(seq + i) < *(seq + j))
???{?
????int temp = *(seq + i);
????nAssignmentOperation ++;
????// insert, move (i-j) items
????for(int k = i; k > j; k-- )
????{
?????*(seq + k) = *(seq + k - 1);
?????nAssignmentOperation ++;
????}
????*(seq + k) = temp;
????nAssignmentOperation ++;
????nComparsionOperation ++;
????break;
???}
??}
?}
}
void IncrementInsertSort(int *seq, int length, int increment)
{
?for(int k = 0; k < increment; k++)
?{
??for (int i = increment + k; i < length; i+=increment + k)
??{
???int temp = *(seq + i);
???for (int j = i; j > increment - 1;)
???{
????nComparsionOperation ++;
????if(temp > *(seq + j - increment))
????{????
?????*(seq + j) = *(seq + j - increment);
?????nAssignmentOperation ++;
?????j-=increment;
????}
????else
????{
?????break;
????}
???}
???*(seq + j) = temp;
???nAssignmentOperation ++;????
??}
?}?
}
////////////////////////////////////////////////////////////////////////////////
// Shell Sort algorithm (Increment insert sort, increment = increment/3 + 1.).? (By SoRoMan, 2006.7.31)
// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void ShellSort(int *seq, int length)
{
?for(int increment = length; increment > 1;)
?{
??increment = increment/3 + 1;
??IncrementInsertSort(seq, length, increment);
?}
}
////////////////////////////////////////////////////////////////////////////////
// Heap Sort algorithm.? (SoRoMan, 2006.7.31)
//
//1.堆的概念：
//堆是一個關鍵字序列{k1,k2,…,kn},它具有如下特性：
//ki ≤k2i, ki ≤ k2i+1
//或ki ≥ k2i,ki ≥ k2i+1(i=1,2,…, └n/2┘)
//堆的特性在完全二叉樹中解釋為：完全二叉樹中任一結點的關鍵字都小于等于（或大于等于）它的左右孩子的關鍵字。
//如下列關鍵字序列均是堆： {5,23,16,68,94,72,71,73} (小頂堆) {96,83,27,38,11,9} （大頂堆） 由堆的定義可知：若關鍵字序列{k1,k2,…,kn}是堆，則堆頂元素是n個元素序列中的最小（或最大）元素。
//2.基本思想：
//首先將初始待排序記錄序列建堆，則堆頂元素必為含最大關鍵字或最小關鍵字的記錄，輸出該記錄，然后將剩余記錄再調整為堆，如此反復，直至排序結束。
//在堆排序主要需解決兩個問題：
//① 如何建堆？ 在完全二叉樹中，所有序號i>└n/2┘的結點都是葉子，因此，以這些結點為根的子樹均已是堆，這樣只需將以序號為└n/2┘, └n/2┘-1, └n/2┘-2,…,1的結點為根、的子樹都調整為堆即可。在按此次序調整每個結點時，其左、右子樹均已是堆。
//② 若ki的左、右子樹已經是堆，如何將以ki為根的完全二叉樹也調整為堆？ 因ki的左、右子樹已經是堆，所以必須在ki 和它的左、右孩子中選出最小（或最大）的結點放到ki的位置上，不妨設k2I關鍵字最小，將ki與k2I交換位置，而交換之后有可能導致以k2I為根的子樹不再為堆，于是可重復上述過程，將以k2I為根的子樹調整為堆，……,如此逐層下去，最多可能一直調整到樹葉，此方法稱為"篩選法"。
//3.性能分析：
//堆排序的時間主要由建立初始堆和不斷重復建堆這兩部分的時間開銷構成。其中：建立初始堆時，總共需進行的關鍵字比較次數 ≤ 4n =O(n) ;排序過程中進行n-1次重建堆所進行的總比較次數不超過下式： 2*(└ log2(n-1) ┘+└ log2(n-2) ┘+…+ └ log22 ┘) < 2n └ log2n ┘=O(n log2n)因此堆排序總的時間復雜度是 O(n+ n log2n)= O(n log2n)。
//堆排序在最壞情況下的時間復雜度也是O(nlog2n)，相對于快速排序來說，這是堆排序的最大優點。
//另外，堆排序僅需一個記錄大小供交換用的輔助空間。由于建初始堆所需的比較次數較多，所以堆排序不適宜于記錄較少的文件，但對n較大的文件還是很有效的。
// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void HeapSort(int *seq, int length)
{
?for(int n = length; n > 0; n--)
?{
??for(int j = n/2; j > 0; j--)
??{
???AdjustHeap(seq, j, n);
??}
??Swap(seq, seq+n-1);??
?}?
}
void AdjustHeap(int *seq, int startIndex, int endIndex)
{
?while(2*startIndex <= endIndex)
?{
??int i =? startIndex - 1;
??startIndex = startIndex*2;
??nComparsionOperation ++;
??if (startIndex < endIndex && *(seq + startIndex -1) < *(seq + startIndex))
??{
???startIndex++;
??}
??nComparsionOperation ++;
??if(*(seq + startIndex -1) > *(seq + i))
??{
???Swap(seq + startIndex - 1, seq + i);
??}??
??else
??{
???break;
??}
?}
}
////////////////////////////////////////////////////////////////////////////////
// Selection Sort algorithm.? (SoRoMan, 2006.7.31)
// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void SelectionSort(int *seq, int length)
{
?for(int i = 0; i < length; i++)
?{
??int k = i;
??for(int j = i+1; j < length; j++)
??{
???nComparsionOperation ++;
???if (*(seq + j) < *(seq + k))
???{
????k = j;
???}
??}
??Swap(seq + k, seq + i);
?}
}
////////////////////////////////////////////////////////////////////////////////
// Bubble Sort algorithm.? (SoRoMan, 2006.7.31)
// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void BubbleSort(int *seq, int length)
{
?for(int i = 0; i < length; i++)
?{
??for(int j = length-1; j > i; j--)
??{
???nComparsionOperation ++;
???if (*(seq + j) < *(seq + j - 1))
???{
????Swap(seq + j, seq + j - 1);
???}
??}
?}
}
////////////////////////////////////////////////////////////////////////////////
// Bi-Directinal Bubble Sort algorithm.? (SoRoMan, 2006.7.31)
//思想：
//基于在一趟排序中，位于最后一次交換關鍵字的的后面的關鍵字序列已經是有序的，所以不用再排序。
//相對于一般的冒泡排序，可以減少關鍵字比較次數，但交換次數不變。
// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void BiBubbleSort(int *seq, int length)
{
?int k,low,up;
?low = 0;
?up = length-1;
?while (up > low)
?{
??k = low;??
??for(int i = low; i < up; i++)
??{
???nComparsionOperation ++;
???if (*(seq + i) > *(seq + i + 1))
???{
????Swap(seq + i, seq + i + 1);
????k = i;
???}
??}
??up = k;
??for(int j = up; j > low; j--)
??{
???nComparsionOperation ++;
???if (*(seq + j) < *(seq + j - 1))
???{
????Swap(seq + j, seq + j - 1);
????k = j;
???}
??}?
??low = k;
?}
}
?
?
?