Сортировка пузырьком: различия между версиями
Материал из Поле цифровой дидактики
Patarakin (обсуждение | вклад) (Новая страница: «{{Scripting Tutorials |Description=Сортиро́вка простыми обменами, сортировка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Метод сортировки обменами лежит...») |
Patarakin (обсуждение | вклад) |
||
(не показано 6 промежуточных версий этого же участника) | |||
Строка 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 | ||
Строка 6: | Строка 7: | ||
|Environment=Scratch | |Environment=Scratch | ||
}} | }} | ||
== Сортировка пузырьком == | |||
Алгоритм состоит из повторяющихся проходов по сортируемому [[список|списку]]. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по [[список|списку]]повторяются | Алгоритм состоит из повторяющихся проходов по сортируемому [[список|списку]]. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по [[список|списку]] повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — [[список]] отсортирован. При каждом проходе [[алгоритм]]а по внутреннему [[цикл]]у, очередной наибольший элемент массива ставится на своё место в конце списка рядом с предыдущим «наибольшим элементом», а наименьший [[элемент]] перемещается на одну позицию к началу [[массив]]а («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название [[алгоритм]]а). | ||
=== [[Scratch]] === | |||
<scratchblocks> | <scratchblocks> | ||
when green flag clicked | when green flag clicked | ||
Строка 30: | Строка 32: | ||
=== Пояснение алгоритма сортировки пузырьком (YouTube) === | |||
{{#widget:YouTube|id=QdifzKfT9D4|start=0}} | {{#widget:YouTube|id=QdifzKfT9D4|start=0}} | ||
=== | === [[Snap!]] === | ||
[[Файл:SortingBubble ed.png|400px]] | |||
Результат: | |||
[[Файл:SortingBubble.png|400px]] | |||
---- | |||
* [[Сортировка вставками]] | |||
* [[Быстрая сортировка]] | |||
; Теория: | ; Теория: |
Текущая версия на 16:04, 16 декабря 2022
Описание | Сортиро́вка простыми обменами, сортировка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка.
|
---|---|
Область знаний | Информатика |
Область использования (ISTE) | |
Возрастная категория | 9
|
Поясняющее видео | |
Близкие рецепту понятия | Сортировка |
Среды и средства для приготовления рецепта: | Scratch |
Сортировка пузырьком
Алгоритм состоит из повторяющихся проходов по сортируемому списку. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по списку повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — список отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце списка рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название алгоритма).
Scratch
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
Пояснение алгоритма сортировки пузырьком (YouTube)
Snap!
Результат:
- Теория
- Сортировка. Алгоритм сортировки списка. Принципы сортировки пузырьком и вставкой.
- Практика
- Ситуации в среде Scratch, когда необходима сортировка списка. Перечислите визуальные блоки Scratch, управляющие сортировкой списка.