Gale–Shapley algorithm: Difference between revisions

Revision as of 19:32, 30 December 2023

Revision as of 19:43, 30 December 2023

Line 30:

===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 structures:{{r|kt}}

*A list[[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

*A two-dimensional array indexed by an employer and a number <math>i</math> from 1 to <math>n</math>, naming the applicant who is each employer's {{nowrap|<math>i</math>th}} preference

*A one-dimensional array indexed by applicants, specifying their current employer, initially a [[sentinel value]] such as 0 indicating they are unemployed