Difference between revisions of "TADM2E 4.18"
From Algorithm Wiki
(Blanked the page) |
(Undo revision 887 | Why are u doing this? What's the point? It's wiki for learning book) |
||
| (2 intermediate revisions by 2 users not shown) | |||
| 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) | ||
Latest revision as of 08:14, 23 July 2020
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 groupped from j to n.
