Menu
I have written the following class:
public class SortingObjectsWithAngleField implements Comparator<Point> { public int compare(Point p1, Point p2) { double delta = p1.getAngle() - p2.getAngle(); if(delta == 0.00001) return 0; return (delta > 0.00001) ? 1 : -1; } } Then, in my main() method, I have created a List to which I add some objects which has "X" and "angle" field.
I then use:
Collections.sort(list, new SortingObjectsWithAngleField()); What is the complexity of this sort method?
744
sort(Object[]) is based on the TimSort algorithm, giving us a time complexity of O(n log(n)).
Collections sort is a method of Java Collections class used to sort a list, which implements the List interface. All the elements in the list must be mutually comparable. If a list consists of string elements, then it will be sorted in alphabetical order.
The time complexity of a loop is equal to the number of times the innermost statement is to be executed. On the first iteration of i=0, the inner loop executes 0 times. On the first iteration of i=1, the inner loop executes 1 times. On the first iteration of i=n-1, the inner loop executes n-1 times.
HashSet, LinkedHashSet and TreeSet the add, remove, and contains methods has constant time complexity o(1).
You could have read up the docs on Collections sort, but here it is for you:
The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance.
Your Comparator doesn't change this complexity, unless you do anything with loops over your collection in it, which you don't.
184
You should have found it in the API: n log(n).
27
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
