Hi to all ,

I wished if any one of you could throw light on mechanism of insertion sorting in C++. I know what is bubble sorting but I had confusion regarding what is insertion sorting? In school my professor had mentioned about it, but I do not have any idea about it.
I got mixed up. I searched for it at the net but no clear ideas were given. It has been confusing for 7 days!!
I am unable to go about it.
I would appreciate if you could give an example of it ,so that i can understand it better.
Please help.

Thanks in advance.
Hinduengg

Hinduengg,

Insertion sorting is simply inserting each of the unsorted values into the list of sorted values in the location that keeps the list of sorted values correctly sorted. e.g. to sort in ascending order, insert each of the unsorted values into the sorted list after all values that are smaller than it, and before all values that are larger than it.

visual e.g.:

Help with Code Tags

C++ Syntax (Toggle Plain Text)

Thank you dougy83 . What is meant by function-insert ?I wished you could give the example in cplusplus syntax for I have to use it in C++.
If an array is inputted like this:

if the array is- [2][7][3][9][4]
then how will insertion sorting occur to sort it.

will it take out first 2
then read the entire array for finding next - 3
then again after entire process- 4
then next in the order would be-7
then -9
so that the ordered array comes to
[2][3][3][7][9]

Please explain, I can not get it

What you've just described is selection sort, where you select the minimum element from an array and append that onto an array that you're growing.

Insertion sort takes out the first element of the remaining elements and inserts it into the right place. To sort [2 7 3 9 4], you'd sort in the following fashion, where the list on the left is the sorted list that we're building, and the list on the right is the unsorted list we're taking elements from:

[] [2 7 3 9 4]
-- take the 2 and insert it 'in the right place'
[2] [7 3 9 4]
-- take the 7 and insert it 'in the right place'
[2 7] [3 9 4]
-- take the 3 and insert it 'in the right place'
[2 3 7] [9 4]
-- take the 9 and insert it...
[2 3 7 9] [4]
-- take the 4 and insert it...
[2 3 4 7 9] []
-- we're done!

And the sorted list becomes [2 3 4 7 9].

Now, I've been using the word 'list' instead of array, but that's only because I'm speaking abstractly. You can do an insertion sort on an array, in the fashion described above, in-place. Instead of changing the sizes of two 'lists' (whatever that means in the context of programming), you can simply walk an index through the array, from 0 to the size of the array. The part of the array before the index is sorted, and the part of the array after the index is the unsorted part.

For example, above, after you've taken the 3 and inserted it into the sorted portion, the array will look like [2 3 7 9 4], and the index will currently be 3, so the next element you take out will be 9.

Thank you so much for the SUPERB explanation .

Now I would try out a program that implements insertion sort and see to it whether I am successful .

Loads of thanks once again.

now it's time to write your own insertion method

no better way to learn than with your very own hands

I haven't yet started this assignment for I have to submit my E.V.S PROJECT within the next 2 days , so I am really busy in that.

On another note, I wanted to know what are actually random nos., because I have often seen all of you using it quite a many times.

what are random numbers?

just that random numbers

http://www.daniweb.com/forums/post394829-10.html

this is an array pointer example i wrote, but it deals with random numbers

>I wanted to know what are actually random nos.
http://www.eternallyconfuzzled.com/t..._tut_rand.aspx
http://www.eternallyconfuzzled.com/a..._art_rand.aspx

And for your insertion sort question:
http://www.eternallyconfuzzled.com/t...ng.aspx#insert

Thanks Killer Typo and Narue.


I understand about random nos. now.
But regards insertion sort , the site 's code is in c not in c++ and i long for C++ for it doesn't have ->signs , I believe, I understand pointers to some extent but not struct that well , I wondered whether you could simplify it with C++ syntax and using for loops. Is there any established site where I can get syntax only pertaining to C++ like the eternally confused.


Please help and advice,
hinduengg