[ is less than the pivote [ - we exchange it with the first the new array is - - - ?? [ is equal to the pivoti [ we do not need to move itwe just advance to the next unclassified elementi the array is - - ?? [ is greater than the pivote [ we exchange it with the last unclassified elementi the new array is - - ?? note how the number of unclassified elements reduces by one in each case red white blue range ( def dutch_flag_partition pivot_index )pivot apivot_index keep the following invariants during partitioning bottom group [smaller middle group asmaller equal unclassified group aequal larger top group alarger :smaller equal larger len(akeep iterating as long as there is an unclassified element while equal larger aequal is the incoming unclassified element if aequal pivot asmaller ]aequal aequal ]asmaller smaller equal smaller equal elif aequal =pivot equal + elseaequal pivot larger - aequal ]alarger alarger ]aequal each iteration decreases the size of unclassified by and the time spent within each iteration is ( )implying the time complexity is (nthe space complexity is clearly ( variantassuming that keys take one of three valuesreorder the array so that all objects with the same key appear together the order of the subarrays is not important for exampleboth figures (band (con page are valid answers for figure (aon page use ( additional space and (ntime variantgiven an array of objects with keys that takes one of four valuesreorder the array so that all objects that have the same key appear together use ( additional space and (ntime variantgiven an array of objects with boolean-valued keysreorder the array so that objects that have the key false appear first use ( additional space and (ntime variantgiven an array of objects with boolean-valued keysreorder the array so that objects that have the key false appear first the relative ordering of objects with key true should not change use ( additional space and (ntime