Chapter4/numTranspositions.c File Reference

Compute average number of transpositions in Insertion Sort of n elements. Exhaustively permute all n objects and compute the total number of transpositions when using Insertion Sort. The average is computed by dividing this total by the number of permutations. Really only useful for table sizes of less than 12. More...

#include <stdlib.h>
#include <stdio.h>

Functions

void out ()
 Output array for debugging.
void eval ()
 count tranpositions.
void permute (int pos)
 Permute the input array.
int main (int argc, char **argv)
 Launch the program.

Variables

int n
 Size of array.
int * A
 The array in memory.
int * TT
 Processing storage, no greater than (n-1)*(n-1).
int ctr = 0
 Permutation number.


Detailed Description

Compute average number of transpositions in Insertion Sort of n elements. Exhaustively permute all n objects and compute the total number of transpositions when using Insertion Sort. The average is computed by dividing this total by the number of permutations. Really only useful for table sizes of less than 12.

Author:
George Heineman
Date:
6/15/08

Function Documentation

void eval (  ) 

count tranpositions.

Every 100,000 iterations a status update is printed.

int main ( int  argc,
char **  argv 
)

Launch the program.

void out (  ) 

Output array for debugging.

void permute ( int  pos  ) 

Permute the input array.


Variable Documentation

int* A

The array in memory.

int ctr = 0

Permutation number.

int n

Size of array.

int* TT

Processing storage, no greater than (n-1)*(n-1).

Algorithm Development Kit 1.0