non-dominated-sorting

This repository contains implementations of algorithms for non-dominated sorting and a benchmarking suite.

Algorithms

The following algorithms are currently implemented:

• Fast Non-Dominated Sorting
• Deductive Sort
• Corner Sort
• Dominance Tree
• ENS
• Best Order Sort
• Jensen-Fortin-Buzdalov divide-and-conquer method
• Sumit Mishra divide-and-conquer method
• ENS-NDT, aka Non-Dominated Tree by Gustavsson and Syberfeldt
• Filter Sort
• Set Intersection Sort

Acknowledgments

The following contributors would like to acknowledge the support of this research by the Russian Scientific Foundation, agreement 17-71-20178:

• Maxim Buzdalov
• Margarita Markina

See also

Links to other implementations of non-dominated sorting

• Official sources of Best Order Sort and Bounded Best Order Sort
• Various algorithms in Java by the author of Best Order Sort
• Implementation of the Jensen-Fortin-Buzdalov approach in C#
• Implementation of the Jensen-Fortin-Buzdalov approach in Python
• Implementation of the Deb's fast NDS in Rust
• A rather stale project in C++ that proposed Filter Sort
• Parallel implementation of Best Order Sort

Links to related projects about similar problems

• Data Structures for Non-Dominated Sets by Jonathan Fieldsend
• Divide-and-conquer non-dominated sets by Dias, Jesus, Paquete
• Skyline queries (aka finding the first non-dominated layer) in Python
• Generalized Offline Orthant Search
• Generalized Online Orthant Search