2.3 Implementing The Stable Matching Algorithm using Lists and Arrays

To asymptotically analyze the running time of an algorithm, we don't need to implement and run it, but we definitely have to think about how the data will be represented and manipulated in an implementation of the algorithm so we could bound the number of computational steps it takes. This section looks at how to implement the Gale-Shapley algorithm using lists and arrays. In the Stable Matching Problems that the algorithm solves, we need to think about how the rankings will be represented, as each man and each woman has a ranking of all members of the opposite gender. In addition, we will need to know which men and women are free, and who is matched with whom. Finally, we need to decide which data structures to use for all of the mentioned data. The goal of for the designer is to choose data structures that will make the algorithm efficient and easy to implement.