header.h
/* header.h
* Steve Gardiner
* CS 227 - Richard Nau
* 2/25/AD1996
* Sort Time v. Number of Inversions
*/

/* A number of definitions governing a particular experiment
* for the project
*/

#include<stdio.h>
#include<time.h>

#define Array_Size 256
#define BIG Array_Size+1
#define MaxInv ((Array_Size*Array_Size)-Array_Size)/2
#define BottomInv (((MaxInv)/2)-100)
#define TopInv (((MaxInv)/2)+100)
#define NoTrials 50
#define NoWithN 2

#define filename "sorts2.data"

typedef int array;

sorts.h
/* Steve Gardiner
* for CS 227 - Richard Nau
* 2/25/AD1996
* Sort Time v. Number of Inversions
*/

/* The sorts used in the data collection for the project */

#include"header.h"

#define NoSorts 6

void MergeSort( array From, array Into, int l, int r)

/* Pre-condition: the array From is a list on in some order.
* The array Into is a copy of From.
* Post-condition: the array Into contains the elements of From in
* order. No guarantee is made about the contents of From.
* Procedure: The two halves of the array are sorted separately into
* From. These two sorted halves are then merged into Into.
*/
{ int split;
int i, j, k;

if ((r-l)<=1)
{
if (From>From)
{
Into = From;
Into = From;
}
else
{
Into = From;
Into = From;
}
}
else
{
split = l + ((r - l) / 2);
MergeSort(Into,From,l,split);
MergeSort(Into,From,split+1,r);
j = l;
k = split + 1;
for (i=l; (i<r) && (j<=split) && (k<=r); i++)
if (From<From)
{
Into = From;
k++;
}
else
{
Into = From;
j++;
}
if (j>split)
while (k<=r)
{
Into = From;
k++;
i++;
}
else
while (j<=split)
{
Into = From;
j++;
i++;
}
}
}

void QuickSort( array A, int l, int r)

/* Pre-condition: the array A is a list on in some order.
* Post-condition: the array A on is in order.
* Procedure: recursive QuickSort. The last value is taken as a pivot,
* and its final position in the array is calculated. Then the two
* halves of the array, those before the pivot and those after, are
* sorted using the same algorithm. The base case of the recursion
* is when l=r, in which case the array of 1 element is in order as is.
*/
{ int pivot= A;
int i = l-1;
int j = r;
int temp;

if (r>l)
{
do
{
do i++; while (A<pivot);
do j--; while (A>pivot);
temp = A;
A = A;
A = temp;
}
while (j>i);
A = A;
A = pivot;
A = temp;
QuickSort(A,l,i-1);
QuickSort(A,i+1,r);
}
}

void SelectionSort( array A, int M)

/* Pre-condition: the array A is a list on in some order.
* Post-condition: the array A on is in order.
* Procedure: a selection sort. The first i-1 values are assumed to
* be in order and to be less than all values A, A .. A.
* The minimum value on A..A is found and placed in A, with
* the value of A being placed where this minimum value was. Then
* the procedure is repeated for i+1.
*/
{ int i, j;
int min;
int temp;

for (i=1; i<M-1; i++)
{
min = i;
for (j=i+1; j<=M; j++)
if (A<A)
min = j;
temp = A;
A = A;
A = temp;
}
}

void ImprovedBubbleSort( array A, int M)

/* Pre-condition: the array A is a list on in some order.
* Post-condition: the array A on is in order.
* Procedure: a bubble sort. Consecutive elements are exchanged if
* need be; so larger elements "bubble" up toward the high end of
* the array. A variable last_exchgd keeps track of the last element
* which was out of order on the previous pass. So last_exchgd is
* the first element which we don't know is in its final position.
* When last_exchgd reaches 0, the array is in order.
*/
{ int last_exchgd = M; /* We don't know if any elements are in order */
int i;
int j;
int temp;

while (last_exchgd>0)
{
i = last_exchgd;
last_exchgd = 0;
for (j=1; j<i; j++)
if (A>A)
{
temp = A;
A = A;
A = temp;
last_exchgd = j;
}
}
}

void BubbleSort( array A, int M)

/* Pre-condition: the array A is a list on in some order.
* Post-condition: the array A on is in order.
* Procedure: a bubble sort. Consecutive elements are exchanged as need
* be; so larger elements "bubble" up toward the high end of the array.
* After the kth pass, we know that the last k elements are in order.
*/
{ int i;
int j;
int temp;

for (i=M-1; i>1; i--)
for (j=1; j<=i; j++)
if (A>A)
{
temp = A;
A = A;
A = temp;
}
}

void InsertionSort( array A, int M)

/* Pre-condition: the array A is a list on in some order.
* Post-condition: the array A on is in order.
* Procedure: the array is considered to be in order. The
* element A is inserted into its correct position in this
* list by moving the elements in the list forward until the
* correct position is found. Thus an ordered list in
* is created. The procedure is repeated for i+1.
*/
{ int i;
int j;
int R;

for (i=2; i<M; i++)
{
R = A;
for (j=i-1; A>R; j--)
A = A;
A = R;
}
}

project.c
#include<stdio.h>
#include<time.h>
#include"sorts.h"

typedef time_t times;

int uniform( int N)
{
return ( random() % N );
}

void Tausch( array In, int first, int second)
{ int temp;

temp= In;
In= In;
In= temp;
}

void Initialize( array A, array B, array C, int M)
{ int j;

for (j=0; j<M+1; j++)
{
A= j;
B= 0;
C= j;
}
}

void LoadInvTable( array B, array C, int M, int N)
{ int Least_Unused = M-1;
int current;
int j;

for (j=0; j<M+1; j++)
{
current= uniform(Least_Unused)+1;
B]++;
if (B]==M-current)
{
Tausch(C,current,Least_Unused);
Least_Unused--;
}
}

B= -1;
}

void Invert( array A, array B, int M)

{ int k=M;

while (k>0)
{
while (B==0)
k--;
while (B>0)
{
Tausch(A,k,k+1);
B=B-1;
B=0;
k++;
}
}
}

void BuildArray( array A, int M, int N)
{ array B;
array C;

Initialize(A,B,C,M);
LoadInvTable(B,C,M,N);
Invert(A,B,M);
}

void Copy( array A, array B, array C, int M)
{ int i;
for (i=1;i<=M;i++)
{
B= C= A;
}
B=C=-1;
for (i=M+2;i<(2*M);i++)
{
B = C = BIG;
}
}

void main()
{ array A,B,C;
int M = Array_Size;
int N, Inv;
time_t starttime;
int sort;
int i, k;
times table;
FILE *outfile;

for (Inv = BottomInv; Inv<=TopInv; Inv++)
for (k=0; k<NoWithN; k++)
{
N = Inv;
BuildArray(A,M,N);
for (sort=0; sort<NoSorts; sort++)
{
starttime = clock();
printf("%d\n",sort);
for (i=1; i<NoTrials; i++)
{
Copy(A,B,C,M);
switch (sort)
{
case 0: BubbleSort(B,M); break;
case 1: ImprovedBubbleSort(B,M); break;
case 2: SelectionSort(B,M); break;
case 3: InsertionSort(B,M); break;
case 4: MergeSort(B,C,1,M); break;
case 5: QuickSort(B,1,M); break;
}
}
table+= clock()-starttime;
printf("%d %d: %d\n",sort,Inv,table);
}
}
outfile= fopen(filename,"w");
for (sort=0; sort<NoSorts; sort++)
for (Inv=BottomInv; Inv<=TopInv; Inv++)
fprintf(outfile,"%d %d %d\n",sort,Inv,table);
fclose(outfile);
}

Back to Paper

אל תלך בדרכי רשעים - צפוף שם