Stable vs. Non-Stable Sorting

Prerequisites, Goals, and Outcomes

Prerequisites: Students should have mastered the following prerequisite skills.

·         Sorting - Knowledge of Bubblesort, Insertionsort, Selestsort and Shellsort

·         Complexity - Knowledge of basic asymptotic analysis and Big-Oh notation

Goals: This assignment is designed to reinforce the student's understanding of basic and fast sorting algorithms and complexity.

Outcomes: Students successfully completing this assignment would master the following outcomes.

·         Understand Bubblesort, Insertionsort, Selestsort and Shellsort

·         Familiarize the complexity of the sort methods mentioned above

·         Understand the difference between stable and non-stable sorting algorithms

Background

A stable sort is a sort algorithm that performs the same amount of work regardless of the data being sorted. The amount of work a non-stable sort performs, on the other hand, can vary significantly depending on the arrangement of data. This translates to stable sorts having identical best case, worst case, and average case complexity. The worst case complexity of a non-stable sort can be an entirely different runtime class than its best or average case.

Description

The program to be completed for this assessment demonstrates the runtime differences between a stable and non-stable sort.

In this assessment, you should firstly implement the sort methods mentioned above corresponding in functions Bubblesort, Insertionsort, Selestsort and Shellsort.

To test the complexity of these four sort methods, you should considerate the best case, worst case, and average case, and correspondingly generate the data. For the stable sort algorithm, the average and worst case are identical. The non-stable sort algorithm, on the other hand, has distinct worst and average cases. A supplied main routine repeatedly initializes and sorts these arrays to demonstrate the differences between the stable and non-stable sort algorithms.

The correct implementation of data initialization requires the generation of random numbers. Use the rand library function to generate a random integer.

Tasks

To complete this assessment, you need to implement four sort algorithm mentioned above and complete the data initialization in main.cpp.

Submission

Submit only the following.

1.    main.cpp– contain the sort function and data initialization.

参考代码：

#include "iostream.h"
#include "stdlib.h"
#include "string.h"
//////////////////// "Compare.h"/////////////////////
class Compare{
public:
 static bool lt(int x,int y) {return x<y;}
 static bool eq(int x,int y) {return x==y;}
 static bool gt(int x,int y) {return x>y;}
};
//////////////// "Sorter.h"///////////////////////////
template <class Record,class Compare>
class Sorter{
protected:
 static void swap(Record Array[],int i,int j); //交换数组中的两个记录
public:
 void Sort(Record Array[],int n);   //对数组Array进行排序
 void PrintArray(Record array[], int n);  //输出数组内容
};

//交换数组中的两个记录
template <class Record,class Compare>
void Sorter<Record,Compare>::swap(Record Array[],int i,int j)
{
 Record TempRecord = Array[i];
 Array[i] = Array[j];
 Array[j] = TempRecord;
 
}

//输出数组内容
template <class Record,class Compare>
void Sorter<Record,Compare>::PrintArray(Record Array[], int n)
{
 for(int i=0;i<n;i++)
  cout<<Array[i]<<" ";
 cout<<endl;
}
template <class Record,class Compare>
class InsertSorter:public Sorter<Record,Compare>{};
 
//////////////////////"BubbleSorter.h"/////////////////////////
template <class Record,class Compare>
class BubbleSorter:public Sorter<Record,Compare>
{
public:
 void Sort(Record Array[],int n);
};

//起泡排序，Array[]为待排序数组，n为数组长度
template <class Record,class Compare>
void BubbleSorter<Record,Compare>::Sort(Record Array[], int n)
{
 for (int i=1; i<n; i++)    // 第i个记录起泡
  for (int j=n-1; j>=i; j--)  // 依次比较相邻记录
   if (Compare ::lt(Array[j], Array[j-1])) //如果逆置，就交换
    swap(Array, j, j-1);
}
//////////////////////StraightInsertSorter///////////////
template <class Record,class Compare>
class StraightInsertSorter:public InsertSorter<Record,Compare>
{
public:
 void Sort(Record Array[],int n);
};

////////直接插入排序，Array[]为待排序数组，n为数组长度
template <class Record,class Compare>
void StraightInsertSorter<Record,Compare>::Sort(Record Array[], int n)
{
 // 依次插入第i个记录
 for (int i=1; i<n; i++)
 {
  //依次与前面的记录进行比较，如果发现比它小的记录，就交换
  for (int j=i;j>0;j--)
  {
   if (Compare::lt(Array[j], Array[j-1]))
    swap(Array, j, j-1);
   else break;  //此时i前面的所有记录(包括i)已排好序  
  }
 }
}
template <class Record,class Compare>
class StraightSelectSorter:public Sorter<Record,Compare>
{
public:
 void Sort(Record Array[],int n);
};

//直接选择排序，Array[]为待排序数组，n为数组长度
template <class Record,class Compare>
void StraightSelectSorter<Record,Compare>::Sort(Record Array[], int n)
{
 for (int i=0; i<n-1; i++) // 依次选出第i小的记录，即剩余记录中最小的那个
 {
        int Smallest = i;  // 首先假设记录i就是最小的
        for (int j=i+1;j<n; j++) // 开始向后扫描所有剩余记录
            if (Compare::lt(Array[j], Array[Smallest]))
              Smallest = j;  // 如果发现更小的记录，记录它的位置
        swap(Array, i, Smallest); //将第i小的记录放在数组中第i个位置
 }
}
template <class Record,class Compare>
class ShellSorter:public Sorter<Record,Compare>
{
private:
 // 针对变化的增量而修改的插入排序算法，参数delta表示当前的增量
 void ModifiedInsertSort(Record Array[],int n,int delta);
public:
 void Sort(Record Array[],int n);
 void delta3Sort(Record Array[], int n);
};

//Shell排序，Array[]为待排序数组，n为数组长度
template <class Record,class Compare>
void ShellSorter<Record,Compare>::Sort(Record Array[], int n)
{
 for (int delta=n/2; delta>0; delta/=2)      //增量delta每次除以2递减
  for (int j=0; j<delta; j++)       //分别对delta个子序列进行插入排序
   ModifiedInsertSort(&Array[j], n-j, delta);
}

//Shell排序，Array[]为待排序数组，n为数组长度
template <class Record,class int_intCompare>
void ShellSorter<Record,int_intCompare>::delta3Sort(Record Array[], int n)
{
 for (int delta=n/3; delta>=3; delta/=3)      //增量delta每次除以3递减
  for (int j=0; j<delta; j++)       //分别对delta个子序列进行插入排序
   ModifiedInsertSort(&Array[j],n-j, delta);
 ModifiedInsertSort(Array,n,1);
}

// 针对变化的增量而修改的插入排序算法，参数delta表示当前的增量
template <class Record,class Compare>
void ShellSorter<Record,Compare>::ModifiedInsertSort(Record Array[],int n, int delta)
{
 for (int i=delta; i<n; i+=delta) // 对子序列中第i个记录排序
  for (int j=i; (j>=delta)&&(Compare::lt(Array[j], Array[j-delta])); j-=delta)
  {
//   if
    swap(Array, j, j-delta);
//   else break;
  }
}

// 设定随即函数的种子
inline void Randomize()
  { srand(1); }

//返回一个0到n-1之间的随机数
inline int Random(int n)
  { return rand() % (n); }

void main()
{
 //产生随机数组,长度为100
 Randomize();
 int * sortarray =new int[100];
 for(int i=0;i<100;i++)
  sortarray[i]=Random(100);
 int choice;
 cout<<"选择排序方式： 1---Bubblesort,2---Insertionsort,3---Selestsort,4---Shellsort"<<endl;
 cin>>choice;
 if(choice==1)//排序 
 {//实例化起泡排序类
 BubbleSorter<int,Compare> sorter;
 cout<<"排序前：";cout<<endl;
 sorter.PrintArray(sortarray,100);
 sorter.Sort(sortarray,100);
 //输出排序后数组内容
 cout<<"排序后：";cout<<endl;
 sorter.PrintArray(sortarray,100);
 }
 if(choice==2)
 {//实例化直接插入排序类
 StraightInsertSorter<int,Compare> sorter;
 cout<<"排序前：";cout<<endl;
 sorter.PrintArray(sortarray,100);
 sorter.Sort(sortarray,100);
 //输出排序后数组内容
 cout<<"排序后：";cout<<endl;
 sorter.PrintArray(sortarray,100);
 }
 if(choice==3)
 {//实例化直接选择排序类
 StraightSelectSorter<int,Compare> sorter;
 cout<<"排序前：";cout<<endl;
 sorter.PrintArray(sortarray,100);
  sorter.Sort(sortarray,100);
 //输出排序后数组内容
 cout<<"排序后：";cout<<endl;
 sorter.PrintArray(sortarray,100);
 }
    if(choice==4)
 {//实例化Shell排序类
 ShellSorter<int,Compare> sorter;
  cout<<"排序前：";cout<<endl;
 sorter.PrintArray(sortarray,100);
 //输出排序后数组内容
 cout<<"排序后：";cout<<endl;
 sorter.PrintArray(sortarray,100);
 }

}