Сортировка пузырьком - История изменений

Patarakin в 13:04, 16 декабря 2022

2022-12-16T13:04:23Z

← Предыдущая версия		Версия от 16:04, 16 декабря 2022
Строка 1:		Строка 1:
	{{Scripting Tutorials		{{Scripting Tutorials
	\|Description=Сортиро́вка простыми обменами, сортировка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка.		\|Description=Сортиро́вка простыми обменами, сортировка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка.
			http://digida.mgpu.ru/images/thumb/d/d8/SortingBubble_ed.png/400px-SortingBubble_ed.png
	\|Field_of_knowledge=Информатика		\|Field_of_knowledge=Информатика
	\|Возрастная категория=9		\|Возрастная категория=9
Строка 45:		Строка 46:
	----		----
	* [[Сортировка вставками]]		* [[Сортировка вставками]]
			* [[Быстрая сортировка]]

	; Теория:		; Теория:

Patarakin: /* Snap! */

2022-12-16T13:02:36Z

Snap!

← Предыдущая версия		Версия от 16:02, 16 декабря 2022
Строка 37:		Строка 37:
	=== [[Snap!]] ===		=== [[Snap!]] ===

	[[Файл:SortingBubble ed.png\|~~600px~~]]		[[Файл:SortingBubble ed.png\|400px]]

	Результат:		Результат:

Patarakin: /* Snap! */

2022-12-16T13:02:19Z

Snap!

← Предыдущая версия		Версия от 16:02, 16 декабря 2022
Строка 41:		Строка 41:
	Результат:		Результат:

	[[Файл:SortingBubble.png]]		[[Файл:SortingBubble.png\|400px]]

	----		----

Patarakin: /* Snap! */

2022-12-15T19:50:05Z

Snap!

← Предыдущая версия		Версия от 22:50, 15 декабря 2022
Строка 39:		Строка 39:
	[[Файл:SortingBubble ed.png\|600px]]		[[Файл:SortingBubble ed.png\|600px]]

			Результат:

			[[Файл:SortingBubble.png]]

	----		----

Patarakin в 19:22, 15 декабря 2022

2022-12-15T19:22:08Z

← Предыдущая версия		Версия от 22:22, 15 декабря 2022
Строка 36:		Строка 36:

	=== [[Snap!]] ===		=== [[Snap!]] ===

			[[Файл:SortingBubble ed.png\|600px]]

Patarakin: /* Сортировка пузырьком */

2022-12-15T19:15:26Z

Сортировка пузырьком

← Предыдущая версия		Версия от 22:15, 15 декабря 2022
Строка 6:		Строка 6:
	\|Environment=Scratch		\|Environment=Scratch
	}}		}}
	=== Сортировка пузырьком ===		== Сортировка пузырьком ==
	Алгоритм состоит из повторяющихся проходов по сортируемому [[список\|списку]]. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по [[список\|списку]] повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — [[список]] отсортирован. При каждом проходе [[алгоритм]]а по внутреннему [[цикл]]у, очередной наибольший элемент массива ставится на своё место в конце списка рядом с предыдущим «наибольшим элементом», а наименьший [[элемент]] перемещается на одну позицию к началу [[массив]]а («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название [[алгоритм]]а).		Алгоритм состоит из повторяющихся проходов по сортируемому [[список\|списку]]. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по [[список\|списку]] повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — [[список]] отсортирован. При каждом проходе [[алгоритм]]а по внутреннему [[цикл]]у, очередной наибольший элемент массива ставится на своё место в конце списка рядом с предыдущим «наибольшим элементом», а наименьший [[элемент]] перемещается на одну позицию к началу [[массив]]а («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название [[алгоритм]]а).

			=== [[Scratch]] ===
	<scratchblocks>		<scratchblocks>
	when green flag clicked		when green flag clicked
Строка 30:		Строка 31:


	==== Пояснение алгоритма сортировки пузырьком (YouTube) ====		=== Пояснение алгоритма сортировки пузырьком (YouTube) ===

	{{#widget:YouTube\|id=QdifzKfT9D4\|start=0}}		{{#widget:YouTube\|id=QdifzKfT9D4\|start=0}}

			=== [[Snap!]] ===


			----
	* [[Сортировка вставками]]		* [[Сортировка вставками]]

Patarakin в 16:36, 15 декабря 2022

2022-12-15T16:36:03Z

← Предыдущая версия		Версия от 19:36, 15 декабря 2022
Строка 7:		Строка 7:
	}}		}}
	=== Сортировка пузырьком ===		=== Сортировка пузырьком ===
	Алгоритм состоит из повторяющихся проходов по сортируемому [[список\|списку]]. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по [[список\|списку]]повторяются }N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — [[список]] отсортирован. При каждом проходе [[алгоритм]]а по внутреннему [[цикл]]у, очередной наибольший элемент массива ставится на своё место в конце списка рядом с предыдущим «наибольшим элементом», а наименьший [[элемент]] перемещается на одну позицию к началу [[массив]]а («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название [[алгоритм]]а).		Алгоритм состоит из повторяющихся проходов по сортируемому [[список\|списку]]. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по [[список\|списку]] повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — [[список]] отсортирован. При каждом проходе [[алгоритм]]а по внутреннему [[цикл]]у, очередной наибольший элемент массива ставится на своё место в конце списка рядом с предыдущим «наибольшим элементом», а наименьший [[элемент]] перемещается на одну позицию к началу [[массив]]а («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название [[алгоритм]]а).

	<scratchblocks>		<scratchblocks>
Строка 34:		Строка 34:
	{{#widget:YouTube\|id=QdifzKfT9D4\|start=0}}		{{#widget:YouTube\|id=QdifzKfT9D4\|start=0}}

	~~===~~ Сортировка вставками ~~===~~		* [[Сортировка вставками]]

	~~<scratchblocks>~~
	~~when green flag clicked~~
	~~set [item v] to [2]~~
	~~repeat until <(length of [data v]) < (item)>~~
	~~set [insert location v] to ((item) - (1))~~
	~~repeat until <<(item (insert location) of [data v]) < (item (item) of [data v])> or <(insert location) < [1]>>~~
	~~change [insert location v] by (-1)~~
	~~end~~
	~~insert (item (item) of [data v]) at ((insert location) + (1)) of [data v]~~
	~~delete ((item) + (1)) of [data v~~]
	~~change [item v~~] ~~by (1)~~
	~~end~~
	~~</scratchblocks>~~

	; Теория:		; Теория:

Patarakin: Новая страница: «{{Scripting Tutorials |Description=Сортиро́вка простыми обменами, сортировка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Метод сортировки обменами лежит...»

2022-12-15T16:34:07Z

Новая страница: «{{Scripting Tutorials |Description=Сортиро́вка простыми обменами, сортировка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Метод сортировки обменами лежит...»

Новая страница

{{Scripting Tutorials
|Description=Сортиро́вка простыми обменами, сортировка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка.
|Field_of_knowledge=Информатика
|Возрастная категория=9
|similar_concepts=Сортировка
|Environment=Scratch
}}
=== Сортировка пузырьком ===
Алгоритм состоит из повторяющихся проходов по сортируемому [[список|списку]]. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по [[список|списку]]повторяются }N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — [[список]] отсортирован. При каждом проходе [[алгоритм]]а по внутреннему [[цикл]]у, очередной наибольший элемент массива ставится на своё место в конце списка рядом с предыдущим «наибольшим элементом», а наименьший [[элемент]] перемещается на одну позицию к началу [[массив]]а («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название [[алгоритм]]а).

<scratchblocks>
when green flag clicked
set [pass v] to [0]
set [swaps v] to [0]
repeat until <<(pass) > [0]> and <(swaps) = [0]>>
set [item v] to [0]
change [pass v] by (1)
set [swaps v] to [0]
repeat ((length of [data v]) - (1))
change [item v] by (1)
if <(item ((item) + (1)) of [data v]) < (item (item) of [data v])> then
set [value v] to (item ((item) + (1)) of [data v])
replace item ((item) + (1)) of [data v] with (item (item) of [data v])
replace item (item) of [data v] with (value)
change [swaps v] by (1)
end
end
end
</scratchblocks>

==== Пояснение алгоритма сортировки пузырьком (YouTube) ====

{{#widget:YouTube|id=QdifzKfT9D4|start=0}}

=== Сортировка вставками ===

<scratchblocks>
when green flag clicked
set [item v] to [2]
repeat until <(length of [data v]) < (item)>
set [insert location v] to ((item) - (1))
repeat until <<(item (insert location) of [data v]) < (item (item) of [data v])> or <(insert location) < [1]>>
change [insert location v] by (-1)
end
insert (item (item) of [data v]) at ((insert location) + (1)) of [data v]
delete ((item) + (1)) of [data v]
change [item v] by (1)
end
</scratchblocks>

; Теория:
: [[Сортировка]]. [[Алгоритм сортировки]] списка. Принципы сортировки пузырьком и вставкой.
; Практика
: Ситуации в среде Scratch, когда необходима сортировка списка. Перечислите визуальные блоки Scratch, управляющие сортировкой списка.