TADM2E 4.18 - Revision history

Bkarpov96: Undo revision 887 | Why are u doing this? What's the point? It's wiki for learning book

2020-07-23T08:14:33Z

Undo revision 887 | Why are u doing this? What's the point? It's wiki for learning book

Fucs: Undo revision 865 by Bkarpov96 (talk)

2020-07-22T22:54:45Z

Undo revision 865 by Bkarpov96 (talk)

Bkarpov96: Undo revision 860 by Bkarpov96Wars (talk)

2020-07-22T11:20:50Z

Undo revision 860 by Bkarpov96Wars (talk)

Bkarpov96Wars: Blanked the page

2020-07-22T00:23:00Z

Blanked the page

Bkarpov96: TADM2E 4.18 solution

2020-06-19T17:36:21Z

TADM2E 4.18 solution

New page

<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)

← Older revision		Revision as of 22:54, 22 July 2020
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)~~

← Older revision		Revision as of 00:23, 22 July 2020
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)~~

← Older revision	Revision as of 08:14, 23 July 2020
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)

← Older revision	Revision as of 11:20, 22 July 2020
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)