• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Sorting method

 
Ranch Hand
Posts: 242
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Ranch Hand
Posts: 92
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 243
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 1953
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 243
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 1953
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 1953
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 1953
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 243
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 1953
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
reply
    Bookmark Topic Watch Topic
  • New Topic