4

I am working on dual pivot quick sort I found here (page no-20 in slide)

Comparisons:

Yaroslavskiy needs = 1.9 n ln n on average.

Classic Quicksort needs = 2 n ln n comparisons!

Swaps:

Swaps for Yaroslavskiy’s algorithm = 0.6 n ln n

Swaps for classic Quicksort=0.3 n ln n

Results

Data type-----comp-------swap

int -------------591ns---------802ns

float-----------838ns----------873ns

double -------873ns----------1047ns

char ----------593ns-----------837ns

/* note :- above results in nanosecond and performed in java lang using intel core 2 duo */

if we combine the cost of swap and comparison than Classic Quicksort beats Yaroslavskiy Quicksort except in case of string where we use array of pointer to swap which require 88 nanosecond.Here Yaroslavskiy’s algorithm take advantage of 1.9 n ln n comparison because comparison is too much expensive compare to swap in case of string.

i want to know why java uses Yaroslavskiy Quicksort ? is main focus of inbuilt library sort are string what if it is not good on others data type?

Community
  • 1
  • 1
asd
  • 215
  • 3
  • 9
  • Where does java use this algorithm? Collections.sort uses modified mergesort as per javadoc – Zavior Feb 16 '14 at 14:02
  • google it i can provide u public domain code http://www.docjar.com/html/api/java/util/DualPivotQuicksort.java.html – asd Feb 16 '14 at 14:05
  • "The algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations." I would guess this is why. Other than that, you would have to ask the people who included it in the library. – Zavior Feb 16 '14 at 14:07
  • @Zavior `Collections.sort` might use mergesort, but [`Arrays.sort`](http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(byte[])) (those operating on arrays of primitive types) uses quicksort. It has to do with the stability of the sort - stable vs unstable sort on primitives containers makes no difference in the result, but it does on objects. – Bernhard Barker Feb 16 '14 at 14:09
  • @Zavior yes it is correct but only for worst case what about avg case?where single pivot is better than dual for other data type except string – asd Feb 16 '14 at 14:11
  • The answer to this question is given on slide 9 of the presentation you linked (whether or not the researcher's timings are more valid than yours is an open question). Also, note that the sort algorithms used for primitives and objects are different. See [GrepCode](http://grepcode.com/search/?query=java.util.Arrays) for comparison. – kdgregory Feb 16 '14 at 14:11
  • they didn't mention which data type if string then they are correct but what about others – asd Feb 16 '14 at 14:16
  • if they are true for others than why ?because my results are not matching with them for other data types except string – asd Feb 16 '14 at 14:18
  • For your time results, did you follow these steps - [How do I write a correct micro-benchmark in Java?](http://stackoverflow.com/q/504103), or did you get the results from some other source? – Bernhard Barker Feb 16 '14 at 16:00
  • Adding up the number of comparisons with the number of swaps and other operations to predict the performance of a computer program has, to my knowledge, never worked on any real computer. There are subtler effects going on---pipelining, caches, branch predictability, etc.---and at least one of them tends to dominate in most real programs before operation count matters. You have to write code on a computer and measure the code on the computer **carefully** to draw any conclusions about whether one algorithm is faster than another. – tmyklebu Feb 16 '14 at 16:23
  • Also, because of aforesaid subtler effects, you can't reasonably break the time down into "time spent doing comparisons" and "time spent doing swaps." Since you didn't provide code to reproduce your benchmark, we can't figure out what you did from what you say you thought you did. – tmyklebu Feb 16 '14 at 16:28
  • Collections.sort use timsort, see java.util.ComparableTimSort. MergeSort is not used anymore. – Oroboros102 Apr 01 '14 at 17:32
  • Sorry, I misinformed you. MergeSort is used on big arrays (bigger then 286). – Oroboros102 Apr 01 '14 at 17:38

2 Answers2

1

I don't know where you got your numbers from. According to this page:

It is proved that for the Dual-Pivot Quicksort the average number of comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n), whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n) respectively.

It looks like dual-pivot is always better.

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
ElKamina
  • 7,747
  • 28
  • 43
0

I tested dual java's pivot quicksort against many other quicksorts. It was 10~15% faster at minimum. Besides doublepivotness, it uses a lot of other optimisations:

  • 5-point pivot selection
  • insertion sort degration for small subarrays
  • data properties detection (instead of shuffling)
Oroboros102
  • 2,214
  • 1
  • 27
  • 41