Data structure learning (C ++) continued - sort [1] test program

The following routines are all sorts of the array, and the use of the static linked list is also suitable for sorting of the linked list. For simplicity, only the single key code is sorted, and the last result is arranged in an ascending order from beginning to tail. Below is a unified test program:

#include

#include

Using namespace std;

#include

#include

#include

#include "insertsort.h"

#define random (NUM) (Rand ()% (NUM))

#define randomize () SRAND (NULL) TIME (NULL)

#define n Number of Sorting Elements

#define sort insertsort // Sort Method

Class Timer // Unit MS

{

PUBLIC:

Void start () {start_t = clock ();

Clock_t time () {return (clock () - start_t);

Private:

Clock_t start_t;

}

INT KCN, RMN; Timer Timer;

Void Test (int A [])

{

Timer.Start ();

Sort (A, N, KCN, RMN);

Cout << "/ TTIMESPARED: << Timer.Time () <<" MS "<< endl;

COUT << "KCN =" << Left << SETW (11) << kcn;

COUT << "KCN / N =" << Left << SETW (11) << (double) KCN / N;

COUT << "KCN / N ^ 2 =" << Left << SETW (11) << (double) KCN / N / N;

COUT << "KCN / NLOGN =" << Left << SETW (11) << (Double) KCN / N / LOG ((Double) N) * log (2.0) << ENDL;

COUT << "RMN =" << Left << SETW (11) << RMN;

COUT << "RMN / N =" << Left << SETW (11) << (double) RMN / N;

COUT << "RMN / N ^ 2 =" << Left << SETW (11) << (double) RMN / N / N;

Cout << "RMN / NLOGN =" << Left << SETW (11) << (double) RMN / N / LOG ((Double) N) * log (2.0) << ENDL;

}

int main ()

{

INT I;

// randomize (); in order to compare each sort algorithm in the same case, do not add this sentence

INT * ascending = new int [n]; // ascending sequence

INT * DESCENDING = new int [n]; // Descending sequence INT * Randomness = new int [n]; // random sequence

For (i = 0; i

For (i = 0; i

COUT << "sort assending n =" << n; test (ascending);

COUT << "sort randomness n =" << n; test (randomness);

Cout << "sort descending n =" << n; test (descending);

Return 0;

}

It should be noted that the KCN (the number of key code comparisons), the RMN (number of recorded movements) is not the algorithm, and is an intuitive evaluation of the performance of the algorithm (without those formulas calculated). Sorting more than 10,000 integer should be the most surprising test means. It is recommended not to increase the number of records. First, in the worst case, it is necessary to wait for too long. When it is worse, the number of records may overflow, causing the program to crash.