# Insertion Sort

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

1. ### kathirGuest

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

2. ### Eric SosmanGuest

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

3. ### Dann CorbitGuest

In article <a0432c76-6395-454f-8ff3-f110963b96a6
>
> 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
4. ### jchlGuest

"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
5. ### UnoGuest

ot Re: Insertion Sort

Dann Corbit wrote:
> In article <a0432c76-6395-454f-8ff3-f110963b96a6
>> 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

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