Santhosh Kumar

Ranch Hand

Posts: 242

Preethi Suryam

Ranch Hand

Posts: 92

mohit joshi

Ranch Hand

Posts: 243

posted 16 years ago

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.

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

Posts: 1953

posted 16 years ago

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,

Thanks!

Roseanne

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

posted 16 years ago

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.

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

posted 16 years ago

Average case big O

Bubble sort: O(n*n) : generally considered

Merge sort, Heap sort, etc.: O(n*lg(n)): Generally considered

Quick sort: O(n*lg(n)): Generally considered

However, on almost sorted data (assumed the case above):

Bubble Sort: O(n):

Quick sort: O(n*n):

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

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)) algorithmsHowever, 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

Roseanne Zhang

Ranch Hand

Posts: 1953

mohit joshi

Ranch Hand

Posts: 243

Roseanne Zhang

Ranch Hand

Posts: 1953

posted 16 years ago

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

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

Consider Paul's rocket mass heater. |