My 3 sorting functions REDUX

[Trent]

Still have problems with this thing.

Seems my results are not matching the "correct" example given.
The three sets of numbers below the last 3 columns is suppose to be the
number of comparisons made by eahc sorting function.

I have having trouble getting the number of comparisons to match. One
comment was that "the counts are in the wrongs place," but I have moved them
all over the function and still they do not match.

Thanks to all have given advice so far.
Trent

Output and code below:

=============== ="CORRECT" OUTPUT========= ===

Unsorted List Bubble Sorted Insertion Sorted Selection Sorted

678 678 678 678
850 850 850 850
999 999 999 999
1050 1050 1050 1050
1222 1222 1222 1222
1325 1325 1325 1325
1444 1444 1444 1444
1600 1600 1600 1600
1900 1900 1900 1900
1900 1900 1900 1900

9 9 45

Unsorted List Bubble Sorted Insertion Sorted Selection Sorted

1600 231 231 231
1444 231 231 231
1325 678 678 678
1222 850 850 850
1050 999 999 999
999 1050 1050 1050
850 1222 1222 1222
678 1325 1325 1325
231 1444 1444 1444
231 1600 1600 1600

81 45 45

Unsorted List Bubble Sorted Insertion Sorted Selection Sorted

1444 678 678 678
850 850 850 850
999 999 999 999
678 1050 1050 1050
1222 1050 1050 1050
1050 1222 1222 1222
1325 1325 1325 1325
1600 1444 1444 1444
1900 1600 1600 1600
1050 1900 1900 1900

54 21 45

Unsorted List Bubble Sorted Insertion Sorted Selection Sorted

999 231 231 231
850 231 231 231
678 678 678 678
231 850 850 850
1222 999 999 999
1325 1222 1222 1222
1444 1325 1325 1325
1600 1444 1444 1444
1900 1600 1600 1600
231 1900 1900 1900

81 20 45

Unsorted List Bubble Sorted Insertion Sorted Selection Sorted

850 231 231 231
999 678 678 678
1050 850 850 850
1222 999 999 999
1325 1050 1050 1050
1444 1222 1222 1222
1600 1325 1325 1325
1900 1444 1444 1444
678 1600 1600 1600
231 1900 1900 1900

90 24 45
=============== =MY OUTPUT========= =======
Unsorted List Bubble Sorted Selection Sorted Insertion Sorted
231 231 231 231
678 678 678 678
850 850 850 850
999 999 999 999
1050 1050 1050 1050
1222 1222 1222 1222
1325 1325 1325 1325
1444 1444 1444 1444
1600 1600 1600 1600
1900 1900 1900 1900

Number: 9 9 9

Unsorted List Bubble Sorted Selection Sorted Insertion Sorted
1900 231 231 231
1600 678 678 678
1444 850 850 850
1325 999 999 999
1222 1050 1050 1050
1050 1222 1222 1222
999 1325 1325 1325
850 1444 1444 1444
678 1600 1600 1600
231 1900 1900 1900

Number: 18 18 18

Unsorted List Bubble Sorted Selection Sorted Insertion Sorted
231 231 231 231
1444 678 678 678
850 850 850 850
999 999 999 999
678 1050 1050 1050
1222 1222 1222 1222
1050 1325 1325 1325
1325 1444 1444 1444
1600 1600 1600 1600
1900 1900 1900 1900

Number: 27 27 27

Unsorted List Bubble Sorted Selection Sorted Insertion Sorted
1050 231 231 231
999 678 678 678
850 850 850 850
678 999 999 999
231 1050 1050 1050
1222 1222 1222 1222
1325 1325 1325 1325
1444 1444 1444 1444
1600 1600 1600 1600
1900 1900 1900 1900

Number: 36 36 36

Unsorted List Bubble Sorted Selection Sorted Insertion Sorted
231 231 231 231
850 678 678 678
999 850 850 850
1050 999 999 999
1222 1050 1050 1050
1325 1222 1222 1222
1444 1325 1325 1325
1600 1444 1444 1444
1900 1600 1600 1600
678 1900 1900 1900

Number: 45 45 45


=============== =CODE========== ======

#include <iostream>
#include <fstream>
#include<iomani p>
#include<cstdli b>

using namespace std;
void bubbleSort(int array[], int, int &); //function prototypes
void selectionSort(i nt [], int, int &);
void insertionSort(i nt [], int, int &);
void swap(int &, int &);
void print(int array[], int size, int bubbleSort[], int selectionSort[], int
insertionSort[], int bcount, int scount, int icount);
// print(&numArray , arraySize, &bsort, &ssort, &isort,
bsortCounter,sS ortCounter, iSortCounter);

ifstream inFile;
ofstream outFile;

int main()
{

const int arraySize = 10;
int numArray[arraySize];
int bsort[arraySize];
int bsortCounter =0;
int isort[arraySize];
int iSortCounter =0;
int ssort[arraySize];
int sSortCounter =0;
// each sort needs array and counter (parallel arrays)
inFile.open("in put.txt"); //opening input file
if (!inFile)
{
cerr << "Error Opening File" << endl;
system("pause") ;
EXIT_FAILURE; //stop program on failure
}
for (int i =0;i < 5;i++)
{
for (int j=0; j< arraySize;j++)
{
inFile >numArray[j];
bsort[j]=numArray[j];
isort[j]=numArray[j];
ssort[j]=numArray[j];
}

cout << endl;
bubbleSort(bsor t, arraySize, bsortCounter);// call the sort functions
selectionSort(s sort, arraySize,sSort Counter);
insertionSort(i sort, arraySize,iSort Counter);

print(numArray, arraySize, bsort, ssort, isort, bsortCounter,sS ortCounter,
iSortCounter);\

}

cout << endl;
system("pause") ;

inFile.close();// close files
outFile.close() ;
return 0;
}

// Funtions below


void bubbleSort(int array[], int size, int &count)
{
int i, pass, flag;
for (pass =0; pass < size - 1; pass++) //# of passes
{
for (i= 0; i < size - 1; i++) // one pass
{

if (array[i] array[i+1]) //one comparison
{

swap(array[i], array[i+1]); //one swap
}
}count++;
}
}// end of bubble Sort function
void selectionSort(i nt array[], int size, int &count)
{
int i, j, tmp;
for (i = 0; i < size - 1; i++)
{
tmp = i;
count = count++;
for (j = i+1; j < size; j++)
if (array[j] < array[tmp])
{
tmp = j;
}

swap(array[i], array[tmp]); //call swap funtion

}
}//end of selection sort function

void insertionSort(i nt array[],int size, int &count)
{
int tmp,i;
for(int j=1;j<size;j++)
{
tmp=array[j];
i=j-1;
while(i>=0 && array[i]>tmp)

{

array[i+1]=array[i];

i--;

}
array[i+1]=tmp;
count++;
}
}
void print(int array[], int size, int bubbleSort[], int selectionSort[], int
insertionSort[], int bcount, int scount, int icount)
{
cout << " Unsorted List Bubble Sorted Selection Sorted Insertion
Sorted" << endl;

for (int k =0;k < size;k++)
cout << setw(15) <<array[k] << setw(16) << bubbleSort[k] << setw(20) <<
selectionSort[k] << setw(19) << insertionSort[k] << endl;
cout << endl << "Number: " << setw(23) <<bcount << setw(20)<<scoun t
<<setw(19)<< icount << endl;

}// end of print function

void swap(int &element1, int &element2)
{
int tmp = element1;
element1 = element2;
element2 = tmp;
}

[Robert Bauck Hamar]

Trent wrote:

Still have problems with this thing.

Seems my results are not matching the "correct" example given.
The three sets of numbers below the last 3 columns is suppose to be the
number of comparisons made by eahc sorting function.

I have having trouble getting the number of comparisons to match. One
comment was that "the counts are in the wrongs place," but I have moved
them all over the function and still they do not match.

If you take advantage of the fact that ints can be converted to bools, you
can move the incrementation of the count into the comparisons. If the
comparison was

array[i] < array[i + 1]

you could say

++count && array[i] < array[i + 1]

If count was initialised to 0, the expression ++count would always compare
true, and the && operator would always return the old comparison. This
would always work, but to solve your problem, try to hand trace the code
for a small input sample. Use a piece of paper, and write down the values
in your variables, and keep track of the changes made in each statement.

Output and code below:

[snip output]

>
#include <iostream>
#include <fstream>
#include<iomani p>
#include<cstdli b>

using namespace std;
void bubbleSort(int array[], int, int &); //function prototypes
void selectionSort(i nt [], int, int &);
void insertionSort(i nt [], int, int &);
void swap(int &, int &);
void print(int array[], int size, int bubbleSort[], int selectionSort[],
int insertionSort[], int bcount, int scount, int icount);
// print(&numArray , arraySize, &bsort, &ssort, &isort,
bsortCounter,sS ortCounter, iSortCounter);

ifstream inFile;
ofstream outFile;

int main()
{

const int arraySize = 10;
int numArray[arraySize];
int bsort[arraySize];
int bsortCounter =0;
int isort[arraySize];
int iSortCounter =0;
int ssort[arraySize];
int sSortCounter =0;
// each sort needs array and counter (parallel arrays)
inFile.open("in put.txt"); //opening input file
if (!inFile)
{
cerr << "Error Opening File" << endl;
system("pause") ;
EXIT_FAILURE; //stop program on failure
}
for (int i =0;i < 5;i++)
{
for (int j=0; j< arraySize;j++)
{
inFile >numArray[j];
bsort[j]=numArray[j];
isort[j]=numArray[j];
ssort[j]=numArray[j];
}

cout << endl;
bubbleSort(bsor t, arraySize, bsortCounter);// call the sort functions
selectionSort(s sort, arraySize,sSort Counter);
insertionSort(i sort, arraySize,iSort Counter);

print(numArray, arraySize, bsort, ssort, isort, bsortCounter,sS ortCounter,
iSortCounter);\

}

cout << endl;
system("pause") ;

inFile.close();// close files
outFile.close() ;
return 0;
}

// Funtions below


void bubbleSort(int array[], int size, int &count)
{
int i, pass, flag;
for (pass =0; pass < size - 1; pass++) //# of passes
{
for (i= 0; i < size - 1; i++) // one pass
{

if (array[i] array[i+1]) //one comparison
{

swap(array[i], array[i+1]); //one swap
}
}count++;
}
}// end of bubble Sort function

Here, you have the comparison inside the inner loop, but your count
increment is outside it.

void selectionSort(i nt array[], int size, int &count)
{
int i, j, tmp;
for (i = 0; i < size - 1; i++)
{
tmp = i;
count = count++;

Here, you are modifying count twice in the same statement. This is undefined
behaviour. Read this:

http://www.parashift.com/c++-faq-lit...html#faq-39.15

Undefined behaviour means anything could happen, but the likely results
right here is that 1) count stays the same and 2) count is incremented.
Different compilers and/or compiler settings may give different results.
Most compilers should be able to warn you about this, however.

for (j = i+1; j < size; j++)
if (array[j] < array[tmp])
{
tmp = j;
}

swap(array[i], array[tmp]); //call swap funtion

}
}//end of selection sort function

void insertionSort(i nt array[],int size, int &count)
{
int tmp,i;
for(int j=1;j<size;j++)
{
tmp=array[j];
i=j-1;
while(i>=0 && array[i]>tmp)

{

array[i+1]=array[i];

i--;

}
array[i+1]=tmp;
count++;
}
}
void print(int array[], int size, int bubbleSort[], int selectionSort[],
int insertionSort[], int bcount, int scount, int icount)
{
cout << " Unsorted List Bubble Sorted Selection Sorted
Insertion
Sorted" << endl;

for (int k =0;k < size;k++)
cout << setw(15) <<array[k] << setw(16) << bubbleSort[k] << setw(20)
<<
selectionSort[k] << setw(19) << insertionSort[k] << endl;
cout << endl << "Number: " << setw(23) <<bcount << setw(20)<<scoun t
<<setw(19)<< icount << endl;

}// end of print function

void swap(int &element1, int &element2)
{
int tmp = element1;
element1 = element2;
element2 = tmp;
}

--
rbh

[Trent]

"Robert Bauck Hamar" <ro**********@i fi.uio.nowrote in message
news:f6******** **@readme.uio.n o...

Trent wrote:

>Still have problems with this thing.

Seems my results are not matching the "correct" example given.
The three sets of numbers below the last 3 columns is suppose to be the
number of comparisons made by eahc sorting function.

I have having trouble getting the number of comparisons to match. One
comment was that "the counts are in the wrongs place," but I have moved
them all over the function and still they do not match.

If you take advantage of the fact that ints can be converted to bools, you
can move the incrementation of the count into the comparisons. If the
comparison was

I cannot do that. I must comply with the pseudo code
..

array[i] < array[i + 1]

you could say

++count && array[i] < array[i + 1]

If count was initialised to 0, the expression ++count would always compare
true, and the && operator would always return the old comparison. This
would always work, but to solve your problem, try to hand trace the code
for a small input sample. Use a piece of paper, and write down the values
in your variables, and keep track of the changes made in each statement.

I have gone over and over them and still do not match for reasons I do not
know.
Only thing I can think of is the two algorithihms are just not operating the
same.

>Output and code below:

[snip output]

>>
#include <iostream>
#include <fstream>
#include<ioman ip>
#include<cstdl ib>

using namespace std;
void bubbleSort(int array[], int, int &); //function prototypes
void selectionSort(i nt [], int, int &);
void insertionSort(i nt [], int, int &);
void swap(int &, int &);
void print(int array[], int size, int bubbleSort[], int selectionSort[],
int insertionSort[], int bcount, int scount, int icount);
// print(&numArray , arraySize, &bsort, &ssort, &isort,
bsortCounter,s SortCounter, iSortCounter);

ifstream inFile;
ofstream outFile;

int main()
{

const int arraySize = 10;
int numArray[arraySize];
int bsort[arraySize];
int bsortCounter =0;
int isort[arraySize];
int iSortCounter =0;
int ssort[arraySize];
int sSortCounter =0;
// each sort needs array and counter (parallel arrays)
inFile.open("in put.txt"); //opening input file
if (!inFile)
{
cerr << "Error Opening File" << endl;
system("pause") ;
EXIT_FAILURE; //stop program on failure
}
for (int i =0;i < 5;i++)
{
for (int j=0; j< arraySize;j++)
{
inFile >numArray[j];
bsort[j]=numArray[j];
isort[j]=numArray[j];
ssort[j]=numArray[j];
}

cout << endl;
bubbleSort(bso rt, arraySize, bsortCounter);// call the sort functions
selectionSort( ssort, arraySize,sSort Counter);
insertionSort( isort, arraySize,iSort Counter);

print(numArray , arraySize, bsort, ssort, isort,
bsortCounter,s SortCounter,
iSortCounter); \

}

cout << endl;
system("pause") ;

inFile.close();// close files
outFile.close() ;
return 0;
}

// Funtions below


void bubbleSort(int array[], int size, int &count)
{
int i, pass, flag;
for (pass =0; pass < size - 1; pass++) //# of passes
{
for (i= 0; i < size - 1; i++) // one pass
{

if (array[i] array[i+1]) //one comparison
{

swap(array[i], array[i+1]); //one swap
}
}count++;
}
}// end of bubble Sort function

Here, you have the comparison inside the inner loop, but your count
increment is outside it.

Yes. I was still playing around. I now have all count++ with the swaps.
In addtion I must change part of the code. Notice in main() I am
making a copy of the array that read read in from the file into other
arrays.
The change I must make is to doing to copying from inside each function.

That is the part that is confusing me.
My thinking is I have to make yet another array and pass numArray to the
function then copy the pass to the inside array.
Did not work.

Suggestions?

Thanks for the assistance you have given.

Trent
The newest code below:

#include <iostream>
#include <fstream>
#include<iomani p>
#include<cstdli b>

using namespace std;
void bubbleSort(int array[], int, int &); //function prototypes
void selectionSort(i nt [], int, int &);
void insertionSort(i nt [], int, int &);
void swap(int &, int &);
void print(int array[], int size, int bubbleSort[], int selectionSort[], int
insertionSort[], int bcount, int scount, int icount);
// print(&numArray , arraySize, &bsort, &ssort, &isort,
bsortCounter,sS ortCounter, iSortCounter);

ifstream inFile;
ofstream outFile;

int main()
{

const int arraySize = 10;
int numArray[arraySize];
int bsort[arraySize];
int bsortCounter =0;
int isort[arraySize];
int iSortCounter =0;
int ssort[arraySize];
int sSortCounter =0;
// each sort needs array and counter (parallel arrays)
inFile.open("in put.txt"); //opening input file
if (!inFile)
{
cerr << "Error Opening File" << endl;
system("pause") ;
EXIT_FAILURE; //stop program on failure
}

outFile.open("o utput.txt"); //opening input file
if (!outFile)
{
cerr << "Error Opening File" << endl;
system("pause") ;
EXIT_FAILURE; //stop program on failure
}

for (int i =0;i < 5;i++)
{
for (int j=0; j< arraySize;j++)
{
inFile >numArray[j];
bsort[j]=numArray[j];
isort[j]=numArray[j];
ssort[j]=numArray[j];
}

cout << endl;
bubbleSort(bsor t, arraySize, bsortCounter);// call the sort functions
selectionSort(s sort, arraySize,sSort Counter);
insertionSort(i sort, arraySize,iSort Counter);

print(numArray, arraySize, bsort, ssort, isort, bsortCounter,sS ortCounter,
iSortCounter);\

}

cout << endl;

inFile.close();// close files
outFile.close() ;

system("pause") ;
return EXIT_SUCCESS;
}

// Funtions below

void bubbleSort(int array[], int size, int &count)
{
int i, pass;
for (pass =0; pass < size - 1; pass++) //# of passes
{
for (i= 0; i < size - 1; i++) // one pass
{

if (array[i] array[i+1]) //one comparison
{
count++;
swap(array[i], array[i+1]); //one swap and call swap
function
}
}
}
}// end of bubble Sort function
void selectionSort(i nt array[], int size, int &count)
{
int i, j, tmp;
for (i = 0; i < size - 1; i++)
{
tmp = i;

for (j = i+1; j < size; j++)
{

if (array[j] < array[tmp])
{

tmp = j;
}

}
swap(array[i], array[tmp]); //call swap funtion
count++;
}
}//end of selection sort function

void insertionSort(i nt array[],int size, int &count)
{
int tmp,i;
for(int j=1;j<size;j++)
{
tmp=array[j];
i=j-1;
while(i>=0 && array[i]>tmp)

{

array[i+1]=array[i];

i--;

}
array[i+1]=tmp;
count++;
}
}
void print(int array[], int size, int bubbleSort[], int selectionSort[], int
insertionSort[], int bcount, int scount, int icount)
{
cout << " Unsorted List Bubble Sorted Selection Sorted Insertion
Sorted" << endl;

for (int k =0;k < size;k++)
cout << setw(15) <<array[k] << setw(16) << bubbleSort[k] << setw(20) <<
selectionSort[k] << setw(19) << insertionSort[k] << endl;
cout << endl << "Number: " << setw(23) <<bcount << setw(20)<<scoun t
<<setw(19)<< icount << endl;

}// end of print function

void swap(int &element1, int &element2)
{
int tmp = element1;
element1 = element2;
element2 = tmp;
}

[BobR]

Trent <tr***@nerd.com wrote in message...

>
I have gone over and over them and still do not match for reasons I do not
know.
Only thing I can think of is the two algorithihms are just not operating

the

same.

[snip output]

Why didn't you remove the old code when you posted new code?

>
Yes. I was still playing around. I now have all count++ with the swaps.
In addtion I must change part of the code. Notice in main() I am
making a copy of the array that read read in from the file into other
arrays.
The change I must make is to doing to copying from inside each function.

That is the part that is confusing me.
My thinking is I have to make yet another array and pass numArray to the
function then copy the pass to the inside array.
Did not work.
Suggestions?
Thanks for the assistance you have given.
Trent

The newest code below:

#include <iostream>
#include <fstream>
#include<iomani p>
#include<cstdli b>
using namespace std;

[ snip declarations ]

>

// ifstream inFile;
// ofstream outFile;
You only use these in main(), so move them there. [1]

>
int main(){

const int arraySize = 10;
int numArray[arraySize];
int bsort[arraySize];
int bsortCounter =0;
int isort[arraySize];
int iSortCounter =0;
int ssort[arraySize];
int sSortCounter =0;
// each sort needs array and counter (parallel arrays)

// inFile.open("in put.txt"); file://opening input file

ifstream inFile("input.t xt"); file://opening input file

if (!inFile){
cerr << "Error Opening File" << endl;
system("pause") ;

// EXIT_FAILURE; file://stop program on failure
return EXIT_FAILURE; file://stop program on failure

}

// outFile.open("o utput.txt"); file://opening input file

ofstream outFile("output .txt"); file://opening input file

if (!outFile){
cerr << "Error Opening File" << endl;
system("pause") ;

// EXIT_FAILURE; file://stop program on failure
return EXIT_FAILURE; file://stop program on failure

}

for (int i =0;i < 5;i++){
for (int j=0; j< arraySize;j++){
inFile >numArray[j];
bsort[j]=numArray[j];
isort[j]=numArray[j];
ssort[j]=numArray[j];
}

cout << endl;
bubbleSort(bsor t, arraySize, bsortCounter);// call the sort functions
selectionSort(s sort, arraySize,sSort Counter);
insertionSort(i sort, arraySize,iSort Counter);

print(numArray, arraySize, bsort, ssort, isort, bsortCounter,sS ortCounter,
iSortCounter);\
}
cout << endl;
inFile.close();// close files
outFile.close() ;
system("pause") ;
return EXIT_SUCCESS;
} // main()

>
// Funtions below

void bubbleSort(int array[], int size, int &count){

// int i, pass;
// for (pass =0; pass < size - 1; pass++) file://# of passes

// This is 'C' style code. You do not use 'pass' or 'i' outside the
// for loop, so do it like this (same in your other functions):

for( int pass(0); pass < size - 1; ++pass ) file://# of passes

{

// for (i= 0; i < size - 1; i++) // one pass
for( int i(0); i < size - 1; ++i ) // one pass

{
if (array[i] array[i+1]) file://one comparison
{
count++;
swap(array[i], array[i+1]); file://one swap and call swap
function
}
}
}
}// end of bubble Sort function

[1] If you need to output to a file from a function outside main(), you can
do it like this:

void MyFunc( std::ostream &out ){
out<<"Hello World!"<<std::e ndl;
}

{ in main()
// open outFile
MyFunc( outFile );
MyFunc( std::cout ); // also works
}

--
Bob R
POVrookie

[Juha Nieminen]

Trent wrote:

void bubbleSort(int array[], int size, int &count)
{
int i, pass, flag;
for (pass =0; pass < size - 1; pass++) //# of passes
{
for (i= 0; i < size - 1; i++) // one pass

Btw, note that after each pass the largest item will end up at
the end of the array. Thus it's useless to test the last item in
the array with the second-to-last. In the second pass you can loop
one less than in the first pass and still get a correct answer.
Likewise in the third pass you can loop one less than in the second
pass, and so on.

Not that it makes bubblesort any better, but...