Velocity Reviews > Insertion Sort

# Insertion Sort

kathir
Guest
Posts: n/a

 08-04-2010

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[i];
}

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[i];
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

Eric Sosman
Guest
Posts: n/a

 08-04-2010
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
http://www.velocityreviews.com/forums/(E-Mail Removed)lid

Dann Corbit
Guest
Posts: n/a

 08-04-2010
In article <a0432c76-6395-454f-8ff3-f110963b96a6
@q21g2000prm.googlegroups.com>, (E-Mail Removed) 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[i];
> }
>
> 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

jchl
Guest
Posts: n/a

 08-05-2010

"Eric Sosman" <(E-Mail Removed)> wrote in message
news:i3bi8q\$9jt\$(E-Mail Removed)-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.

Uno
Guest
Posts: n/a

 08-06-2010
Dann Corbit wrote:
> In article <a0432c76-6395-454f-8ff3-f110963b96a6
> @q21g2000prm.googlegroups.com>, (E-Mail Removed) 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[i];
>> }
>>
>> 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

 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 OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post N. C++ 3 09-22-2007 08:03 PM Java Newbie Java 2 02-09-2007 07:53 PM Jochus C++ 3 04-21-2005 10:06 PM Tim923 Java 11 04-13-2005 09:03 AM Navin ASP General 1 09-09-2003 07:16 AM

Advertisments