Two Laptop Bag*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes confused by collection sorted Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "confused by collection sorted" Watch "confused by collection sorted" New topic
Author

confused by collection sorted

Dodo Anakin
Greenhorn

Joined: Jul 19, 2007
Posts: 10
why people say

" The collection/array being searched must be sorted before you can search it "

waiting for explaination

thanks !
Chandra Bhatt
Ranch Hand

Joined: Feb 28, 2007
Posts: 1707
Hi,

It is binarySearch() method of the Collections factory class that you
use to find the object from the collection. Binary search method's
prerequisites is that your array or collection must be sorted.

To see how binary search method works, follow the link:

Binary Search Method


Thanks,


cmbhatt
Karen Marie
Greenhorn

Joined: Nov 10, 2007
Posts: 23
I know this is old but after reading the Binary Search Algorithm on wikipedia, I'm still unclear on the consequences of not sorting before performing a search as mentioned on page 557 in K&B.

Using the following:

Object[] obj = {"Hello", "Goodbye", "Adios", "Sionara", "Aloha"};
System.out.println(Arrays.binarySearch(obj, "Adios"));

The output is 2 as expected.

Based on what was said, I was expecting it not to be found or something? It does not discuss the consequences.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18507
    
  40

Based on what was said, I was expecting it not to be found or something? It does not discuss the consequences.


The consequences is that it *may* not be found. You have an example where it does work. Try seaching for something else.

Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Karen Marie
Greenhorn

Joined: Nov 10, 2007
Posts: 23
Ah. Hello, Goodbye, and Aloha all returned -4. I just got lucky (unlucky) picking Adios.

Thanks. It helps to have an example of what happens when you do things the *wrong* way as much as when you have it the *right* way.
Nicholas Jordan
Ranch Hand

Joined: Sep 17, 2006
Posts: 1282
[Karen Marie:]   Thanks. It helps to have an example of what happens when you do things the *wrong* way as much as when you have it the *right* way.

Well, yes - but just try to write a search for Bill Smith from Mule Shoe Arizona in a short dictionary that is not in alphabetical order.

Your example is short and demonstrates the matter effectively. When we discuss large datasets, such demonstrations are not always easy. Dodo Anakin should google for searching in Java to see the vast collection of work that is devoted to sorting, there are in fact searches that will work on unsorted datasets, be they collections or anything that can be searched. I doubt the internet will lean over to be sorted just because a bunch of computer scientists think it should be sorted, but it can be searched even though it is not sorted - so I would like to know who told Dodo that collections have to be sorted.


"The differential equations that describe dynamic interactions of power generators are similar to that of the gravitational interplay among celestial bodies, which is chaotic in nature."
marc weber
Sheriff

Joined: Aug 31, 2004
Posts: 11343

See this thread on binary searching.


"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." ~Joe Strummer
sscce.org
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18507
    
  40

I doubt the internet will lean over to be sorted just because a bunch of computer scientists think it should be sorted, but it can be searched even though it is not sorted - so I would like to know who told Dodo that collections have to be sorted.


Nicholas does make a good point here. This thread has made the assumption that Dodo is referring to the binary search methods of the Collections class. In fact, the original question (post) makes no such references.

Henry
[ November 25, 2007: Message edited by: Henry Wong ]
Karen Marie
Greenhorn

Joined: Nov 10, 2007
Posts: 23
--------------------------------------------------------------------
Nicholas does make a good point here. This thread has made the assumption that Dodo is referring to the binary search methods of the Collections class. In fact, the original question (post) makes no such references.
---------------------------------------------------------------------------


In the original post "The collection/array being searched must be sorted before you can search it " is an exact quote from a bullet point the K&B book pg 557 regarding the binarySearch() method in Arrays and Collections. Searching on that phrase is how I found the thread. I think Dodo had just left out a few details.
Nicholas Jordan
Ranch Hand

Joined: Sep 17, 2006
Posts: 1282
[Karen Marie:]   In the original post "The collection/array being searched must be sorted before you can search it " is an exact quote from a bullet point the K&B book pg 557 regarding the binarySearch() method in Arrays and Collections. Searching on that phrase is how I found the thread. I think Dodo had just left out a few details

Well, the original poster stated: waiting for explaination so these investigations can become teflon-on-ice without occasional feedback from needs of original poster, but what is this doing in certification ? This is a beginner or intermediate java question.

[Karen Marie:]   Based on what was said, I was expecting it not to be found or something? It does not discuss the consequences.

I thought about this all week and really, really wanted to do a stochastic scatter search, still may or may not find it and the thing could be tuned to demonstrate that the consequences of not sorting the data set may or may not hinge on prepatory work such as sorting and searches can be done in arbitrary beginner modes if one is willing to accept an 80% reliability of the search, but the real consequence of sorting is that a much faster determinisim of whether the item is in the dataset will be done.

This is discussed in nearly every sorting and searching paper aimed at this level of work. The link marc cites states "sorted in ascending order", but what that does not discuss is that for short-lived lists of a lengthy nature, it may be faster just to walk through the set using whatever search makes sense if you have detailed knowledge of what the application is trying to do and how the data is structured.

Without further requests from original poster, I suggest you re-post in General Computing, this is a General Computing issue of standard computer science: operating systems, applications, hardware, drivers, features, etc. General computer use stuff.
Burkhard Hassel
Ranch Hand

Joined: Aug 25, 2006
Posts: 1274
Howdy "Dodo Anakin" !

Please have a look into your private messages by clicking the "My Private Messages" link near the top of this page.

Yours,
Bu.
Karen Marie
Greenhorn

Joined: Nov 10, 2007
Posts: 23
what is this doing in certification ? This is a beginner or intermediate java question.


That quote Dodo mentioned was taken from the K&B book written specifically for the purpose of preparing novices for certification by two people who helped create the exam.

Without further requests from original poster, I suggest you re-post in General Computing, this is a General Computing issue of standard computer science: operating systems, applications, hardware, drivers, features, etc. General computer use stuff.


The original poster appears to be long gone but my question was answered. The quote was intended to make a novice like myself aware of what might happen if you search without sorting in simple cases. I also learned from you that the real world there are much more complicated cases which are not so black and white.

However, I have the answer that should prepare me for the questions on the exam which is enough for now. Thanks so much to everyone for their help.
Nicholas Jordan
Ranch Hand

Joined: Sep 17, 2006
Posts: 1282
I also learned from you that the real world there are much more complicated cases which are not so black and white.

It gets worse, my best suggestion I can give you is try to code a useable application for any real-world activity that interests you. It all scopes in place much better if you do that.

What is K&B, I always hear that term. It is a certification book, obviously, but we get people in the field who can pass scholastics but are totally useless in reality. The certification guides are a dramatic improvement, I just want to see what this one is.
Karen Marie
Greenhorn

Joined: Nov 10, 2007
Posts: 23
Sun Certified Programmer for Java 5 Study Guide by Kathy Sierra and Bert Bates. It is definitely for people trying learn Java without a ton of experience. They explain concepts very carefully, repeat, and give lots of examples. Excellent book.

The first thing is that, just like college, there is a big difference between those who know enough to score in the upper 90s and those who barely pass. Unfortunately I have heard a lot of people view the certificate itself as the end game and go for the barely passing grade. They memorize facts without spending a lot of time working with the code.

But the certification itself should just be motivation to learn the material really well and practice. I'm in QA so its perfect for me actually. I get a lot of practice in recognizing mistakes in crappy code.

In general its been a lot like learning a "real" language. I spend a ton of time on new words and new rules for grammer. But no matter how well you know the rules, you can't carry on real conversations unless you practice. I have written about 5500 lines of code so far just practicing concepts that are new to me.

Once a person can 'carry on simple conversations' in Java, so-to-speak, there is still a huge gap between that and being able to author a novel. I suppose the next step would be practicing algorithms or something.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: confused by collection sorted
 
Similar Threads
Difference between sorted and ordered?
difference between sorting and ordering
Tomcat 3.2.3 and VisualAge Java 4
help with loop
PriorityQueue