All things are lawful, but not all things are profitable.
Knute Snortum wrote:What is the error? On what line? Do you have a stack trace?
Stefan Evans wrote:I gave it a run. Error I get is a stack overflow. It gets stuck in an endless recursion because of bugs in the partition method.
Can you explain how your partition method is supposed to work?
One of the things wrong is the return value of your partition function. Should it really be return a[pivot] ?
Molayo Decker wrote:Hi
You are using a recursive Binary search .To sort your arrays in natural order. That is from the smallest to the largest, i suggest you use the Collections framework TreeSet array.
example Set<Integer> mySet = new TreeSet<Integer>();
This will sort your array from the smallest to the largest;
Instead of using a while loop why don't you change it to a for loop. This will make your code much simpler.
No, it won't. It will lose any duplicates. If your array look like thisMolayo Decker wrote:. . . TreeSet array.
example Set<Integer> mySet = new TreeSet<Integer>();
This will sort your array from the smallest to the largest . . .
Campbell Ritchie wrote:
I personally think you should sort the array or not sort the array. Don't try half‑sorting the array..
Molayo Decker wrote:This will sort your array from the smallest to the largest;
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
One way is to use the Map suggestion which Winston made.Riaz Ud Din wrote:Is there any way to find the smallest kth element without sorting?
Winston Gutkowski wrote:I suspect Riaz is looking for an O(n) solution.
There are three kinds of actuaries: those who can count, and those who can't.
There are three kinds of actuaries: those who can count, and those who can't.
Riaz Ud Din wrote:No No No ... O(n) solution is not necessary. I am looking for any better solution.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Don't expect Piet Souris to do the homework for you. At best what could happen in that way, that Piet Souris will know how to do your homework and likely he would get good mark, but how about you? You'll need to solve similar problems in your daily job, and probably Piet Souris won't be sitting next to you. What's then?Riaz Ud Din wrote:Hi again Piet Souris
finger cross, soon you get time to implement it successfully. I am cursing the moment i watched the algorithm video, i can't implement it successfully and now it's bugging me.
Liutauras Vilda wrote:
Don't expect Piet Souris to do the homework for you. At best what could happen in that way, that Piet Souris will know how to do your homework and likely he would get good mark, but how about you? You'll need to solve similar problems in your daily job, and probably Piet Souris won't be sitting next to you. What's then?Riaz Ud Din wrote:Hi again Piet Souris
finger cross, soon you get time to implement it successfully. I am cursing the moment i watched the algorithm video, i can't implement it successfully and now it's bugging me.
I'd think start yourself, and Piet Souris and everyone else will advice you in case you miss some important parts.
Winston Gutkowski wrote:
The nice thing about a heap solution is that heaps are relatively simple, and can be applied to any array (or portion of); and getting the "max" (or "min") value is an O(1) operation. Insertion is O(log (k)), but if k is small relative to n (the size of your array), then you shouldn't need to do it very often.
I'm also pretty sure that "heapifying" itself is an O(n) task, so the worst overall time case should be something like O(k) + O((n-k) log(k)) (which I think is still O(n log(k)) unfortunately).
You can also deal with the problem in stages:
1. Get your heap working.
2. Use it to solve the problem.
Plus (@Riaz), you get to implement a heap; which is a fun exercise anyway.
Winston
Riaz Ud Din wrote:I don't know much about heap but i will surely first study heap and then try to implement this algorithm.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Riaz Ud Din wrote:[I]n my spare time i try to learn Java. In fact, I suck at programming but i still like it and want to learn it, just for hobby. I welcome any suggestion/feedback...
split the array into 'left' and 'right', where each a[i] in left <=
a[0], and each a[i] in right > a[0].
If lieft.length >= k, then the element sought is in left, So
do a recursion with left.
If left.len < k, then the element in question is in right, and
we need to find the element k - left.len.
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
fred rosenberger wrote:
Make sure you learn that in programming, simpler is often the better choice. If you are doing this simply for fun, great. But in the "real world", I would much rather see someone write code that's easy to follow and understand than write something complicated and clever that shaves a few microseconds off the execution time.
There are three kinds of actuaries: those who can count, and those who can't.
Piet Souris wrote:OP is referring to a Youtube film. Has any of you watched that film?
Then, why o why are you telling OP to go for the easy way of sorting...
or for using heaps, or whatever.
At least try to explain what is wrong with OP's attempt to implement the algorithm.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Riaz Ud Din wrote:I want to find kth smallest element in unsorted array without fully sorting the array. I use Quicksort to partially sort the array and find the kth smallest element. But i get error. Here is the code
Winston Gutkowski wrote:
No, you're quite right there. However, many of us are familiar with the general problem.
There are three kinds of actuaries: those who can count, and those who can't.
sets answer to 0
loops through all the numbers from 0 up to x
adds i to answer
returns answer
May be you right. I don't know what should be the new pivot value? I thought a[pivot] is the new pivot value and i returned it.
What you suggest what should be the return value?
Stefan Evans wrote:Ok, I've written a wall of text here. But hopefully you can find some answers in here.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Stefan Evans wrote:It is THAT sort of explanation you need to be able to give for your partition method.
Until you understand what you want it to do, you won't be able to fix your code.
I think the return value should represent an index into the array, not the value of an entry in the array. a[pivot] is thus obviously wrong.
The correct answer might actually be "pivot" but where is the "pivot" value right now?
Ok, I've written a wall of text here. But hopefully you can find some answers in here.
>
There are three kinds of actuaries: those who can count, and those who can't.
Piet Souris wrote:Well, I have nothing to add to Stefans remarks, and I presume that
Riaz has enough information to repair his original listing. I conclude
with a List-version, like I wrote about. I also included a stream-Map
version for java 8, because I find that a difficult subject and so I
use every opportunity to practise it.
Don't get me started about those stupid light bulbs. |