also, i need mike to explain this:

Tuesday, March 11, 2003

//
// Stationery for AP classes
// 031398 -- RGrehan, Metrowerks, Inc.

// Includes
#include "apvector.h"
#include "apqueue.h"
#include "apstack.h"
#include "apstring.h"
#include "apmatrix.h"

// Define objects
apvector intVector; // Integer vector
apqueue intQueue; // Integer queue
apstack intStack; // Integer stack
apstring myString; // String
apmatrix intMatrix(5,5,3); // Integer matrix
void Insertion (apvector, int &, int &);
void print_values (apvector);
void Selection (apvector , int &, int &);

int main()
{
apvector A(5);
A[0] = 5;
A[1] = 4;
A[2] = 3;
A[3] = 2;
A[4] = 1;

int comparison_count = 0;
int switch_count = 0;

Insertion(A, comparison_count, switch_count);

int insertion_comp_count = comparison_count;
int insertion_switch_count = switch_count;
comparison_count = 0;
switch_count = 0;

Selection(A, comparison_count, switch_count);

}

void Insertion (apvector arr, int & comparison_count, int & switch_count)
{
cout << "******* INSERTION SORT ********";
cout << endl;
cout << "THE ARRAY NOW APPEARS : ";
print_values(arr);
cout << endl;
int i, j;
int temp;
for ( i = 1; i < arr.length(); i++ )
{
temp = arr[i];
j = i;
while ( j > 0 && temp < arr[j-1] )
{
cout << temp;
cout << " is compared with ";
cout << arr[j-1];
comparison_count++;
cout << endl;
arr[j] = arr[j-1];
j--;
}
cout << arr[j];
cout << " is switched with ";
cout << temp;
cout << endl;

arr[j] = temp;
switch_count++;

}
cout << "Total Comparisons : ";
cout << comparison_count;
cout << endl;
cout << "Total Switchs : ";
cout << switch_count;
cout << endl;
cout << "THE ARRAY NOW APPEARS : ";
print_values(arr);
cout << endl;
}

void Selection(apvector a, int & comparisoncount, int & switchcount)

// Sort a[0], ..., a[size-1] in ascending order.

{
cout << endl;
cout << "SELECTION SORT : ";
cout << endl;
int i, iMax, n;
double aTemp;
int size = a.length();

for (n = size; n >= 2; n--) {
// Find the index "iMax" of the largest element
// among a[0], ..., a[n-1]:

iMax = 0;
for (i = 1; i < n -1 ; i++)
cout << a[i];
cout << " is compared with ";
cout << a[iMax];
cout << endl;
if (a[i] > a[iMax])
iMax = i;

// Swap a[iMax] with a[n-1]:
cout << a[n - 1];
cout << " is switched with ";
cout << a[iMax];
cout << endl;
aTemp = a[iMax]; // Save a[iMax] in a temporary location.
a[iMax] = a[n-1]; // Copy a[n-1] to a[iMax].
a[n-1] = aTemp; // Copy saved value to a[n-1].
//print_values(a);
//cout << endl;
// Decrement n (accomplished by n-- in the "for" loop).
}
print_values(a);
cout << endl;
switchcount = size - 1;
comparisoncount = (size / 2)*(size - 1);

cout << "Total Comparisons : ";
cout << comparisoncount;
cout << endl;

cout << "Total Switches : " ;
cout << switchcount;
cout << endl;
}




void print_values (apvector A)
{
for(int i = 0; i < A.length(); i++)
cout << A[i];
}

- Mike, 6:47 AM

Monday, March 10, 2003

//
// Stationery for AP classes
// 031398 -- RGrehan, Metrowerks, Inc.

// Includes
#include "apvector.h"
#include "apqueue.h"
#include "apstack.h"
#include "apstring.h"
#include "apmatrix.h"
#include "fstream.h"
// Define objects
apvector intVector; // Integer vector
apqueue intQueue; // Integer queue
apstack intStack; // Integer stack
apstring myString; // String
apmatrix intMatrix(5,5,3); // Integer matrix
//void insertionsort (apvector, int &, int &);
void changearray (/*apvector, int, int, int*/void);
void print_values (apvector);
int NUMBER = 0;
void sel_sort (apvector , int &, int &);
void BubbleSort (apvector, int &, int &);
void Insertion (apvector, int &, int&);

void shortcircuit (apvector v, int & comparisoncount, int & switchcount);

int main()
{
fstream I;
fstream J;
fstream f1;
apvector a (5);

f1.open("numbers.txt", ios :: app);



a[4] = 4;
a[3] = 3;
a[2] = 2;
a[1] = 5;
a[0] = 1;
char choice = 'n';
int switchcount = 0;
int comparisoncount = 0;
//insertionsort(a,comparisoncount,switchcount);
cout << "WOULD YOU LIKE TO SEE THE INSERTION SORT? (Y/N) :";
cin >> choice;
if (choice == 'Y')
{
sel_sort(a, comparisoncount, switchcount);
int sel_switch = switchcount;
int sel_compare = comparisoncount;
switchcount = 0;
comparisoncount = 0;
}
//BubbleSort(a, comparisoncount, switchcount);
//insertionsort(a,comparisoncount,switchcount);
//int bubbleswitch = switchcount;
//int bubblescompare = comparisoncount;
//switchcount = 0;
//comparisoncount = 0;
choice = 'n';
cout << "WOULD YOU LIKE TO SEE THE INSERTION SORT? (Y/N) : ";
cin >> choice;
if(choice == 'Y')
{
Insertion(a, comparisoncount, switchcount);
int insertionswitch = switchcount;
int insertioncompare = comparisoncount;
switchcount = 0;
comparisoncount = 0;
}
choice = 'n';
cout << "WOULD YOU LIKE TO SEE THE BUBBLE SORT? (Y/N) : ";
cin >> choice;
if(choice == 'Y')
{
BubbleSort(a, comparisoncount, switchcount);
//insertionsort(a,comparisoncount,switchcount);
int bubbleswitch = switchcount;
int bubblescompare = comparisoncount;
switchcount = 0;
comparisoncount = 0;
}
choice = 'n';
cout << "WOULD YOU LIKE TO SEE THE EFFICIENT BUBBLE SORT? (Y/N) :";
cin >> choice;
if(choice == 'Y')
{
shortcircuit(a, comparisoncount, switchcount);
}
}

void insertionsort (apvector A, int & comparisoncount, int & switchcount)
{
cout << endl;
cout << "INSERTION SORT : ";
cout << endl;
int temp;
//int switchcount = 0;
int counter2 = 0;
int counter = 0;
int i = 1;
//int comparisoncount = 0;
int len = A.length();
for(int i = 1; i <= len-1; i++)
{
//if(i == 1)
//{
//cout << " (th)(rd)(st)(nd)";
print_values(A);
cout << endl;
//}
counter++;
switchcount++;

for(int j = i - 1; j >= 0; j--)
{
if(A[i] < A[j])
{
temp = A[i];

while (i > j)
{
A[i] = A[i -1];
comparisoncount++;
changearray();
i--;

}
A[j] = temp;


}


}



}
cout << "THE NUMBER OF SWITCHES WAS : ";
cout << switchcount;
cout << endl;
cout << "THE NUMBER OF COMPARISONS WAS : ";
cout << comparisoncount;
cout << endl;
//i++;

}




void changearray (apvector A,int i,int j,int tem)
{
NUMBER++;
//while(i > j)
// A[i - 1] = A[i];
//A[j] = temp;
//print_values(A);
}

void print_values (apvector A)
{
for(int i = 0; i < A.length(); i++)
cout << A[i];
}


void sel_sort(apvector a, int & comparisoncount, int & switchcount)

// Sort a[0], ..., a[size-1] in ascending order.

{
cout << endl;
cout << "SELECTION SORT : ";
cout << endl;
int i, iMax, n;
double aTemp;
int size = a.length();

for (n = size; n >= 2; n--) {
print_values(a);
cout << endl;
// Find the index "iMax" of the largest element
// among a[0], ..., a[n-1]:

iMax = 0;
for (i = 1; i < n; i++)
if (a[i] > a[iMax])
iMax = i;

// Swap a[iMax] with a[n-1]:

aTemp = a[iMax]; // Save a[iMax] in a temporary location.
a[iMax] = a[n-1]; // Copy a[n-1] to a[iMax].
a[n-1] = aTemp; // Copy saved value to a[n-1].
//print_values(a);
//cout << endl;
// Decrement n (accomplished by n-- in the "for" loop).
}
print_values(a);
cout << endl;
switchcount = size - 1;
comparisoncount = (size / 2)*(size - 1);
cout << "THE NUMBER OF SWITCHES WAS : " ;
cout << switchcount;
cout << endl;
cout << "THE NUMBER OF COMPARISONS WAS : ";
cout << comparisoncount;
cout << endl;
}

//****************************************************************
//*********** Bubble sort **************
//****************************************************************

void BubbleSort (apvector v, int & comparisoncount, int & switchcount)
{ cout << endl;
cout << "THE BUBBLE SORT : ";
cout << endl;
int i, n = v.length(), temp;
print_values(v);
cout << endl;
while (n > 1)
{
for (i = 1; i < n; i++)
{
if (v[i - 1] > v[i]) // if left side is greater than right side
{
temp = v[i];
v[i] = v[i-1];
v[i-1] = temp;
switchcount++;
print_values(v);
cout << endl;
}
}
n--;
}
comparisoncount = (((v.length() * v.length()) - v.length()) / 2);
cout << "THE NUMBER OF COMPARISONS WAS : ";
cout << comparisoncount;
cout << endl;
cout << "THE NUMBER OF SWITCHES WAS : ";
cout << switchcount;
cout << endl;
}



void Insertion (apvector arr, int & comparisoncount, int & switchcount)
{
int i, j;
int temp;
cout << endl;
cout << "INSERTION SORT : ";
cout << endl;
print_values(arr);
cout << endl;
for ( i = 1; i < arr.length(); i++ ) {
temp = arr[i];
j = i;
comparisoncount++;
while ( j > 0 && temp < arr[j-1] ) {
arr[j] = arr[j-1];
//print_values(arr);
//cout << endl;
switchcount++;
j--;
if ( j > 0 )
comparisoncount++;
}
arr[j] = temp;
switchcount++;
print_values(arr);
cout << endl;
}
cout << "THE NUMBER OF COMPARISONS WAS : ";
cout << comparisoncount;
cout << endl;
cout << "THE NUMBER OF SWITCHES WAS : ";
cout << switchcount;
cout << endl;
}


//****************************************************************
//*********** short circuiting sort **************
//****************************************************************

void shortcircuit (apvector v, int & comparisoncount, int & switchcount)
{ cout << endl;
cout << "THE MORE EFFIECENT BUBBLE SORT : ";
cout << endl;
int i, n = v.length(), temp;
int switchcount2;
print_values(v);
cout << endl;
while (n > 1)
{
for (i = 1; i < n; i++)
{
switchcount2 = switchcount;
if (v[i - 1] > v[i]) // if left side is greater than right side
{
temp = v[i];
v[i] = v[i-1];
v[i-1] = temp;
switchcount++;
print_values(v);
cout << endl;
if(switchcount2 == switchcount)
n = 1;
}
}
n--;
}
comparisoncount = (((v.length() * v.length()) - v.length()) / 2);
cout << "THE NUMBER OF COMPARISONS WAS : ";
cout << comparisoncount;
cout << endl;
cout << "THE NUMBER OF SWITCHES WAS : ";
cout << switchcount;
cout << endl;
}