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

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.

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.

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

posted

0

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

posted

0

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

posted

0

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

posted

0

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

posted

0

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).]