Fot those with extra time.. sorting question

[Trent]

Running this I see that on first run, both bubble and selection sort have 9
sort counts while insertion sort has ZERO. With a sorted list, should this
be ZERO for all?

Also bsort and Ssort have the same exact sorting counts also..shouldn't they
differ somewhat?

Source and data file below.

Thanks

Trent

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

using namespace std;
void bubbleSort(int *array, const int, int &); //function prototypes
void selectionSort(i nt *, const int, int &);
void insertionSort(i nt *, const 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") ;
return -1;
}
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, const int size, int &count)
{
int i, pass;
for (pass =0; pass < size - 1; pass++) //# of passes
count= count+1;

for (i= 0; i < size - 1; i++) // one pass
if (array[i] array[i+1]) //one comparison
{
swap(array[i], array[i+1]);
}

}// end of bubble Sort function
void selectionSort(i nt *array, const int size, int &count)
{
int i, j, tmp;
for (i = 0; i < size - 1; i++)
{
tmp = i;
count = count + 1;
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,const int size, int &count)
{
int tmp,i;
for(int j=1;j<size;j++)
{
tmp=array[j];
i=j-1;
while(array[i]>tmp && i>=0)
{
count = count +1;
array[i+1]=array[i];
i--;
}
array[i+1]=tmp;
}
}
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;
}
----------------------
Data Input File
----------------------

231
678
850
999
1050
1222
1325
1444
1600
1900

1900
1600
1444
1325
1222
1050
999
850
678
231

231
1444
850
999
678
1222
1050
1325
1600
1900

1050
999
850
678
231
1222
1325
1444
1600
1900

231
850
999
1050
1222
1325
1444
1600
1900
678

[Trent]

Oh..I forgot..here are the results:
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 0

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 45

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 54

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 64

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 72

Press any key to continue . . .

[Robert Bauck Hamar]

Trent wrote:

Running this I see that on first run, both bubble and selection sort have
9 sort counts while insertion sort has ZERO. With a sorted list, should
this be ZERO for all?

I guess you by ZERO mean zero? Then please stop screaming. No. Your
algorithms only give zero for the insertion sort on a sorted list.

Also bsort and Ssort have the same exact sorting counts also..shouldn't
they differ somewhat?

for (int i = 0; i < size-1; ++i) {
count = count + 1;
}

should always provide the same answer for count as long as size remains the
same.

Note that how different sorting algorithms work is off topic on this group.

Source and data file below.

Thanks

Trent

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

using namespace std;
void bubbleSort(int *array, const int, int &); //function prototypes
void selectionSort(i nt *, const int, int &);
void insertionSort(i nt *, const int, int &);
void swap(int *, int *);

What's wrong with std::swap?

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;

Any particular reason for making these global?

>
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") ;

I have no pause program on my computer. When posting to this list, please
don't rely upon external programs.

return -1;

There are only three portable values to return from main:
0, EXIT_SUCCESS, or EXIT_FAILURE.

The two names are macros from <cstdlib>. Every other value has
implementation-defined results.

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

if (!(inFile >numArray[j])) { /*handle*/ }

Even if you did open the file, and you _know_ that it contains what you
want, reading it might fail.

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, const int size, int &count)
{
int i, pass;
for (pass =0; pass < size - 1; pass++) //# of passes
count= count+1;

a) why not ++count or count++?
b) count is always incremented size-1 times.

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

Usually, this would be
for (i = 0; i < size - (pass + 1); i++)
You should find out why.

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

This cannot possibly call your swap function. My theory is that if this
actually compiled, you are calling std::swap: A standard header is allowed
to include another, and since you said "using namespace std;" it might
actually _use_ any member of namespace std. You should generally
avoid "using namespace std;".

}

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

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

I repeat the remarks from bubble sort about swap and count.

}//end of selection sort function

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

This is undefined behaviour if array[0] < tmp. Make this:
while (i>=0 && array[i]>tmp)

{
count = count +1;

This time counting is done in the inner loop. What are you actually
counting?

array[i+1]=array[i];
i--;
}
array[i+1]=tmp;
}
}

--
rbh

[Trent]

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

Trent wrote:

>Running this I see that on first run, both bubble and selection sort have
9 sort counts while insertion sort has ZERO. With a sorted list, should
this be ZERO for all?

I guess you by ZERO mean zero? Then please stop screaming. No. Your
algorithms only give zero for the insertion sort on a sorted list.

>Also bsort and Ssort have the same exact sorting counts also..shouldn't
they differ somewhat?

for (int i = 0; i < size-1; ++i) {
count = count + 1;
}

should always provide the same answer for count as long as size remains
the
same.

Note that how different sorting algorithms work is off topic on this
group.

But, they are written in C++, and understanding how they work in C++,
therefore on topic

>

>Source and data file below.

Thanks

Trent

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

using namespace std;
void bubbleSort(int *array, const int, int &); //function prototypes
void selectionSort(i nt *, const int, int &);
void insertionSort(i nt *, const int, int &);
void swap(int *, int *);

What's wrong with std::swap?

Not in specifications

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

Any particular reason for making these global?

>>
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") ;

I have no pause program on my computer. When posting to this list, please
don't rely upon external programs.

You mean like iostream is an external program?
It's part of the C++ library <iomanip>

>

> return -1;

There are only three portable values to return from main:
0, EXIT_SUCCESS, or EXIT_FAILURE.

Okay I went ahead and inplmented that.

The two names are macros from <cstdlib>. Every other value has
implementation-defined results.

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

if (!(inFile >numArray[j])) { /*handle*/ }

Even if you did open the file, and you _know_ that it contains what you
want, reading it might fail.

Yes, but this is a learning excercise. I am not trying to make a commercial
package.
As I learn more I will be glad to add more stuff. :-)

> 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, const int size, int &count)
{
int i, pass;
for (pass =0; pass < size - 1; pass++) //# of passes
count= count+1;

a) why not ++count or count++?
b) count is always incremented size-1 times.

I can do it anyway..again this is a learning exercise, but I can implement
it.

>

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

Usually, this would be
for (i = 0; i < size - (pass + 1); i++)
You should find out why.

Actually I grabbed an example from the Deitel & Deitel "C++ How to Program"
Second Ed.
In reality all my sorts should be like this, but I am out of time to try and
figure the psuedo code out.

Bubble Sort:
Sorted = False

While not Sorted do

Sorted = True

For I = 1 to N-1 do

If A[i] A[I+1] then

Swap(A[i], A[I+1])

Sorted = False

Insertion Sort:

For I = 2 to N do

J = I

Done = False

While J >= 2 and not Done

If A[J-1] A[J] Then

Swap(A[J], A[J-1])

Else

Done = True

J=J-1



Selection Sort:

For I = 1 to N-1 do

Smallest = A[i]

Location = I

For J=I+1 to N do

If A[J] < Smallest then

Smallest = A[J]

Location = J

Swap(A[i], A[Location])

>

> if (array[i] array[i+1]) //one comparison
{
swap(array[i], array[i+1]);

This cannot possibly call your swap function. My theory is that if this
actually compiled, you are calling std::swap: A standard header is allowed
to include another, and since you said "using namespace std;" it might
actually _use_ any member of namespace std. You should generally
avoid "using namespace std;".

It does...The bubble sort and the swap came from the same example.
Actually I am calling the function swap that is at the end of the program,
correct?

>

> }

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

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

I repeat the remarks from bubble sort about swap and count.

Okay, but seems to be functioning to me.

>

>}//end of selection sort function

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

This is undefined behaviour if array[0] < tmp. Make this:
while (i>=0 && array[i]>tmp)

I did that and results are still the same.

> {
count = count +1;

This time counting is done in the inner loop. What are you actually
counting?

I am trying to count the actual amount of sorts it takes to sort the array.

> array[i+1]=array[i];
i--;
}
array[i+1]=tmp;
}
}

Thanks for the input

--
rbh

[Victor Bazarov]

Trent wrote:

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

>Note that how different sorting algorithms work is off topic on this
group.

But, they are written in C++, and understanding how they work in C++,
therefore on topic
[..]

My cookbook software is written in C++. Should I ask questions about
cooking here too? If you need to know how algorithms work, go ask in
comp.programmin g. If you have questions on the _language_ itself, or
how to turn an algorithm into C++ language constructs, ask here.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Trent]

"Victor Bazarov" <v.********@com Acast.netwrote in message
news:l-*************** *************** @comcast.com...

Trent wrote:

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

>>Note that how different sorting algorithms work is off topic on this
group.

But, they are written in C++, and understanding how they work in C++,
therefore on topic
[..]

My cookbook software is written in C++. Should I ask questions about
cooking here too? If you need to know how algorithms work, go ask in
comp.programmin g. If you have questions on the _language_ itself, or
how to turn an algorithm into C++ language constructs, ask here.

Oh, but I am not asking about cooking..I am asking about constructing
something in C++

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[BobR]

Trent <tr***@nunya.co mwrote in message...

Running this I see that on first run, both bubble and selection sort have

9

sort counts while insertion sort has ZERO. With a sorted list, should this
be ZERO for all?
Also bsort and Ssort have the same exact sorting counts also..shouldn't

they

differ somewhat?
Source and data file below.
Thanks
Trent

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

using namespace std;

void bubbleSort(int *array, const int, int &); file://function prototypes
void selectionSort(i nt *, const int, int &);
void insertionSort(i nt *, const 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;
Should be an unsigned type (try array[ -1 ], compile?):
std::size_t const 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
if (!inFile){
cerr << "Error Opening File" << endl;
system("pause") ;
return -1;
}
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];
} // for(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);\
} // for(i)
cout << endl;
system("pause") ;

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

/* // - style cop -

void bubbleSort(int *array, const int size, int &count){
int i, pass;
for (pass =0; pass < size - 1; pass++) file://# of passes
count= count+1;
for (i= 0; i < size - 1; i++) // one pass
if (array[i] array[i+1]){ file://one comparison
swap(array[i], array[i+1]);
}
}// end of bubble Sort function

*/ // - style cop -

void bubbleSort( int *array, const int size, int &count){
// for( int pass( 0 ); pass < size - 1; ++pass){ // # of passes
// ++count; // count = count+1;
// } // for(pass)
// // but, why not just?: count += size -1;

for( int i( 0 ); i < size - 1; ++i){ // one pass
if( array[ i ] array[ i+1 ] ){ file://one comparison
swap( array[ i ], array[ i+1 ] );
} // if()
// - or put it here: -
++count;
} // for(i)
} // end of bubble Sort function

>
void selectionSort(i nt *array, const int size, int &count){

int tmp( 0 );
for( int i( 0 ); i < size - 1; ++i ){

tmp = i;

++count; // count = count + 1;
for( int j( i+1 ); j < size; ++j )

if( array[ j ] < array[ tmp ] )
tmp = j;
swap( array[ i ], array[ tmp ] ); file://call swap funtion
} // for(i)
}//end of selection sort function

void insertionSort(i nt *array,const int size, int &count){

int tmp( 0 ), i( 0 );

for( int j=1; j < size; ++j ){
tmp = array[ j ];
i = j - 1;
while( array[ i ] tmp && i >= 0 ){
++count; // count = count +1;
array[i+1] = array[ i ];
i--;
} // while()
array[i+1] = tmp;
} // for(i)
} // insertionSort(i nt*,const int,int&)
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;
}

If this is not homework, use 'std::vector'.

{
std::vector<int numArray( arraySize ); // #include <vector>
std::vector<int bsort;
// etc.
// open 'infile'
for( std::size_t i( 0 ); i < 5; ++i){
for( std::size_t j( 0 ); j < numArray.size() ; ++j){
inFile >numArray[ j ];
} // for(j)
bsort = numArray; // std::vector has assignment
// etc.
// rest of stuff
} // for(i)
}

--
Bob R
POVrookie

[Trent]

"BobR" <re***********@ worldnet.att.ne twrote in message
news:mh******** ************@bg tnsc05-news.ops.worldn et.att.net...

>
Trent <tr***@nunya.co mwrote in message...

>Running this I see that on first run, both bubble and selection sort have

9

>sort counts while insertion sort has ZERO. With a sorted list, should
this
be ZERO for all?
Also bsort and Ssort have the same exact sorting counts also..shouldn't

they

>differ somewhat?
Source and data file below.
Thanks
Trent

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

using namespace std;

void bubbleSort(int *array, const int, int &); file://function prototypes
void selectionSort(i nt *, const int, int &);
void insertionSort(i nt *, const 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;
Should be an unsigned type (try array[ -1 ], compile?):
std::size_t const 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
if (!inFile){
cerr << "Error Opening File" << endl;
system("pause") ;
return -1;
}
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];
} // for(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);\
} // for(i)
cout << endl;
system("pause") ;

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

/* // - style cop -

>void bubbleSort(int *array, const int size, int &count){
int i, pass;
for (pass =0; pass < size - 1; pass++) file://# of passes
count= count+1;
for (i= 0; i < size - 1; i++) // one pass
if (array[i] array[i+1]){ file://one comparison
swap(array[i], array[i+1]);
}
}// end of bubble Sort function

*/ // - style cop -

void bubbleSort( int *array, const int size, int &count){
// for( int pass( 0 ); pass < size - 1; ++pass){ // # of passes
// ++count; // count = count+1;
// } // for(pass)
// // but, why not just?: count += size -1;

for( int i( 0 ); i < size - 1; ++i){ // one pass
if( array[ i ] array[ i+1 ] ){ file://one comparison
swap( array[ i ], array[ i+1 ] );
} // if()
// - or put it here: -
++count;
} // for(i)
} // end of bubble Sort function

>>
void selectionSort(i nt *array, const int size, int &count){

int tmp( 0 );
for( int i( 0 ); i < size - 1; ++i ){

> tmp = i;

++count; // count = count + 1;
for( int j( i+1 ); j < size; ++j )

> if( array[ j ] < array[ tmp ] )
tmp = j;
swap( array[ i ], array[ tmp ] ); file://call swap funtion
} // for(i)
}//end of selection sort function

void insertionSort(i nt *array,const int size, int &count){

int tmp( 0 ), i( 0 );

> for( int j=1; j < size; ++j ){
tmp = array[ j ];
i = j - 1;
while( array[ i ] tmp && i >= 0 ){
++count; // count = count +1;
array[i+1] = array[ i ];
i--;
} // while()
array[i+1] = tmp;
} // for(i)
} // insertionSort(i nt*,const int,int&)
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;
}

If this is not homework, use 'std::vector'.

It is.
Maybe I should include the pseudocode required.
Thanks for the reply Bob.

Bubble Sort:
Sorted = False

While not Sorted do

Sorted = True

For I = 1 to N-1 do

If A[i] A[I+1] then

Swap(A[i], A[I+1])

Sorted = False

Insertion Sort:

For I = 2 to N do

J = I

Done = False

While J >= 2 and not Done

If A[J-1] A[J] Then

Swap(A[J], A[J-1])

Else

Done = True

J=J-1



Selection Sort:

For I = 1 to N-1 do

Smallest = A[i]

Location = I

For J=I+1 to N do

If A[J] < Smallest then

Smallest = A[J]

Location = J

Swap(A[i], A[Location])

{
std::vector<int numArray( arraySize ); // #include <vector>
std::vector<int bsort;
// etc.
// open 'infile'
for( std::size_t i( 0 ); i < 5; ++i){
for( std::size_t j( 0 ); j < numArray.size() ; ++j){
inFile >numArray[ j ];
} // for(j)
bsort = numArray; // std::vector has assignment
// etc.
// rest of stuff
} // for(i)
}

--
Bob R
POVrookie

[John Harrison]

Trent wrote:

Running this I see that on first run, both bubble and selection sort have 9
sort counts while insertion sort has ZERO. With a sorted list, should this
be ZERO for all?

Also bsort and Ssort have the same exact sorting counts also..shouldn't they
differ somewhat?

Yes they should, but look at your code to see why they don't.

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

for (i= 0; i < size - 1; i++) // one pass
if (array[i] array[i+1]) //one comparison
{
swap(array[i], array[i+1]);
}

}// end of bubble Sort function
void selectionSort(i nt *array, const int size, int &count)
{
int i, j, tmp;
for (i = 0; i < size - 1; i++)
{
tmp = i;
count = count + 1;
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

Look at those loops, both loops go round size-1 times. In both loops
count gets incremented by one each time round the loop. So in both cases
it's not surprising that count==size - 1 at the end of the loop.

This is an example of how the computer does EXACTLY what you tell it to
do, not what you wanted to tell it to do.

You bubble sort routine is wrong. You should stop the loop when the sort
has finished. If at the end of a pass you have not swapped any elements
then the sort has finished and you should quit the loop. I'll leave you
to work out the details.

john

[John Harrison]

>void bubbleSort(int *array, const int size, int &count)

>{
int i, pass;
for (pass =0; pass < size - 1; pass++) //# of passes
count= count+1;

for (i= 0; i < size - 1; i++) // one pass
if (array[i] array[i+1]) //one comparison
{
swap(array[i], array[i+1]);
}

}// end of bubble Sort function

I see your bubble sort code still has the mistake with missing curly
brackets I pointed out in your last post, but your bubble sort routine
is now sorting correctly. Strange isn't it? You really should post the
code you are actaully compiling if you don't want to end up confusing
everyone.

john