# Performs the quicksort algorithm. # Partition the sublist the_list[p ... r] so that the pivot # (originally in the_list[r]) moves to the_list[q], # all items in the_list[p ... q-1] are less than or equal to the pivot, # and all items in the_list[q+1 ... r] are greater than the pivot. # Return the index q where the pivot ends up. def partition(the_list, p, r, compare_func): pivot = the_list[r] # Set up the indices i and j so that # the_list[p ... i] contains items <= pivot, # the_list[i+1 ... j-1] contains items> pivot, and # the_list[j ... r-1] contains items not yet compared with the pivot. i = p - 1 j = p while j < r: if compare_func(the_list[j], pivot): # Move this item into the section known to be <= pivot. i += 1 (the_list[i], the_list[j]) = (the_list[j], the_list[i]) j += 1 # Get the pivot into the correct position. (the_list[i+1], the_list[r]) = (the_list[r], the_list[i+1]) return i+1 # Sort the sublist the_list[p ... r] using the quicksort algorithm. def quicksort(the_list, p, r, compare_func): if p < r: # nothing to do if the sublist has fewer than 2 items q = partition(the_list, p, r, compare_func) # divide quicksort(the_list, p, q-1, compare_func) # conquer smaller items quicksort(the_list, q+1, r, compare_func) # conquer larger items # Sort the_list by running quicksort on it. def sort(the_list, compare_func): quicksort(the_list, 0, len(the_list)-1, compare_func) # Return True if city1 has the same or higher population than city2. def compare_population(city1, city2): return city1.get_population()>= city2.get_population() # Return True if city1 comes at or before city2 alphabetically. def compare_name(city1, city2): return city1.get_name().lower() <= city2.get_name().lower() # Return True if city1's latitude is less than or equal to city2's latitude. def compare_latitude(city1, city2): return city1.get_latitude() <= city2.get_latitude()