• Post Reply Bookmark Topic Watch Topic
  • New Topic

How does the Collections.Sort-method work?  RSS feed

 
Kenneth Van Gysegem
Ranch Hand
Posts: 43
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So I have a little program that sorts a list of books by bookname, and if the name of the book is the same, the books are sorted by ISBN-Number.
I overwrote the Compare-method to do this.



There's a bit more code, but all does what it has to do. My only question is about the Collections.sort-Method. How does it work? If I ctrl-click the method in netbeans I don't get any wiser.
so I give the sort method a list of books, and a new comparator object, does it iterate over all the books, or what does it?
It might be a silly question but if one of you guys could point me towards a source where I could find out more I would be very thankfull.
Cheers!
 
Campbell Ritchie
Marshal
Posts: 56536
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Does this[edit]←Look for List.sort link in that link on the left[/edit] help? Or this related method from Arrays? If you want to know more about the algorithms, try Wikipedia or these animations.
 
Kenneth Van Gysegem
Ranch Hand
Posts: 43
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Ritchie,
The thing is I understand what the comparator does, I also understand how I define the sorting, the thing I don't understand is the inner working of the sort-method.

What I see happening is Collections.sort-method getting 2 param. the first is the list to be sorted, the second is basically an object with a method that returns an int, right?
What does the sort method doe with de list and the generated Object that makes it possible to actually sort it, where does it call the compare-method from that Comparator-object.
I know if I would write the sort method myself I would get the first book and compare its name to all the other books, depending on what int the compareTo-method would give as return,
I would then set it before or after the book. Then I would do this with the second book etc.

Is this what this sort method does?
How can I see the code of what actually happens in the sort-method?

I know, a lot of questions, maybe a little unnecessary as I know how to use the comparator interface. I was just curious and thought I might be overseeing something simple.
Thanks!
 
Stephan van Hulst
Saloon Keeper
Posts: 7973
143
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is from List.sort(), which Collections.sort() delegates to in Java 8.

Java™ Platform, Standard Edition 8 API Specification wrote:
This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.
The implementation takes equal advantage of ascending and descending order in its input array, and can take advantage of ascending and descending order in different parts of the same input array. It is well-suited to merging two or more sorted arrays: simply concatenate the arrays and sort the resulting array.

The implementation was adapted from Tim Peters's list sort for Python ( TimSort). It uses techniques from Peter McIlroy's "Optimistic Sorting and Information Theoretic Complexity", in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993.


Basically you can view it as a merge-sort that performs insertion-sort when the amount of elements to sort is below some threshold, and has some other optimizations as well. I imagine it might use a ForkJoinAction to perform the recursive sorting in separate threads if the amount of elements to sort is large enough.
 
Kenneth Van Gysegem
Ranch Hand
Posts: 43
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hey Stephan,
Thank you very much, this was exactly what I was looking for!
I see now that, Ritchie was also referring to the same link.
Thanks for the explanation and the effort guys.
Greets
 
Campbell Ritchie
Marshal
Posts: 56536
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That's a pleasure
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!