The Greedy Algorithm in Motion

Animated GIF89 image of the greedy algorithm.

The largest available county is added to the smallest district in each iteration of the greedy algorithm. The process begins with the 12 most populous counties in the state, which form the nuclei of the 12 districts. Then in each subsequent step the program searches for the district with the smallest population and adds to it the largest unallocated county from among those adjacent to the district. Thus in the bar graph, at each stage the bar that grows ought to be the shortest bar. This rule is observed until toward the end of the run, when most of the districts are boxed in by others; finally only two districts have adjacent unallocated counties can can continue growing.