Win a copy of The Little Book of Impediments (e-book only) this week in the Agile and Other Processes forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Simple Sorting Algorithm

 
Peter Popp
Greenhorn
Posts: 4
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Rancher
Posts: 1089
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 51447
87
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Rancher
Posts: 1089
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 51447
87
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Rancher
Posts: 1089
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Rancher
Posts: 1530
33
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 10571
64
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Peter Popp
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 10571
64
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Rancher
Posts: 1530
33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Rancher
Posts: 1530
33
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Rancher
Posts: 1089
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:
4) And finally: read Chan Ag's first reply again. His question


Her... :-)

Greetings,
Chan.
 
Piet Souris
Rancher
Posts: 1530
33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Oooops... sexist, role confirming me..

Ma'am, I sincerely apologize!

Greetings,
Piet
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic