Insertion Sort

[kathir]

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

 

[Eric Sosman]

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.

 

[Dann Corbit]

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

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]

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