My 3 sorting functions REDUX

T

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<iomanip>
#include<cstdlib>

using namespace std;


void bubbleSort(int array[], int, int &); //function prototypes
void selectionSort(int [], int, int &);
void insertionSort(int [], 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,sSortCounter, 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("input.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(bsort, arraySize, bsortCounter);// call the sort functions
selectionSort(ssort, arraySize,sSortCounter);
insertionSort(isort, arraySize,iSortCounter);

print(numArray, arraySize, bsort, ssort, isort, bsortCounter,sSortCounter,
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 > array[i+1]) //one comparison
{

swap(array, array[i+1]); //one swap


}
}count++;
}
}// end of bubble Sort function


void selectionSort(int 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, array[tmp]); //call swap funtion

}
}//end of selection sort function

void insertionSort(int 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>tmp)

{

array[i+1]=array;

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)<<scount
<<setw(19)<< icount << endl;

}// end of print function

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

Robert Bauck Hamar

Trent said:
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.
Click to expand...

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 < array[i + 1]

you could say

++count && array < 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<iomanip>
#include<cstdlib>

using namespace std;


void bubbleSort(int array[], int, int &); //function prototypes
void selectionSort(int [], int, int &);
void insertionSort(int [], 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,sSortCounter, 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("input.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(bsort, arraySize, bsortCounter);// call the sort functions
selectionSort(ssort, arraySize,sSortCounter);
insertionSort(isort, arraySize,iSortCounter);

print(numArray, arraySize, bsort, ssort, isort, bsortCounter,sSortCounter,
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 > array[i+1]) //one comparison
{

swap(array, array[i+1]); //one swap


}
}count++;
}
}// end of bubble Sort function
Click to expand...


Here, you have the comparison inside the inner loop, but your count
increment is outside it.
void selectionSort(int array[], int size, int &count)
{
int i, j, tmp;
for (i = 0; i < size - 1; i++)
{
tmp = i;
count = count++;
Click to expand...

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

http://www.parashift.com/c++-faq-lite/misc-technical-issues.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, array[tmp]); //call swap funtion

}
}//end of selection sort function

void insertionSort(int 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>tmp)

{

array[i+1]=array;

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)<<scount
<<setw(19)<< icount << endl;

}// end of print function

void swap(int &element1, int &element2)
{
int tmp = element1;
element1 = element2;
element2 = tmp;
}
Click to expand...
 
T

Trent

Robert Bauck Hamar said:
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
Click to expand...

I cannot do that. I must comply with the pseudo code
..
array < array[i + 1]

you could say

++count && array < 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.
Click to expand...



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<iomanip>
#include<cstdlib>

using namespace std;


void bubbleSort(int array[], int, int &); //function prototypes
void selectionSort(int [], int, int &);
void insertionSort(int [], 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,sSortCounter, 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("input.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(bsort, arraySize, bsortCounter);// call the sort functions
selectionSort(ssort, arraySize,sSortCounter);
insertionSort(isort, arraySize,iSortCounter);

print(numArray, arraySize, bsort, ssort, isort,
bsortCounter,sSortCounter,
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 > array[i+1]) //one comparison
{

swap(array, array[i+1]); //one swap


}
}count++;
}
}// end of bubble Sort function
Click to expand...


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


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<iomanip>
#include<cstdlib>

using namespace std;


void bubbleSort(int array[], int, int &); //function prototypes
void selectionSort(int [], int, int &);
void insertionSort(int [], 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,sSortCounter, 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("input.txt"); //opening input file
if (!inFile)
{
cerr << "Error Opening File" << endl;
system("pause");
EXIT_FAILURE; //stop program on failure
}

outFile.open("output.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(bsort, arraySize, bsortCounter);// call the sort functions
selectionSort(ssort, arraySize,sSortCounter);
insertionSort(isort, arraySize,iSortCounter);

print(numArray, arraySize, bsort, ssort, isort, bsortCounter,sSortCounter,
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 > array[i+1]) //one comparison
{
count++;
swap(array, array[i+1]); //one swap and call swap
function


}
}
}
}// end of bubble Sort function


void selectionSort(int 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, array[tmp]); //call swap funtion
count++;
}
}//end of selection sort function

void insertionSort(int 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>tmp)

{

array[i+1]=array;

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)<<scount
<<setw(19)<< icount << endl;

}// end of print function

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

BobR

Trent said:
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]
Click to expand...
Click to expand...

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<iomanip>
#include<cstdlib>
using namespace std;
[ snip declarations ]
Click to expand...
// > 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)
Click to expand...
// > inFile.open("input.txt"); file://opening input file

ifstream inFile("input.txt"); file://opening input file
if (!inFile){
cerr << "Error Opening File" << endl;
system("pause");
Click to expand...
// > EXIT_FAILURE; file://stop program on failure
return EXIT_FAILURE; file://stop program on failure
}
Click to expand...
// > outFile.open("output.txt"); file://opening input file

ofstream outFile("output.txt"); file://opening input file
if (!outFile){
cerr << "Error Opening File" << endl;
system("pause");
Click to expand...
// > 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(bsort, arraySize, bsortCounter);// call the sort functions
selectionSort(ssort, arraySize,sSortCounter);
insertionSort(isort, arraySize,iSortCounter);

print(numArray, arraySize, bsort, ssort, isort, bsortCounter,sSortCounter,
iSortCounter);\
}
cout << endl;
inFile.close();// close files
outFile.close();
system("pause");
return EXIT_SUCCESS;
} // main()
Click to expand...
// Funtions below

void bubbleSort(int array[], int size, int &count){
Click to expand...

// > 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
{
Click to expand...
// > for (i= 0; i < size - 1; i++) // one pass
for( int i(0); i < size - 1; ++i ) // one pass
{
if (array > array[i+1]) file://one comparison
{
count++;
swap(array, array[i+1]); file://one swap and call swap
function
}
}
}
}// end of bubble Sort function
Click to expand...


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

void MyFunc( std::eek:stream &out ){
out<<"Hello World!"<<std::endl;
}

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

Juha Nieminen

Trent said:
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
Click to expand...

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...
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Fot those with extra time.. sorting question 11
What is Error 1 error LNK2019: unresolved external symbol ???? 9
Help understand probems - Binary Search and Sequenital Search 5
How can I make a better program from the following one 1
Speed up creation of combo box options 2
OK ... AGE FUNCTION TEST RESULTS ... 1
Random Number Not Seeding 4

Members online

Total: 26 (members: 2, guests: 24)
Robots: 369

Forum statistics

Threads
473,770
Messages
2,569,583
Members
45,072
Latest member
trafficcone

Latest Threads

Top