This week's book giveaway is in the Other Languages forum.
We're giving away four copies of Rust Web Development and have Bastian Gruber on-line!
See this thread for details.
Win a copy of Rust Web Development this week in the Other Languages forum!
  • 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:
  • Tim Cooke
  • Campbell Ritchie
  • Ron McLeod
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Junilu Lacar
  • Rob Spoor
  • Paul Clapham
Saloon Keepers:
  • Tim Holloway
  • Tim Moores
  • Jesse Silverman
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Piet Souris
  • Frits Walraven

Number of comparison in sorting

 
Ranch Hand
Posts: 1283
Netbeans IDE Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
In Java we do perform sorting using comparable or comparator interfaces and for similar objects it can be done by Collection.sort() method. I wanted to know, for say if we have 5 objects to sort, how many comparison will going to take place? is it !n or !n-1. also wanted to know, is there any default implementation of compareTo and compare methods? if so what algorithm is used by it and how to compression of objects take place?

Thanks
 
Rancher
Posts: 43027
76
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The fastest way to get answers to these is probably to look it up in the Java source code that comes with the JDK in a file called src.zip or src.jar.
 
Kaustubh G Sharma
Ranch Hand
Posts: 1283
Netbeans IDE Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I did that ulf but I am not able to understand what Collections.sort() functioning, One thing I don't understand is we pass collection object from Collections.sort() method to compareTo() method that we override and from there we compare this.value to collectionObject.value... means we comparing what from what??
 
author
Posts: 23912
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Kaustubh G Sharma wrote:In Java we do perform sorting using comparable or comparator interfaces and for similar objects it can be done by Collection.sort() method. I wanted to know, for say if we have 5 objects to sort, how many comparison will going to take place? is it !n or !n-1. also wanted to know, is there any default implementation of compareTo and compare methods? if so what algorithm is used by it and how to compression of objects take place?



This can't be answer exactly -- certainly not if the question is "is it N or N-1 comparisons?", meaning specific to an exact count. From the JavaDoc, the algorithm is a modified merge sort. And for those who studied what a merge sort is, it has an order of "N Log N", but ...

1. "N Log N" is only the complexity. It may be relative to the number of comparisons, and even then, it makes the assumption that N approaches infinity. So, you can get a relative scale, but not really an exact count.

2. With the merge sort, the "N Log N" is only a cap. It is actually data dependent. I believe merge sort needs less comparisons for a set of data that is more "sorted" than a completely random set of data.

3. The modified part of the merge sort will actually cause more comparisons, but depending on the result of the comparison, it may actually cause less comparisons. In other words, a more sorted set of data may trigger short cuts which may need less comparisons.

Henry
 
Kaustubh G Sharma
Ranch Hand
Posts: 1283
Netbeans IDE Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Wooooo... Henry to understand this, will take years for me..I am very bad in mathematics I wrote a demo code for sorting 5 custom class objects using comparable interface and also keeping track of no. comparisons and I've got compareTo() method finish to run in 5 times.. how it does that?
 
Rancher
Posts: 1043
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The number of the comparisions depends on both the algorithm and the input data. As an extreme, you can sort N objects using N-1 comparisions: obviously if they happen to be in the ideal sequence, comparing them in their order lets you check with N-1 comparisions that they are already sorted.

 
Ranch Hand
Posts: 239
12
Scala IntelliJ IDE Eclipse IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Just want to note that in Java 7, the merge sort algorithm previously used has been replaced with the "dual pivot quicksort" by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch for primitives and by TimSort for objects (since it is stable and quicksort is not). The information available for the dual pivot quicksort is exciting if you are interested in analysis of algorithms. Google it if you are interested.
 
Kaustubh G Sharma
Ranch Hand
Posts: 1283
Netbeans IDE Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Scott Shipp wrote:Just want to note that in Java 7, the merge sort algorithm previously used has been replaced with the "dual pivot quicksort" by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch for primitives and by TimSort for objects (since it is stable and quicksort is not). The information available for the dual pivot quicksort is exciting if you are interested in analysis of algorithms. Google it if you are interested.



Interesting information. Thanks Scott
 
You showed up just in time for the waffles! And this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic