choose pivot from median of three elements for quicksort

[larskotthoff]

The method for choosing the pivot as implemented at the moment results in degenerate behaviour when the array is already sorted or reverse sorted. A better way is to choose the median of three elements (first, mid, last) as the pivot. See Robert Sedgewick. Implementing Quicksort Programs. Commun. ACM, 1(10):847–857, October 1978.

[larskotthoff]

Test failures seem to be unrelated? Not sure what's going on there.

[orist22]

I think it is critical to choose appropriate pivot. If you fix the conflict, it would be really helpful!

[orist22]

The code bot says that you exceeded the maximum size of array. I hope it would be helpful!

[codecov]

Codecov Report

Merging #171 into master will not change coverage.
The diff coverage is 100%.

@@          Coverage Diff          @@
##           master   #171   +/-   ##
=====================================
  Coverage     100%   100%           
=====================================
  Files         147    147           
  Lines        2590   2595    +5     
  Branches      432    434    +2     
=====================================
+ Hits         2590   2595    +5

Impacted Files	Coverage Δ
src/algorithms/sorting/quick-sort/QuickSort.js	100% <100%> (ø)	⬆️
src/algorithms/graph/kruskal/kruskal.js	100% <100%> (ø)	⬆️

---

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update d9946c1...478abba. Read the comment docs.

[codecov]

Codecov Report

Merging #171 into master will decrease coverage by 0.41%.
The diff coverage is 100%.

@@            Coverage Diff             @@
##           master     #171      +/-   ##
==========================================
- Coverage     100%   99.58%   -0.42%     
==========================================
  Files         147      128      -19     
  Lines        2590     2429     -161     
  Branches      432      413      -19     
==========================================
- Hits         2590     2419     -171     
- Misses          0        9       +9     
- Partials        0        1       +1

Impacted Files	Coverage Δ
src/algorithms/sorting/quick-sort/QuickSort.js	100% <100%> (ø)	⬆️
src/algorithms/graph/kruskal/kruskal.js	44.44% <0%> (-55.56%)	⬇️
...algorithms/sorting/selection-sort/SelectionSort.js	100% <0%> (ø)	⬆️
...hms/math/euclidean-algorithm/euclideanAlgorithm.js	100% <0%> (ø)	⬆️
src/data-structures/stack/Stack.js	100% <0%> (ø)	⬆️
src/utils/comparator/Comparator.js	100% <0%> (ø)	⬆️
src/algorithms/sorting/bubble-sort/BubbleSort.js	100% <0%> (ø)	⬆️
...rc/algorithms/search/binary-search/binarySearch.js	100% <0%> (ø)	⬆️
src/data-structures/trie/Trie.js	100% <0%> (ø)	⬆️
src/data-structures/heap/MinHeap.js	100% <0%> (ø)	⬆️
... and 32 more

---

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update d9946c1...f4668db. Read the comment docs.

[larskotthoff]

Should be fixed -- I wasn't choosing pivots the right way, and it turned out Kruskal's algorithm was broken...

[larskotthoff]

@trekhleb Could you have a look please? This makes quicksort better and fixes a bug in Kruskal's algorithm that breaks it in some cases.

[RayJune]

The method for choosing the pivot as implemented at the moment results in degenerate behaviour when the array is already sorted or reverse sorted. A better way is to choose the median of three elements (first, mid, last) as the pivot. See Robert Sedgewick. Implementing Quicksort Programs. Commun. ACM, 1(10):847–857, October 1978.

What a nice improvement. @larskotthoff Thanks a lot.

The fact that this PR is not merged in is a loss for the repository.

[lazarljubenovic]

The repo is mostly dead.