Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Fot those with extra time.. sorting question

Reply
Thread Tools

Fot those with extra time.. sorting question

 
 
Trent
Guest
Posts: n/a
 
      06-29-2007
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[i] > array[i+1]) //one comparison
{
swap(array[i], 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[i], 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[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)<<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



 
Reply With Quote
 
 
 
 
Trent
Guest
Posts: n/a
 
      06-29-2007
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 . . .


 
Reply With Quote
 
 
 
 
Robert Bauck Hamar
Guest
Posts: n/a
 
      06-29-2007
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<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.

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(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[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(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[i], 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[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
 
Reply With Quote
 
Trent
Guest
Posts: n/a
 
      06-30-2007

"Robert Bauck Hamar" <(E-Mail Removed)> wrote in message
news:f643kf$87a$(E-Mail Removed)...
> 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<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?
>


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



 
Reply With Quote
 
Victor Bazarov
Guest
Posts: n/a
 
      06-30-2007
Trent wrote:
> "Robert Bauck Hamar" <(E-Mail Removed)> wrote in message
> news:f643kf$87a$(E-Mail Removed)...
>> 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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask


 
Reply With Quote
 
Trent
Guest
Posts: n/a
 
      06-30-2007

"Victor Bazarov" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> Trent wrote:
>> "Robert Bauck Hamar" <(E-Mail Removed)> wrote in message
>> news:f643kf$87a$(E-Mail Removed)...
>>> 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++




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




 
Reply With Quote
 
BobR
Guest
Posts: n/a
 
      06-30-2007

Trent <(E-Mail Removed)> 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


 
Reply With Quote
 
Trent
Guest
Posts: n/a
 
      06-30-2007

"BobR" <(E-Mail Removed)> wrote in message
news:mhihi.131599$(E-Mail Removed)...
>
> Trent <(E-Mail Removed)> 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'.
>


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



 
Reply With Quote
 
John Harrison
Guest
Posts: n/a
 
      06-30-2007
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(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[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
 
Reply With Quote
 
John Harrison
Guest
Posts: n/a
 
      06-30-2007
>> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Urgent help needed:Installable fot DCOracle2 for windows harshu010 Python 0 05-29-2008 04:10 AM
verilog testbench fot vhdl ams apurva VHDL 1 02-06-2007 05:22 PM
Anyone here signed up & sit fot the Vista Exam 71-620 in Nov 2006 Vincent Leung MCDST 7 11-13-2006 12:40 PM
Fot those of you Gea Digital Photography 7 09-23-2006 08:14 PM
Telephoto converter fot Canon S2 John H Digital Photography 3 01-15-2006 07:10 PM



Advertisments