Re: Fot those with extra time.. sorting question
Trent <trent@nunya.com> wrote 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<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[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(int *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(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)
<< > 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;
}
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