Win a copy of Head First Go this week in the Go 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Paul Clapham
  • Jeanne Boyarsky
Sheriffs:
  • Devaka Cooray
  • Junilu Lacar
  • Tim Cooke
Saloon Keepers:
  • Tim Moores
  • Ron McLeod
  • Tim Holloway
  • Claude Moore
  • Stephan van Hulst
Bartenders:
  • Winston Gutkowski
  • Carey Brown
  • Frits Walraven

Discussion on quick sort  RSS feed

 
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dear ranchers,

I am writing a report on java quicksort and comparing it to mine. I have to come with explanations about which ameliorations makes java quicksort so performant against a home made version.

I tried to read the source code which is thousands rows long and could not find obvious ameliorations: I wrote about:
- insertion sort threeshold (47), the merge sort threeshold (286);
- that java had been using empirical tests to choose a pivot (explanations at row 296)
- that java uses pair insertion sort.

What else do you recommend I should be mentioning in my report? I don't really know what makes a difference in performance.
 
Saloon Keeper
Posts: 5289
143
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The classic book "Algorithms & Data Structures" by Wirth is available for free online (see https://coderanch.com/wiki/660152/Find-Links-Free-Stuff for a link) - it has a section on sorting that discusses all kinds of algorithms, including QuickSort. That should be of interest.
 
Greenhorn
Posts: 3
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Java internally uses dual pivot quicksort.
Apart from that, there are multiple different thresholds where either insertion sort, merge sort or the above variant of quicksort is used.
The best way to understand the special cases is to read the code and focus on comments.

The following paper will give more details on dual pivot quicksort
https://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf
 
Saloon Keeper
Posts: 9869
199
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Java only uses quicksort for primitive element types. For collections and arrays of reference types, Java uses a variant of mergesort.
 
Ranch Hand
Posts: 45
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Java uses TimSort for Objects: https://en.wikipedia.org/wiki/Timsort
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you everybody, that was a lot of threads to follow to make a better report
 
Marshal
Posts: 63496
207
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Michael Krimgen wrote:Java uses TimSort for Objects: . . .

I presume you know why? That is the same as the modified merge sort Stephan mentioned.
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:

Michael Krimgen wrote:Java uses TimSort for Objects: . . .

I presume you know why? That is the same as the modified merge sort Stephan mentioned.



No, I don't know anything except the the information from Wikipedia. Is there a special reason except it's more efficient?
 
Stephan van Hulst
Saloon Keeper
Posts: 9869
199
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The reason is that quicksort is unstable. If you have a few elements in the array that are considered equal, quicksort may rearrange them relative to each other. For primitive values this doesn't really matter, because values that are equal are also identical.

For instance, if you sort [3, 1, 3, 2] to [1, 2, 3, 3], it doesn't really matter if the threes in the last positions originally came from indices 0 and 2 respectively, or indices 2 and 0 respectively.

For objects it does matter. Even when two objects are equal to each other, they may have a separate identity. Consider the following code:


Because mergesort is a stable sorting algorithm it is guaranteed that after sorting the array, aliceOne must come before aliceTwo, and therefore changing the name of aliceOne will result in [Eve, Alice, Bob, Carol, Dave]. With quicksort you don't have this guarantee, so it's not used for arrays of objects.
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you!
Even though it was very clear, I don't get why you did not have this garantee for quicksort? If aliceOne is in the right position in the array, the name should be changed easily to Eve even with quicksort?
 
Stephan van Hulst
Saloon Keeper
Posts: 9869
199
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

D.J. Quavern wrote:If aliceOne is in the right position in the array


What's the right position of aliceOne in the array after sorting?
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:

D.J. Quavern wrote:If aliceOne is in the right position in the array


What's the right position of aliceOne in the array after sorting?



I would have said first but I suspect that I am supposed -since you are asking- to reply second since quicksort works with swaps?
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:
Because mergesort is a stable sorting algorithm it is guaranteed that after sorting the array, aliceOne must come before aliceTwo, and therefore changing the name of aliceOne will result in [Eve, Alice, Bob, Carol, Dave]. With quicksort you don't have this guarantee, so it's not used for arrays of objects.



You write that I don't have this guarantee, but it's still possible?
 
Campbell Ritchie
Marshal
Posts: 63496
207
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It might leave those two elements in their original positions and it might not. That behaviour may vary between implementations and it may vary if you have a different size array. I don't know a lot about quicksort, I am afraid.
 
Stephan van Hulst
Saloon Keeper
Posts: 9869
199
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For unstable sorting algorithms, like quicksort, the final position of elements that have an equal somewhere else in the array is undefined.

That's why when the exact ordering is important, you absolutely need to use a stable algorithm, like mergesort. It's possible to make a stable quicksort, but it either:
  • requires more memory, or
  • it won't be quick.
  •  
    D.J. Quavern
    Ranch Hand
    Posts: 81
    Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thank you a lot. I get it now!
     
    I can't beleive you just said that. Now I need to calm down with this tiny ad:
    Become a Java guru with IntelliJ IDEA
    https://www.jetbrains.com/idea/
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!