• Post Reply Bookmark Topic Watch Topic
  • New Topic

Clarification for quicksort  RSS feed

 
Will Huang
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm working out of a Java book and I have a question on what it is asking me to do.

The question is:
Redo the QuickSort class so that it chooses the splitting point as follows: The splitting point is the middle (in size) of the first element, the last element, and the element at approximately the middle of the array. This will make a very uneven split less likely.

I have no idea how it wants me to define the splitting point. How can the split point be the first element, the last element and the middle element all at the same time?

here is the code in question:



Thanks
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
read the directions more carefully:

The splitting point is the middle (in size) of the first element, the last element, and the element at approximately the middle of the array.


it doesn't say the split point IS all three. What I think he's trying to say is take the average of the first and last (hence the 'middle of the first and last element'). since that will (more that likely) not be an actual element, choose one in the middle of the array (i.e. if you have 100 elements to sort, pick one around element 50) that would be close to that average.
 
Campbell Ritchie
Marshal
Posts: 56584
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And welcome to the Ranch
 
Will Huang
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
fred rosenberger wrote:read the directions more carefully:

The splitting point is the middle (in size) of the first element, the last element, and the element at approximately the middle of the array.


it doesn't say the split point IS all three. What I think he's trying to say is take the average of the first and last (hence the 'middle of the first and last element'). since that will (more that likely) not be an actual element, choose one in the middle of the array (i.e. if you have 100 elements to sort, pick one around element 50) that would be close to that average.


Thanks for the help, but which is it? The average of the first and last or the element in the middle of the array?
 
Paul Clapham
Sheriff
Posts: 22839
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're asking about the meaning of an English sentence. And a very poorly-written one at that. This isn't a Java question, it's a question which should be addressed to the person who wrote the sentence.

I think the "middle in size" part means the median of the three numbers, not the arithmetic mean as Fred guessed. But that runs into the same problem as what Fred went on to describe if two of the three numbers are the same. So just ask your teacher what it means.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!