//
// 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;
}
}