//
// 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)
// 快速排序的基本思想是基于分治策略的。對(duì)于輸入的子序列L[p..r]，如果規(guī)模足夠小則直接進(jìn)行排序（比如用前述的冒泡、選擇、插入排序均可），否則分三步處理：
// 1.分解(Divide)：將待排序列L[p..r]劃分為兩個(gè)非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。具體可通過(guò)這樣的途徑實(shí)現(xiàn)：在序列L[p..r]中選擇數(shù)據(jù)元素L[q]，經(jīng)比較和移動(dòng)后，L[q]將處于L[p..r]中間的適當(dāng)位置，使得數(shù)據(jù)元素L[q]的值小于L[q+1..r]中任一元素的值。
// 2.遞歸求解(Conquer)：通過(guò)遞歸調(diào)用快速排序算法，分別對(duì)L[p..q]和L[q+1..r]進(jìn)行排序。
// 3.合并(Merge)：由于對(duì)分解出的兩個(gè)子序列的排序是就地進(jìn)行的，所以在L[p..q]和L[q+1..r]都排好序后不需要執(zhí)行任何計(jì)算L[p..r]就已排好序，即自然合并。
// 這個(gè)解決流程是符合分治法的基本步驟的。因此，快速排序法是分治法的經(jīng)典應(yīng)用實(shí)例之一。
// 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)
//插入排序的基本思想是，經(jīng)過(guò)i-1遍處理后,L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當(dāng)位置，使得L[1..i]又是排好序的序列。要達(dá)到這個(gè)目的，我們可以用順序比較的方法。首先比較L[i]和L[i-1]，如果L[i-1]≤ L[i]，則L[1..i]已排好序，第i遍處理就結(jié)束了；否則交換L[i]與L[i-1]的位置，繼續(xù)比較L[i-1]和L[i-2]，直到找到某一個(gè)位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]時(shí)為止。
//簡(jiǎn)言之,插入排序就是每一步都將一個(gè)待排數(shù)據(jù)按其大小插入到已經(jīng)排序的數(shù)據(jù)中的適當(dāng)位置，直到全部插入完畢。插入排序方法分直接插入排序和折半插入排序兩種，這里只介紹直接插入排序，折半插入排序留到“查找”內(nèi)容中進(jì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 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.堆的概念：
//堆是一個(gè)關(guān)鍵字序列{k1,k2,…,kn},它具有如下特性：
//ki ≤k2i, ki ≤ k2i+1
//或ki ≥ k2i,ki ≥ k2i+1(i=1,2,…, └n/2┘)
//堆的特性在完全二叉樹(shù)中解釋為：完全二叉樹(shù)中任一結(jié)點(diǎn)的關(guān)鍵字都小于等于（或大于等于）它的左右孩子的關(guān)鍵字。
//如下列關(guān)鍵字序列均是堆： {5,23,16,68,94,72,71,73} (小頂堆) {96,83,27,38,11,9} （大頂堆） 由堆的定義可知：若關(guān)鍵字序列{k1,k2,…,kn}是堆，則堆頂元素是n個(gè)元素序列中的最小（或最大）元素。
//2.基本思想：
//首先將初始待排序記錄序列建堆，則堆頂元素必為含最大關(guān)鍵字或最小關(guān)鍵字的記錄，輸出該記錄，然后將剩余記錄再調(diào)整為堆，如此反復(fù)，直至排序結(jié)束。
//在堆排序主要需解決兩個(gè)問(wèn)題：
//① 如何建堆？ 在完全二叉樹(shù)中，所有序號(hào)i>└n/2┘的結(jié)點(diǎn)都是葉子，因此，以這些結(jié)點(diǎn)為根的子樹(shù)均已是堆，這樣只需將以序號(hào)為└n/2┘, └n/2┘-1, └n/2┘-2,…,1的結(jié)點(diǎn)為根、的子樹(shù)都調(diào)整為堆即可。在按此次序調(diào)整每個(gè)結(jié)點(diǎn)時(shí)，其左、右子樹(shù)均已是堆。
//② 若ki的左、右子樹(shù)已經(jīng)是堆，如何將以ki為根的完全二叉樹(shù)也調(diào)整為堆？ 因ki的左、右子樹(shù)已經(jīng)是堆，所以必須在ki 和它的左、右孩子中選出最小（或最大）的結(jié)點(diǎn)放到ki的位置上，不妨設(shè)k2I關(guān)鍵字最小，將ki與k2I交換位置，而交換之后有可能導(dǎo)致以k2I為根的子樹(shù)不再為堆，于是可重復(fù)上述過(guò)程，將以k2I為根的子樹(shù)調(diào)整為堆，……,如此逐層下去，最多可能一直調(diào)整到樹(shù)葉，此方法稱為"篩選法"。
//3.性能分析：
//堆排序的時(shí)間主要由建立初始堆和不斷重復(fù)建堆這兩部分的時(shí)間開(kāi)銷構(gòu)成。其中：建立初始堆時(shí)，總共需進(jìn)行的關(guān)鍵字比較次數(shù) ≤ 4n =O(n) ;排序過(guò)程中進(jìn)行n-1次重建堆所進(jìn)行的總比較次數(shù)不超過(guò)下式： 2*(└ log2(n-1) ┘+└ log2(n-2) ┘+…+ └ log22 ┘) < 2n └ log2n ┘=O(n log2n)因此堆排序總的時(shí)間復(fù)雜度是 O(n+ n log2n)= O(n log2n)。
//堆排序在最壞情況下的時(shí)間復(fù)雜度也是O(nlog2n)，相對(duì)于快速排序來(lái)說(shuō)，這是堆排序的最大優(yōu)點(diǎn)。
//另外，堆排序僅需一個(gè)記錄大小供交換用的輔助空間。由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄較少的文件，但對(duì)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)
//思想：
//基于在一趟排序中，位于最后一次交換關(guān)鍵字的的后面的關(guān)鍵字序列已經(jīng)是有序的，所以不用再排序。
//相對(duì)于一般的冒泡排序，可以減少關(guān)鍵字比較次數(shù)，但交換次數(shù)不變。
// 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;
?}
}
?
?
?