Insertion Sort

Discussion in 'C Programming' started by kathir, Aug 4, 2010.

  1. kathir

    kathir Guest

    http://softwareandfinance.com/CPP_Insertion_Sort.html

    #include <iostream>
    #include <string>



    int InsertionSort()
    {
    int max;
    std::cout << "\nProgram for Ascending order of Numeric Values
    using INSERTION SORT";
    std::cout << "\n\nEnter the total number of elements: ";
    std::cin >> max;

    int *numarray = new int[max];

    for(int i = 0; i < max; i++)
    {
    std::cout << "\nEnter [" << i + 1 << "] element: ";
    std::cin >> numarray;
    }

    std::cout << "Before Sorting : ";
    for(int k = 0; k < max; k++)
    std::cout << numarray[k] << " ";
    std::cout << "\n";

    for(int i = 1; i < max; i++)
    {
    int j = i;
    while(j > 0)
    {
    if(numarray[j-1] > numarray[j])
    {
    int temp = numarray[j - 1];
    numarray[j - 1] = numarray[j];
    numarray[j] = temp;
    j--;
    }
    else
    break;
    }
    std::cout << "After iteration " << i << ": ";
    for(int k = 0; k < max; k++)
    std::cout << numarray[k] << " ";
    std::cout << "/*** " << i + 1 << " numbers from the begining
    of the array are input and they are sorted ***/\n";
    }

    std::cout << "\n\nThe numbers in ascending orders are given below:
    \n\n";
    for(int i = 0; i < max; i++)
    {
    std::cout << "Sorted [" << i + 1 << "] element: ";
    std::cout << numarray;
    std::cout << "\n";
    }

    delete [] numarray;
    return 0;
    }


    int main()
    {
    InsertionSort();

    return 0;

    }
    Output


    --------------------------------------------------------------------------------
    Program for Ascending order of Numeric Values using INSERTION SORT

    Enter the total number of elements: 8

    Enter [1] element: 80
    Enter [2] element: 60
    Enter [3] element: 40
    Enter [4] element: 20
    Enter [5] element: 10
    Enter [6] element: 30
    Enter [7] element: 50
    Enter [8] element: 70

    Before Sorting : 80 60 40 20 10 30 50 70
    After iteration 1: 60 80 40 20 10 30 50 70
    After iteration 2: 40 60 80 20 10 30 50 70
    After iteration 3: 20 40 60 80 10 30 50 70
    After iteration 4: 10 20 40 60 80 30 50 70
    After iteration 5: 10 20 30 40 60 80 50 70
    After iteration 6: 10 20 30 40 50 60 80 70
    After iteration 7: 10 20 30 40 50 60 70 80


    The numbers in ascending orders are given below:

    Sorted [1] element: 10
    Sorted [2] element: 20
    Sorted [3] element: 30
    Sorted [4] element: 40
    Sorted [5] element: 50
    Sorted [6] element: 60
    Sorted [7] element: 70
    Sorted [8] element: 80
    Press any key to continue . . .


    http://cpp.softwareandfinance.com
     
    kathir, Aug 4, 2010
    #1
    1. Advertising

  2. kathir

    Eric Sosman Guest

    On 8/4/2010 1:47 AM, kathir wrote:
    >
    > http://softwareandfinance.com/CPP_Insertion_Sort.html
    >
    > #include<iostream>
    > #include<string>
    > [...]


    Two things: First, you appear to be using the C++ language, not
    the C language, so any questions should go to comp.lang.c++ and not
    here. Second, you've posted a bunch of code and some sample output,
    but you haven't actually asked a question! If you re-post to
    comp.lang.c++, be sure to tell them what it is you're asking about.

    --
    Eric Sosman
    lid
     
    Eric Sosman, Aug 4, 2010
    #2
    1. Advertising

  3. kathir

    Dann Corbit Guest

    In article <a0432c76-6395-454f-8ff3-f110963b96a6
    @q21g2000prm.googlegroups.com>, says...
    >
    > http://softwareandfinance.com/CPP_Insertion_Sort.html
    >
    > #include <iostream>
    > #include <string>
    >
    >
    >
    > int InsertionSort()
    > {
    > int max;
    > std::cout << "\nProgram for Ascending order of Numeric Values
    > using INSERTION SORT";
    > std::cout << "\n\nEnter the total number of elements: ";
    > std::cin >> max;
    >
    > int *numarray = new int[max];
    >
    > for(int i = 0; i < max; i++)
    > {
    > std::cout << "\nEnter [" << i + 1 << "] element: ";
    > std::cin >> numarray;
    > }
    >
    > std::cout << "Before Sorting : ";
    > for(int k = 0; k < max; k++)
    > std::cout << numarray[k] << " ";
    > std::cout << "\n";
    >
    > for(int i = 1; i < max; i++)
    > {
    > int j = i;
    > while(j > 0)
    > {
    > if(numarray[j-1] > numarray[j])
    > {
    > int temp = numarray[j - 1];
    > numarray[j - 1] = numarray[j];
    > numarray[j] = temp;
    > j--;
    > }
    > else
    > break;
    > }
    > std::cout << "After iteration " << i << ": ";
    > for(int k = 0; k < max; k++)
    > std::cout << numarray[k] << " ";
    > std::cout << "/*** " << i + 1 << " numbers from the begining
    > of the array are input and they are sorted ***/\n";
    > }


    I guess that it is supposed to be some sort of demo or teaching example.
    Truly horrific. It's not generic, and the sort method prints to
    std::cout during the sort operation. It only sorts a list of integers.
    The sort routine itself collects sorting parameters from the user
    (clearly this belongs in main() or in a user input method). I simply
    can't imagine a worse insertion sort, besides one that simply fails to
    sort properly. It's a good teaching example of how NOT to code in C++.

    If you must write your own insertion sort in C++, do it something like
    this:
    http://www.dreamincode.net/code/snippet2129.htm
    but then do not post it on news:comp.lang.c where it is not topical.
    You can see in the cited example, a generic, readable method to order an
    arbitrary vector of objects.

    Since insertion sort is O(N*N), it is a horrible choice for more than 50
    items or so. Hence it is only useful as a clean-up routine for a larger
    sort procedure.

    Most sorting is performed on large lists of data using pointers. A
    generic pointer based example would be better than the one that I cited.
    Optimally, a sort routine would handle pointer and non pointer data with
    equal aplomb. If you want to write a useful sort in C++, study how it
    is done with the STL.

    IMO-YMMV
     
    Dann Corbit, Aug 4, 2010
    #3
  4. kathir

    jchl Guest

    "Eric Sosman" <> wrote in message
    news:i3bi8q$9jt$-september.org...
    > On 8/4/2010 1:47 AM, kathir wrote:
    >>
    >> http://softwareandfinance.com/CPP_Insertion_Sort.html
    >>
    >> #include<iostream>
    >> #include<string>
    >> [...]

    >
    > Two things: First, you appear to be using the C++ language, not
    > the C language, so any questions should go to comp.lang.c++ and not
    > here. Second, you've posted a bunch of code and some sample output,
    > but you haven't actually asked a question! If you re-post to
    > comp.lang.c++, be sure to tell them what it is you're asking about.
    >


    I suspect it's spam, trying to advertising his website disguising his post
    with code. The giveaway are the two links at the top and bottom of his post.
     
    jchl, Aug 5, 2010
    #4
  5. kathir

    Uno Guest

    ot Re: Insertion Sort

    Dann Corbit wrote:
    > In article <a0432c76-6395-454f-8ff3-f110963b96a6
    > @q21g2000prm.googlegroups.com>, says...
    >> http://softwareandfinance.com/CPP_Insertion_Sort.html
    >>
    >> #include <iostream>
    >> #include <string>
    >>
    >>
    >>
    >> int InsertionSort()
    >> {
    >> int max;
    >> std::cout << "\nProgram for Ascending order of Numeric Values
    >> using INSERTION SORT";
    >> std::cout << "\n\nEnter the total number of elements: ";
    >> std::cin >> max;
    >>
    >> int *numarray = new int[max];
    >>
    >> for(int i = 0; i < max; i++)
    >> {
    >> std::cout << "\nEnter [" << i + 1 << "] element: ";
    >> std::cin >> numarray;
    >> }
    >>
    >> std::cout << "Before Sorting : ";
    >> for(int k = 0; k < max; k++)
    >> std::cout << numarray[k] << " ";
    >> std::cout << "\n";
    >>
    >> for(int i = 1; i < max; i++)
    >> {
    >> int j = i;
    >> while(j > 0)
    >> {
    >> if(numarray[j-1] > numarray[j])
    >> {
    >> int temp = numarray[j - 1];
    >> numarray[j - 1] = numarray[j];
    >> numarray[j] = temp;
    >> j--;
    >> }
    >> else
    >> break;
    >> }
    >> std::cout << "After iteration " << i << ": ";
    >> for(int k = 0; k < max; k++)
    >> std::cout << numarray[k] << " ";
    >> std::cout << "/*** " << i + 1 << " numbers from the begining
    >> of the array are input and they are sorted ***/\n";
    >> }

    >
    > I guess that it is supposed to be some sort of demo or teaching example.
    > Truly horrific. It's not generic, and the sort method prints to
    > std::cout during the sort operation. It only sorts a list of integers.
    > The sort routine itself collects sorting parameters from the user
    > (clearly this belongs in main() or in a user input method). I simply
    > can't imagine a worse insertion sort, besides one that simply fails to
    > sort properly. It's a good teaching example of how NOT to code in C++.
    >
    > If you must write your own insertion sort in C++, do it something like
    > this:
    > http://www.dreamincode.net/code/snippet2129.htm
    > but then do not post it on news:comp.lang.c where it is not topical.
    > You can see in the cited example, a generic, readable method to order an
    > arbitrary vector of objects.
    >
    > Since insertion sort is O(N*N), it is a horrible choice for more than 50
    > items or so. Hence it is only useful as a clean-up routine for a larger
    > sort procedure.
    >
    > Most sorting is performed on large lists of data using pointers. A
    > generic pointer based example would be better than the one that I cited.
    > Optimally, a sort routine would handle pointer and non pointer data with
    > equal aplomb. If you want to write a useful sort in C++, study how it
    > is done with the STL.


    Yeah, Dann, I was inclined to think you were just being a purist until I
    read the source.

    One of the authors of one of the 2 definitive fortran texts uses the
    insertion sort, but it is a vastly different creature than this, in
    particular because it shows how to call it correctly from main, which OP
    omits here.

    If he is interested in how to call a sort routine using standard C, then
    he might profitably ask. What he has is incorrectly called a Program,
    unless main has gone out of fashion recently.

    I took a longer look at your allsort.h routine and noticed the
    #define PRELUDE, that you use to leave the door open for the people down
    the hall.

    What would be the usual thing you might define PRELUDE as?
    --
    Uno
     
    Uno, Aug 6, 2010
    #5
    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. Tim923

    insertion sort java code

    Tim923, Apr 12, 2005, in forum: Java
    Replies:
    11
    Views:
    12,179
    bugbear
    Apr 13, 2005
  2. N.
    Replies:
    3
    Views:
    8,799
    charles8784
    Sep 22, 2007
  3. Jochus
    Replies:
    3
    Views:
    532
    Jochus
    Apr 21, 2005
  4. Java Newbie

    Insertion Sort on a linked list

    Java Newbie, Feb 4, 2007, in forum: Java
    Replies:
    2
    Views:
    3,442
    Mark Space
    Feb 9, 2007
  5. Navin
    Replies:
    1
    Views:
    765
    Ken Schaefer
    Sep 9, 2003
Loading...

Share This Page