Сортировка: различия между версиями
Перейти к навигации
Перейти к поиску
Patarakin (обсуждение | вклад) (Новая страница: « Категория:Понятие») |
Patarakin (обсуждение | вклад) |
||
(не показано 12 промежуточных версий этого же участника) | |||
Строка 1: | Строка 1: | ||
+ | {{Понятие | ||
+ | |Description=Процесс упорядочивания элементов в списке | ||
+ | Алгоритм для упорядочивания элементов в списке. | ||
+ | |Field_of_knowledge=Информатика | ||
+ | |FieldActivity=Computational Thinker | ||
+ | |Возрастная категория=10 | ||
+ | |Examples=# Сортировка пузырьком — для каждой пары индексов производится обмен, если элементы расположены не по порядку. | ||
+ | # Сортировка вставками (англ. Insertion sort) определяем, где текущий элемент должен находиться в упорядоченном списке, и вставляем его туда. | ||
+ | }} | ||
+ | === Сортировка пузырьком === | ||
+ | Алгоритм состоит из повторяющихся проходов по сортируемому [[список|списку]]. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по [[список|списку]]повторяются }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) ==== | ||
+ | |||
+ | <pre> {{#widget:YouTube|id=QdifzKfT9D4|start=0}} </pre> | ||
+ | |||
+ | === Сортировка вставками === | ||
+ | |||
+ | <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, управляющие сортировкой списка. |
Текущая версия на 16:25, 10 апреля 2022
Описание | Процесс упорядочивания элементов в списке
Алгоритм для упорядочивания элементов в списке. |
---|---|
Область знаний | Информатика |
Область использования (ISTE) | Computational Thinker |
Возрастная категория | 10 |
Примеры реализации | «E# Сортировка пузырьком — для каждой пары индексов производится обменamples» содержит запрещённый символ «#» и, следовательно, отмечено, как недопустимое., «Eесли элементы расположены не по порядку.
|
Авторы | |
Поясняющее видео | |
Близкие понятия | |
Среды и средства для освоения понятия |
Сортировка пузырьком[править]
Алгоритм состоит из повторяющихся проходов по сортируемому списку. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по спискуповторяются }N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — список отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце списка рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название алгоритма).
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)[править]
{{#widget:YouTube|id=QdifzKfT9D4|start=0}}
Сортировка вставками[править]
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
- Теория
- Сортировка. Алгоритмы сортировки списка. Принципы сортировки пузырьком и вставкой.
- Практика
- Ситуации в среде Scratch, когда необходима сортировка списка. Перечислите визуальные блоки Scratch, управляющие сортировкой списка.