This is my implementation of the Gale Shapley Algorithm written completely in Java. This was one of my semester projects in the Bern University of Applied Sciences (BFH). The algorithm has a couple of Key features that in my opinion make it a solid implementation.
- It runs in worst case O(n^2) and best case O(n)
- Memory consumption is low as it only uses an arrays of int
- Javadoc is written for all major methods.
- There are a couple of JUnit tests, which test the validity of the implementation
The main implementation is in the package "gale.light". The algorithm uses a differently structured array as input data compared to other implementations. To understand it, it is advised to read the javadoc.
In the documents folder is a written report, explaining some basics of the stable marriage problem and the gale shapley algorithm. There are also slides I used for my presentation of the implementation. Additionally, there is also Test Data provided that I used for testing the speed of the algorithm. Sadly the report is written in German.
Feel free to use this implementation in any way you want. There is no licensing applied to it and there won't be in the future. It is open source.