Granny's Programming Pearls
"inside of every large program is a small program struggling to get out"
JavaRanch.com/granny.jsp
The moose likes Java in General and the fly likes Sorting method Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Sorting method" Watch "Sorting method" New topic
Author

Sorting method

Santhosh Kumar
Ranch Hand

Joined: Nov 07, 2000
Posts: 242
Hi all, I have a requirement. I get a vector of a Employee objects and we need to sort them in order and return the sorted vector. What is the efficient way of doing that?
Thanks in advance,
Santhosh Kumar
Preethi Suryam
Ranch Hand

Joined: Nov 17, 2000
Posts: 92
Hi Santhosh!
u can use java.util.Arrya's
public static void sort(Object[] a) method
to sort the employee objects.
Hope u find this information helpful.
Good Luck!
Preethi.
mohit joshi
Ranch Hand

Joined: Sep 23, 2000
Posts: 243
Collections class in java.util has a sort(Vector, Comparator)
function (check from documentation) which provided easiest way of sorting vectors in a specified way.
Otherwise takeout the elements from vector and put them in a TreeSet object( with a required comparator).
Is there any other way?
Be careful that if you put elements in TreeSet and later modify these elements without replacing them in the TreeSet, they do not sort again automatically. The sorting is done only once, when you add element to the TreeSet.
Roseanne Zhang
Ranch Hand

Joined: Nov 14, 2000
Posts: 1953
For your specific situation: (if I understand it correctly)Vector or Array of large/huge number of employees. Most the time, it is an almost sorted stuff with a few anomalies. The most efficient way to do it is write you own bubble sort routine. O(n) can be reached easily.
You hear me correctly, bubble sort. The algorithm can be found from Sun's demo with JDK. You can test and prove my "theory" easily by using Sun'a applet. The first time you click Bubble sort first, then Quick sort. You will see quick sort is much faster than bubble sort. However, since it is already sorted, this time you click quick sort first, then bubble sort to see who wins.
Thanks!
Roseanne
mohit joshi
Ranch Hand

Joined: Sep 23, 2000
Posts: 243
I am no expert in sorting algo. but I remember reading a book - Numerical recipies in C second Edi. Published in 1993, which says that If you know bubble sort, never use it and if you dont know it, make it point never to learn it.
I cant justify their reason because they have not covered bubble sort in their book.So I have my reservations about bubble sort being a useful algo.
Roseanne Zhang
Ranch Hand

Joined: Nov 14, 2000
Posts: 1953
Average case big O
Bubble sort: O(n*n) : generally considered bad.
Merge sort, Heap sort, etc.: O(n*lg(n)): Generally considered good.
Quick sort: O(n*lg(n)): Generally considered good, or better since less constant factor than other O(n*lg(n)) algorithms
However, on almost sorted data (assumed the case above):
Bubble Sort: O(n): Excellent
Quick sort: O(n*n): very bad since plus the algo overhead
Merge sort, Heap sort, etc.: O(n*lg(n)): OK, but not as good as it should be.
Read a good data structure or algorithm book for the concepts.
Or, just play with Sun's applets here
YourJDKDir\demo\applets\SortDemo\example1.html
Thanks!
Roseanne
[This message has been edited by Roseanne Zhang (edited November 27, 2000).]
[This message has been edited by Roseanne Zhang (edited November 27, 2000).]
Roseanne Zhang
Ranch Hand

Joined: Nov 14, 2000
Posts: 1953
Just give an idea about big O, see this:
n=1,000,000
n*lg(n)=19,931,569
n*n=1,000,000,000,000
Roseanne Zhang
Ranch Hand

Joined: Nov 14, 2000
Posts: 1953
If you don't have almost sorted data, or if you're not sure about them, don't use Bubble Sort
mohit joshi
Ranch Hand

Joined: Sep 23, 2000
Posts: 243
I take your advice of reading a good book on sorting, as soon as I find time
Unfortunately I am a poor man and cannot buy too many books, can you suggest one
[This message has been edited by mohit joshi (edited November 27, 2000).]
Roseanne Zhang
Ranch Hand

Joined: Nov 14, 2000
Posts: 1953
I learned these probably from some old Pascal/C book and strengthed my concepts by teaching and coding practice. Really don't know what is good out there now.
I've an excellent algorithm book, but I don't think it fits your situation. But I put here anyway:
Introduction to Algorithms (MIT Electrical Engineering and Computer Science)
by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest

Sorry for not being much help.
Roseanne
 
Don't get me started about those stupid light bulbs.
 
subject: Sorting method