Insertion Sort

[hinduengg]

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

[dougy83]

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.:

unsorted list:     
   3 1 5 4 2
sorted list:     
1) (insert '3')  
   3 
   
2) (insert '1'; '3' is shuffled to the right) 
   1 3 
  
3) (insert '5') 
   1 3 5 
 
4) (insert '4'; '5' is shuffled to the right) 
   1 3 4 5
 
5) (insert '2'; '3', '4' & '5' are shuffled to the right) 
   1 2 3 4 5

[hinduengg]

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 :(

[Rashakil Fol]

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.

[hinduengg]

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. :)

[Killer_Typo]

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 :D

no better way to learn than with your very own hands :)

[hinduengg]

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.

[Killer_Typo]

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 :D

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

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

[Narue]

>I wanted to know what are actually random nos.
http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_rand.aspx
http://www.eternallyconfuzzled.com/arts/jsw_art_rand.aspx

And for your insertion sort question:
http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_sorting.aspx#insert

[hinduengg]

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

[~s.o.s~]

Every C program is a valid C++ program.(except for the deprecated header declarations). C++ is the functional superset of C. It seems that you need to read a few good C++ tutorials and books to get your concepts of 'structs' right.

[Narue]

>the site 's code is in c not in c++ and i long for C++
Fine, here's insertion sort from my website after converting it to C++:

void jsw_insertion ( int a[], int n )
{
  int i;

  for ( i = 1; i < n; i++ ) {
    int j, save = a[i];

    for ( j = i; j >= 1 && a[j - 1] > save; j-- )
      a[j] = a[j - 1];

    a[j] = save;
  }
}

>for it doesn't have ->signs
Yes, it does. The arrow operator is just a short form for accessing a structure (or class) member through a pointer. You're sorting arrays anyway, the second insertion sort example is for linked lists. Focus on the first example (which I've pasted above) for now.

[~s.o.s~]

Why pre-declare variables when C++ doesn't mandate it and anyways you are not using 'i' outside the loop?

[Narue]

>Why pre-declare variables when C++ doesn't mandate it
Why not? ;) Anyway, my point was that the code is perfectly valid and correct C++ without any changes.

[hinduengg]

Thanks a lot, lot. I really needed this help. Thank you.The example is superb. I really needed it.

I had just one small request that please could you please advice a good site that gives in depth analysis of C++ programming.
I will keep on trying , but I need guidance.
There are so many good sites for C but not for C++. Or perhaps I need to focus on C , derive the ideas and do programs in C++ according to C++ rules .
I really need to understand this . Its very important for my exam. I am in search of excellent C++ tutorials who could guide me through.
Please , please help.

[Narue]

>a site that gives in depth analysis of C++ programming.
You won't find one.

>I will keep on trying , but I need guidance.
What are we doing if not giving you guidance?

>I am in search of excellent C++ tutorials who could guide me through.
There aren't any tutorials for your exam. You don't seem to realize that C++ is a very large and complicated language. You can't just find a tutorial that teaches you everything. You need to take bits and pieces that you find and incorporate them into what you already know. Then practice. That's how you learn.

[hinduengg]

Ok I will try my best to do so and ask my problems. Wish me luck. Its not easy but i hope with your giudance I would be able to understand it better .
Thank you once again Narue .

[dougy83]

Thanks Killer Typo and Narue.
the site 's code is in c not in c++ and i long for C++ for it doesn't have ->signs

I think you'll find that C code compiles fine as C++ - i.e. C++ accepts all syntax of C.

The -> sign is found in both C & C++, and if you don't want to use it, you can use the equivalent shown below:

Instead of list->head you can use (*list).head . I personally prefer the former syntax.

-Doug

[hinduengg]

Thank you for your aid.

My course does not involve such high level things specially pointers. I dont know why they do not teach Pointers-so essential thing in C++ .
Although its not in course I still study them in detail to get why are syntaxes have their present form, what they mean such as array declarations.
I think they want us to be confused , but Narue gave me the most accurate solution.Thank you for making me understand.
This is my second year in C++ so uptill now, I can understand basically concepts through simple for, if loops. I am yet to start the high level programming or something that really is essential in C++.

Thank you to all.