Gale–Shapley algorithm: Difference between revisions

Revision as of 19:43, 30 December 2023

Revision as of 19:43, 30 December 2023

Line 29:

===Implementation details and time analysis===

To implement the algorithm efficiently, each employer needs to be able to find its next applicant quickly, and each applicant needs to be able to compare employers quickly. One way to do this is to number each applicant and each employer from 1 to <math>n</math>, where <math>n</math> is the number of employers and applicants, and to store the following [[data structuresstructure]]s:{{r|kt}}

*A [[Set (abstract data type)|set]] of employers with unfilled positions

*A one-dimensional [[Array (data structure)|array]] indexed by employers, specifying the preference index of the next applicant to whom the employer would send an offer, initially 1 for each employer