File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Beginning Java and the fly likes Insertion Sort pseudocode Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Insertion Sort pseudocode" Watch "Insertion Sort pseudocode" New topic
Author

Insertion Sort pseudocode

Anna Greene
Greenhorn

Joined: Feb 25, 2013
Posts: 20
I can't spot where my java implementation of insertion sort differs from the pseudocode here:
Well, there is one difference in the parameters used by the insert method, which is inconsistent in the pseudocode.
I'm pretty sure it should be calling insert (a,n) instead of (a,i,n);



Here is my attempt at a java implementation, which doesn't actually seem to do anything.
I've kept variable names as in the pseudocode. Might technically be bad practice, but
I think it should make it easier to follow in this particular scenario.


Why am I so interested in this pseudocode when there are simpler java-ready examples of insertion sort on the internet? Simply because this is the code the professor uses, so I should be able to understand it.
Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14150
    
  18

Here's how you can discover what's wrong:

Add System.out.println(...); statements at strategic places in your code, to print the value of variables at a certain point. Then run the program and look at what is being printed. Try following in the code, line by line, what's happening, until you discover what is going wrong.

You could also run the program in a debugger and step through it line by line, so that you can inspect at each line what is happening and how the values of variables change. But using println(...); statements is an easy and quick way to debug code.


Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 7 API documentation
Scala Notes - My blog about Scala
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7796
    
  21

Anna Greene wrote:Why am I so interested in this pseudocode when there are simpler java-ready examples of insertion sort on the internet? Simply because this is the code the professor uses, so I should be able to understand it.

So I guess the first question should be: Do you understand it?

I have to admit, I find it a bit confusing. For one thing, it looks like a selection sort to me, not an insertion sort, because the latter doesn't normally have a 'select-min()' function - although the two algorithms are very closely related.

A couple of tips for you, to add to Jesper's great advice:
1. Have a look at the animations in the two links I provided; they may help you to visualise what's going on better.
2. Give your fields and indexes more meaningful names. 'm', 'n' and 'k' may be fine when you're looking at algebra; but they can get mighty confusing when you're trying to decipher code. A few possibilities for you - 'valueToInsert', 'at', 'current', 'sorted' - but you should work them out for yourself from your understanding of the algorithm. Good names can often help you track down errors more quickly, because the logic doesn't make sense in context with the name.

HIH

Winston

Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Anna Greene
Greenhorn

Joined: Feb 25, 2013
Posts: 20
Winston Gutkowski wrote:
Anna Greene wrote:Why am I so interested in this pseudocode when there are simpler java-ready examples of insertion sort on the internet? Simply because this is the code the professor uses, so I should be able to understand it.

So I guess the first question should be: Do you understand it?

I have to admit, I find it a bit confusing. For one thing, it looks like a selection sort to me, not an insertion sort, because the latter doesn't normally have a 'select-min()' function - although the two algorithms are very closely related.

A couple of tips for you, to add to Jesper's great advice:
1. Have a look at the animations in the two links I provided; they may help you to visualise what's going on better.
2. Give your fields and indexes more meaningful names. 'm', 'n' and 'k' may be fine when you're looking at algebra; but they can get mighty confusing when you're trying to decipher code. A few possibilities for you - 'valueToInsert', 'at', 'current', 'sorted' - but you should work them out for yourself from your understanding of the algorithm. Good names can often help you track down errors more quickly, because the logic doesn't make sense in context with the name.

HIH

Winston


His selection sort looks like this...

and I was actually able to write a version of this one that works (as far as I can tell).


I've just noticed the typos on the bottom part of the original post, but I'm not getting the option to edit it
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7796
    
  21

Anna Greene wrote:His selection sort looks like this...

And that makes sense.

Looking at your original post, it would appear that his algorithm does an initial placement of the smallest value in the array in the first position. Strictly speaking, this is not necessary (and possibly incorrect), because:
(a) The first element is trivially sorted.
(b) Insertion sort is supposed to sort elements as they are encountered.
but he may have a reason for this "extra" step.

The way I see insertion sort is, for 0-based indexes:I'm afraid my pseudo-code is hopeless, but see if it makes sense to you with his formula.

HIH

Winston
Anna Greene
Greenhorn

Joined: Feb 25, 2013
Posts: 20
Winston Gutkowski wrote:
Anna Greene wrote:His selection sort looks like this...

And that makes sense.

Looking at your original post, it would appear that his algorithm does an initial placement of the smallest value in the array in the first position. Strictly speaking, this is not necessary (and possibly incorrect), because:
(a) The first element is trivially sorted.
(b) Insertion sort is supposed to sort elements as they are encountered.
but he may have a reason for this "extra" step.

The way I see insertion sort is, for 0-based indexes:I'm afraid my pseudo-code is hopeless, but see if it makes sense to you with his formula.

HIH

Winston


This is what I've gotten from your pseudocode so far. It doesn't work, but the error is more than likely on my end.


I'll keep trying to change it around a bit.

Thanks
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7796
    
  21

Anna Greene wrote:This is what I've gotten from your pseudocode so far. It doesn't work, but the error is more than likely on my end.

I'm afraid it is.

Hint: What are you passing to your swap() method? Now think about what you're supposed to pass.

Also: Note that I said move, not swap. I think I'd be more inclined to call the method shiftRight() although, in this particular case, a method might actually be overkill - but don't get me wrong, it's good that you're thinking about methods.

Winston
Anna Greene
Greenhorn

Joined: Feb 25, 2013
Posts: 20
I arrived at this by comparing it with the second pseudocode example on wikipedia, which seems kind of close.
I had to comment out the if condition to get it to work though.



At least this is similar and seems to actually work. Am I on the right track?
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7796
    
  21

Just another, very trivial point.

You might make your swap() method a little quicker by avoiding the action in cases where it's not needed, viz:You may also be interested in an old "bit trick" called the XOR swap. I only link it as an example of the sort of things that used to amuse us in the BI (Before Internet) era; I certainly wouldn't advise coding a swap that way these days.

Winston
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7796
    
  21

Anna Greene wrote:At least this is similar and seems to actually work. Am I on the right track?

Yes, but I think i should be set to n initially if you're doing it that way.

Also, for your test array: include a value that is negative, or greater than the length of the array (or both). That will highlight your original error.

Winston
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7796
    
  21

Anna Greene wrote:At least this is similar and seems to actually work. Am I on the right track?

Another point: You might want to think about translating that code back to a functional spec of the type your prof gave you. My pseudo-code is entirely procedural, whereas his is more analytic. It might also help you work out what his original intent was.

For example: What do you think is the intent of that inner 'while' loop? And how do you think you might "methodise" it in Java?

Functional analysis and programming takes a lot of discipline, and I take my hat off to folks that can do it properly. Unfortunately, I'm not one of them.

HIH

Winston
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Insertion Sort pseudocode