I need to implement a method sort ( int []x) to sort the array x using a priority queue.

This method should return an array which is sorted!!

The solution to this problem is:

I already have the array int [] x. so what im going to do is search for the smallest item and then remove them by order from smallest to biggest!

My PROBLEM IS : i dont know know how to search my array int[]x to find the smallest item in the array, i know i have to compare each item with the one before it but i cant seem to write the code of it! help guys! Thanks a lot!!

There are three problems with your code so far, but perhaps I'm not seeing something...

1) you are not incrementing (moving) the index. So that loop, as written, is infinite.

edit: oops, scratch that... it exits after one iteration. I should have said "loops that don't increment the loop index, are generally infinite loops". But because of problem #2, your loop actually just exits after a single iteration. (or none, depending on the values being compared).

2) having solved that (you've thrown in an i++ somewhere) all you're doing in the loop is overwriting every array entry with whatever value is in 'smallest'. I think you mean to set smallest equal to the array value (or perhaps the value of the index, i)?

3) having solved that, it will exit, the moment the condition **first** becomes true. That doesn't mean though, it couldn't have been true again, if you kept going. You want to find the smallest number in the entire array, not just the first time you get a smaller number than the 'next' one. [ December 10, 2008: Message edited by: Mike Curwen ]

That is how Sun implemented it. I do not allow my students to use the Collection classes for this kind of problems until they have shown that they understand how to implement sorting and find algorithms.

Ove is correct; this is an exercise in writing your own "find the minimum" algorithm. I don't think this is a job for the Arrays class. If the title of this thread accurately reflects the task required, it's not a job for for sorting algorithms either.

What follows will require lots of work with a pencil and paper; you will have to go through it in your head and write down what the variables will be before you start, after the first stage, etc., etc. My interpretation depends on the title of the thread; if that is not precise, then you will have to alter what follows accordingly.

What you are looking for it the logic behind doing it. Suggest

Write out an array of numbers 9483 12 045654 2845 7980 -3948593 23 -389475 etc.

Work out which is the smallest

Write down how you work out the smallest. Hint you do need a "smallest" variable, but you will need to work out what its initial value ought to be.

Code that lot and get it working.

Work out how you record the index of the array (probably easiest done at the same time as working out the smallest).

Code that lot and get it working.

Put the smallest item into your queue

Work out what "remove the item" means. Does it mean to create an array one element smaller and copy the items into the new array?

Draw a diagram of what that means, then code it and get it working.

Repeat until your array is empty

Empty your queue in order into a new array.Eureka!

Notice you want to do this task in tiny bits. "How do you eat an elephant? One mouthful at a time."

I need to implement a method sort ( int []x) to sort the array x using a priority queue.

The requirement as stated by the OP was to use a priority queue to do the sort. Once you have a correctly implemented priority queue, the sorting process is as easy as continually taking the next item from the top of the queue until the queue is empty. So the next question is, do you (OP) know what a priority queue is? Do you know how to implement one?

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 44028

33

posted

0

Originally posted by Garrett Rowe: The requirement as stated by the OP was to use a priority queue . . .

That sounds a lot simpler than what I thought. Thank you.

Manuel Leiria
Ranch Hand

Joined: Jul 13, 2007
Posts: 171

posted

0

Originally posted by Campbell Ritchie:

That sounds a lot simpler than what I thought. Thank you.