Fot those with extra time.. sorting question

Discussion in 'C++' started by Trent, Jun 29, 2007.

  1. Trent

    Trent Guest

    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
     
    Trent, Jun 29, 2007
    #1
    1. Advertising

  2. Trent

    Trent Guest

    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 . . .
     
    Trent, Jun 29, 2007
    #2
    1. Advertising

  3. 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 > 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;
    > }
    > }


    --
    rbh
     
    Robert Bauck Hamar, Jun 30, 2007
    #3
  4. Trent

    Trent Guest

    "Robert Bauck Hamar" <> wrote in message
    news:f643kf$87a$...
    > 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 > 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.

    >> {
    >> 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--;
    >> }
    >> array[i+1]=tmp;
    >> }
    >> }

    >



    Thanks for the input


    > --
    > rbh
     
    Trent, Jun 30, 2007
    #4
  5. Trent wrote:
    > "Robert Bauck Hamar" <> wrote in message
    > news:f643kf$87a$...
    >> 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
     
    Victor Bazarov, Jun 30, 2007
    #5
  6. Trent

    Trent Guest

    "Victor Bazarov" <> wrote in message
    news:...
    > Trent wrote:
    >> "Robert Bauck Hamar" <> wrote in message
    >> news:f643kf$87a$...
    >>> 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
    >
    >
     
    Trent, Jun 30, 2007
    #6
  7. Trent

    BobR Guest

    Trent <> 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 > 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 ){
    > 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
     
    BobR, Jun 30, 2007
    #7
  8. Trent

    Trent Guest

    "BobR" <> wrote in message
    news:mhihi.131599$...
    >
    > Trent <> 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 > 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 ){
    >> 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 > 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)
    > }
    >
    > --
    > Bob R
    > POVrookie
    >
    >
     
    Trent, Jun 30, 2007
    #8
  9. 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 > 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
     
    John Harrison, Jun 30, 2007
    #9
  10. >> 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
     
    John Harrison, Jun 30, 2007
    #10
  11. Trent wrote:

    >
    > "Robert Bauck Hamar" <> wrote in message
    > news:f643kf$87a$...
    >> Trent wrote:
    >>> 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.


    Yes, but only if we are past the understanding of the algorithm itself.

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


    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 <iostream>. :)

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


    My compiler didn't. My debugger says that swap<int>
    from /usr/include/c++/4.2.0/bits/stl_algobase.h is called.

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

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


    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.

    --
    rbh
     
    Robert Bauck Hamar, Jun 30, 2007
    #11
  12. Trent

    Ron Natalie Guest

    Robert Bauck Hamar wrote:

    > 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.
     
    Ron Natalie, Jul 1, 2007
    #12
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. BinnuChowdary
    Replies:
    1
    Views:
    542
    Swanand Mokashi
    May 1, 2006
  2. BinnuChowdary
    Replies:
    0
    Views:
    418
    BinnuChowdary
    May 2, 2006
  3. BinnuChowdary
    Replies:
    1
    Views:
    552
    =?UTF-8?B?R8O2cmFuIEFuZGVyc3Nvbg==?=
    May 2, 2006
  4. apurva
    Replies:
    1
    Views:
    801
    Ajeetha (www.noveldv.com)
    Feb 6, 2007
  5. harshu010
    Replies:
    0
    Views:
    287
    harshu010
    May 29, 2008
Loading...

Share This Page