|
|
| Line 1: |
Line 1: |
| − | <pre>
| |
| − | 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
| |
| − | </pre>
| |
| − |
| |
| − | 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 groupped from j to n.
| |
| − |
| |
| − | --[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 17:36, 19 June 2020 (UTC)
| |
