wood burning stoves 2.0*
The moose likes Beginning Java and the fly likes Simple Sorting Algorithm Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Simple Sorting Algorithm" Watch "Simple Sorting Algorithm" New topic
Author

Simple Sorting Algorithm

Peter Popp
Greenhorn

Joined: Oct 03, 2013
Posts: 4
I tried to program a simple sorting algorithm for integers, but for some reason it doesn't really work. Instead of putting the integers in the right order it just gives me my input back...
I already tried a few things and figured that something seems not to be working as intended in "check sort" as it always returns true. I just don't understand why it does that.

Here is my code:



Thank you in advance for your help.
Chan Ag
Bartender

Joined: Sep 06, 2012
Posts: 1000
    
  16
Hi and Welcome to the Ranch, Peter.

While I see a couple of problems in that code, I must congratulate you on using code tags in your first post.

Let's address the problems one by one. For now, what is nums[i] and nums[i++]?

How about you print them in the method, public boolean checkSort(int[] nums), just for checking?

Let us know if you found something.
Chan.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38045
    
  22
Welcome to the Ranch
Start by writing down very simply what your sorting algorithm is: simple words which anybody can read and follow. Don't write any code until you have done that.
You can Google for sorting algorithms; there are many of them, with varying efficiencies.
Chan Ag
Bartender

Joined: Sep 06, 2012
Posts: 1000
    
  16
Oh yes, what Campbell has suggested is the first thing I think you must do.

Translating your logic into a Java program should be the next step. And then may be we can talk about that i++ thingy.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38045
    
  22
Chan Ag wrote: . . . For now, what is nums[i] and nums[i++]? . . .
I think it best you start a new thread for that question, please.
Chan Ag
Bartender

Joined: Sep 06, 2012
Posts: 1000
    
  16
I don't have that question. I said that because the OP was doing this.


I thought I was helping. But I must have missed something there.
Peter Popp
Greenhorn

Joined: Oct 03, 2013
Posts: 4
Well, I do know that there are different kinds of sorting algorithms and that mine is not going to be the most effective, but I tried to do this just for practise.
What it is supposed to do is the following:

First ask the user for input:
How many numbers does s/he want to enter. Then it should create an array with the length of the given number.
As a next step it asks for the numbers and puts them in the array.
That part of my program is, as far as I can tell, working fine.

Now that we have our array the program is supposed to bring it in an order from large to small.

My idea was the following:
Step 1:
Check if the array is already in the right order. Yes -> goto Output; No -> Step 2
Step 2:
Check if the first number is larger then the second. Yes -> goto Step 4; No -> goto Step 3
Step 3:
Exchange first with second number
Step 4:
Same as step 2, just with the second and third number, until the last number in the array is reached.
Step 5: -> goto Step 1

Output:
Display the sorted array.

The problem is, as I said, probably in Step 1, as I changed my output so that it displays whether checkSort(int[] nums) returns true or false and no matter what I did, it always answered true.



This part is supposed to check if the i-th number in the given array is smaller than the number following the i-th number (starting with the first number in the array). Whenever this is the case my function should return false (so that my function sort(int[] nums) exchanges the numbers). If it is isn't it should check the next number until the last number is reached. If the i-th number was always larger or equal to the following number, and only then, it should return true.


Piet Souris
Ranch Hand

Joined: Mar 08, 2009
Posts: 459
    
    6
hi Peter,

your intention is clear. I have some remarks:

1) the name 'checkSort' is unfortunate. What does a return value of 'true' or 'false' mean? Is the array sorted or not?
A much better name would be 'isSorted'. Then a return value of 'true' or 'false' has a very clear meaning

2) Never, ever use 'i++' in expressions like you do here. It is asking for trouble. Always use 'i++' as a single statement.

3) From the look of your 'while' condition



you do the sorting when 'checkSort' returns 'false', indicating that 'checkSort' returns false when the
array is UNsorted.
If you then look at 'checkSort':

do you think the 'false' is correct here?

4) And finally: read Chan Ag's first reply again. His question about printing the variables in connection with the use
of this nasty 'i++' is spot on.

Greetings,
Piet
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7552
    
  18

Peter Popp wrote:My idea was the following:

Not bad as far as it goes, but clearly your code isn't doing it, is it?

The main problem, as Chan said earlier, is your use of 'i++'.

What does 'i++' do? Think about it. If need be, come back to us with your description and we'll tell you if you're right or not.

And then look hard at your loop, and work out what's actually happening. If need be, get out some paper and a pencil and write down, for every statement in that loop, what the value of i is.

That's how you debug.

Winston

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

Joined: Oct 03, 2013
Posts: 4
Thanks for your replies so far. I think my mistake was - as you said - a wrong understanding of the way in which i++ works...
I thought nums[i]<nums[i+1] would compare the i-th integer in the given array with the following number, but instead (as i++ is postincrement) it compares the i-th number with itself and then increments i by one...

Correct so far?

Thus I changed my code as follows:



Now it seems to work as intended (I also had to change nums.length-1 to nums.length-2 in my sort(int[] nums) function, as it would give me a outOfBounds-Exeption, obviously).

Do you see any other flaws in my code?
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7552
    
  18

Peter Popp wrote:I thought nums(i]<nums[i+1] would compare the i-th integer in the given array with the following number, but instead (as i++ is postincrement) it compares the i-th number with itself and then increments i by one...

But even that isn't the whole problem. The problem is that it increments i, so even if you'd used ++i it wouldn't have worked. ++i is NOT the same thing as i+1, even though it returns the same value.

However, you seem to have fixed that now.

Do you see any other flaws in my code?

I'll have a closer look and get back if I see anything.

Winston
Piet Souris
Ranch Hand

Joined: Mar 08, 2009
Posts: 459
    
    6
First of all, your latest code is very much better. Well done.

But indeed, there is still a major flaw, in your 'isSorted()' method.
This method should return 'true' when the array is sorted. Now look at the following line:

If nums[i] < nums[i+1] then this indicates that at least these two are sorted. So, should you return 'false' here?
(But, you do the actual sorting in the 'sort' method, so it shouldn't hurt, apart from the possibility of entering
an eternal loop.

So, inspect your 'isSorted()' method, by printing some variables, and see whether it works or not (especially:
are 'true' and 'false' in their correct places, combined with the use of '<'?)

Greetings,
Piet
Peter Popp
Greenhorn

Joined: Oct 03, 2013
Posts: 4
Piet Souris wrote:
But indeed, there is still a major flaw, in your 'isSorted()' method.
This method should return 'true' when the array is sorted. Now look at the following line:

If nums[i] < nums[i+1] then this indicates that at least these two are sorted. So, should you return 'false' here?
(But, you do the actual sorting in the 'sort' method, so it shouldn't hurt, apart from the possibility of entering
an eternal loop.


Sorry, but I don't really see your point. This method should return false whenever the int at any position in the array is smaller than the following one. If and only if every single int in the array is larger or equal to the following one it should return true, since then the array is completely sorted. In every other case it returns false.
Piet Souris
Ranch Hand

Joined: Mar 08, 2009
Posts: 459
    
    6
hi Peter,

yes, you're right. I just noticed the remark in line 06, that you are sorting from large to small, I had completely missed that.

So, indeed, then I don't see any flaws now. Sorry for the confusion.

A little effeciency remark: if you detect, in isSorted(), an i for which nums[i] < nums[i+1], then why not send this i
to the sort() method instead of a boolean?

Greetings,
Piet
Chan Ag
Bartender

Joined: Sep 06, 2012
Posts: 1000
    
  16
Piet Souris wrote:
4) And finally: read Chan Ag's first reply again. His question


Her... :-)

Greetings,
Chan.
Piet Souris
Ranch Hand

Joined: Mar 08, 2009
Posts: 459
    
    6
Oooops... sexist, role confirming me..

Ma'am, I sincerely apologize!

Greetings,
Piet
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Simple Sorting Algorithm
 
Similar Threads
How to combine two arrays within a loop?
Looping Input Help
Having trouble with my Sorting Program
Need to Print out put to Dialog box
Pass By Value