4.23

from random import choices


def group_by_color(data, start, stop, color):
    operations_counter = 0

    while start < stop and start < len(data) and stop >= 0:
        # data[start] is equal to examine(data[start]) except swap function call

        while start < len(data) and data[start] == color:  # Finding first element with incorrect color from start
            start += 1  # Element with correct color already on right position, moving forward
            operations_counter += 1

        while start < stop and stop >= 0 and data[stop] != color:  # Finding first element with correct color from end
            stop -= 1  # Element with incorrect color will be swapped later or keep on that position, moving backward
            operations_counter += 1

        if start < stop:
            data[start], data[stop] = data[stop], data[start]  # Equal to swap(start, stop)
            operations_counter += 1

    assert operations_counter <= len(data) * 2  # Check O(2*n) restriction
    return start  # Return last element with specified color


colors_list = choices(['red', 'white', 'blue'], k=100)
red_ending = group_by_color(colors_list, 0, len(colors_list) - 1, 'red')  # Sort red O(n)
group_by_color(colors_list, red_ending + 1, len(colors_list) - 1, 'white')  # Sort white O(n)
# Blue already sorted

First pass: group red elements from 0 to k. Swapping not red elements found from begin and red elements found from end.

Second pass: group white elements from k to j. Swapping not white elements from k and white elements from end.

Blue elements already grouped from j to n.

-- Bkarpov96 ( talk ) 17:36, 19 June 2020 (UTC)

Back to Chapter 4