Fot those with extra time.. sorting question

T

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

using namespace std;


void bubbleSort(int *array, const int, int &); //function prototypes
void selectionSort(int *, const int, int &);
void insertionSort(int *, 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,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");
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(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, 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 > array[i+1]) //one comparison
{
swap(array, array[i+1]);
}

}// end of bubble Sort function


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

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

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

Robert Bauck Hamar

Trent said:
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<iomanip>

using namespace std;


void bubbleSort(int *array, const int, int &); //function prototypes
void selectionSort(int *, const int, int &);
void insertionSort(int *, 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,sSortCounter, 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("input.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.

}


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(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, 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 > array[i+1]) //one comparison
{
swap(array, 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(int *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, array[tmp]); //call swap funtion
}


I repeat the remarks from bubble sort about swap and count.
}//end of selection sort function

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


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

This time counting is done in the inner loop. What are you actually
counting?
array[i+1]=array;
i--;
}
array[i+1]=tmp;
}
}
 
T

Trent

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


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
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,sSortCounter, 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("input.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 said:
There are only three portable values to return from main:
0, EXIT_SUCCESS, or EXIT_FAILURE.
Okay I went ahead and inplmented that.
}


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(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, 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.
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 > A[I+1] then

Swap(A, 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

Location = I

For J=I+1 to N do

If A[J] < Smallest then

Smallest = A[J]

Location = J

Swap(A, A[Location])



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


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


I did that and results are still the same.
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--;
}
array[i+1]=tmp;
}
}




Thanks for the input

 
V

Victor Bazarov

Trent said:
Robert Bauck Hamar said:
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.programming. If you have questions on the _language_ itself, or
how to turn an algorithm into C++ language constructs, ask here.

V
 
T

Trent

Victor Bazarov said:
Trent said:
Robert Bauck Hamar said:
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.programming. 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++
 
B

BobR

Trent said:
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<iomanip>

using namespace std;

void bubbleSort(int *array, const int, int &); file://function prototypes
void selectionSort(int *, const int, int &);
void insertionSort(int *, 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,sSortCounter, 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("input.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(bsort, arraySize, bsortCounter);// call the sort functions
selectionSort(ssort, arraySize,sSortCounter);
insertionSort(isort, arraySize,iSortCounter);
print(numArray, arraySize, bsort, ssort, isort, bsortCounter,sSortCounter,
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 > array[i+1]){ file://one comparison
swap(array, 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(int *array, const int size, int &count){
int tmp( 0 );
for( int i( 0 ); i < size - 1; ++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(int *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(int*,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)
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;
}

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)
}
 
T

Trent

BobR said:
Trent said:
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<iomanip>

using namespace std;

void bubbleSort(int *array, const int, int &); file://function prototypes
void selectionSort(int *, const int, int &);
void insertionSort(int *, 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,sSortCounter, 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("input.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(bsort, arraySize, bsortCounter);// call the sort functions
selectionSort(ssort, arraySize,sSortCounter);
insertionSort(isort, arraySize,iSortCounter);
print(numArray, arraySize, bsort, ssort, isort, bsortCounter,sSortCounter,
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 > array[i+1]){ file://one comparison
swap(array, 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(int *array, const int size, int &count){
int tmp( 0 );
for( int i( 0 ); i < size - 1; ++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(int *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(int*,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)
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;
}

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 > A[I+1] then

Swap(A, 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

Location = I

For J=I+1 to N do

If A[J] < Smallest then

Smallest = A[J]

Location = J

Swap(A, 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)
}
 
J

John Harrison

Trent said:
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 > array[i+1]) //one comparison
{
swap(array, array[i+1]);
}

}// end of bubble Sort function


void selectionSort(int *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, 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
 
J

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 > array[i+1]) //one comparison
{
swap(array, 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
 
R

Robert Bauck Hamar

Trent said:
But, they are written in C++, and understanding how they work in C++,
therefore on topic.

Yes, but only if we are past the understanding of the algorithm itself.
You mean like iostream is an external program?

No, I mean like pause is an external program. Everything you call with
system is. On my computer system("pause") prints

sh: pause: command not found
It's part of the C++ library <iomanip>

And all this time I've been using said:
if (array > array[i+1]) //one comparison
{
swap(array, 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?
void insertionSort(int *array,const int size, int &count)
{
int tmp,i;
for(int j=1;j<size;j++)
{
tmp=array[j];
i=j-1;
while(array>tmp && i>=0)


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


I did that and results are still the same.


But now you know you are not accessing array[-1]. A good tip: Use
std::vector instead of arrays, and access the elements with the at member
function:

std::vector<int> array(size);
//fill vector.
array.at(3)
I am trying to count the actual amount of sorts it takes to sort the
array.

Try to explain to yourself what a "sort" is. But: How to count the actual
amount of "sorts" in a good manner, is not topical on this group.
 
R

Ron Natalie

Robert said:
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.

Even those values have implementation-defined results. The values
are just hits as to what implementation-defined behavior you want.
 

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

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top