|
|
| Строка 5: |
Строка 5: |
| |similar_concepts=Heap, Список, Сортировка | | |similar_concepts=Heap, Список, Сортировка |
| }} | | }} |
| === Сортировка пузырьком ===
| | Примеры алгоритма сортировки: |
| Алгоритм состоит из повторяющихся проходов по сортируемому [[список|списку]]. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по [[список|списку]]повторяются }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, управляющие сортировкой списка.
| |
| Описание
|
Как использовать различные алгоритмы сортировки
|
| Область знаний
|
Информатика
|
| Область использования (ISTE)
|
|
| Возрастная категория
|
12
|
| Поясняющее видео
|
|
| Близкие рецепту понятия
|
Heap, Список, Сортировка
|
| Среды и средства для приготовления рецепта:
|
|
Примеры алгоритма сортировки:
- Сортировка пузырьком
