Сортировка: различия между версиями

Материал из Поле цифровой дидактики
 
Нет описания правки
 
(не показано 12 промежуточных версий 2 участников)
Строка 1: Строка 1:
{{Понятие
{{Понятие
|Description=Процесс упорядочивания элементов в списке
|Description=Процесс упорядочивания элементов в списке. Алгоритм для упорядочивания элементов в списке.
Алгоритм для упорядочивания элементов в списке.
|Field_of_knowledge=Информатика, Математика
|Field_of_knowledge=Информатика
|similar_concepts=Heap, Куча (структура данных), Алгоритм сортировки
|Environment=Scratch, Snap!, Python, Perl
|FieldActivity=Computational Thinker
|FieldActivity=Computational Thinker
|Возрастная категория=10
|Возрастная категория=10
|Environment=Scratch
}}
}}
=== Сортировка пузырьком ===
== Граф==
Алгоритм состоит из повторяющихся проходов по сортируемому [[список|списку]]. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по [[список|списку]]повторяются }N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — [[список]] отсортирован. При каждом проходе [[алгоритм]]а по внутреннему [[цикл]]у, очередной наибольший элемент массива ставится на своё место в конце списка рядом с предыдущим «наибольшим элементом», а наименьший [[элемент]] перемещается на одну позицию к началу [[массив]]а («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название [[алгоритм]]а).
* [[Deepseek|Deepseek]]
** {{#ask: [[Deepseek]] | ?Description }}


<scratchblocks>
<graphviz>
when green flag clicked
digraph Алгоритмы_сортировки {
set [pass v] to [0]
    rankdir=TB;
set [swaps v] to [0]
    bgcolor="#ffffff";
repeat until <<(pass) > [0]> and <(swaps) = [0]>>
   
  set [item v] to [0]
    // Категории алгоритмов
  change [pass v] by (1)
    subgraph cluster_simple {
  set [swaps v] to [0]
        label="Простые (O(n²))";
  repeat ((length of [data v]) - (1))
        style="rounded,filled";
     change [item v] by (1)
        fillcolor="#FFEBEE";
     if <(item ((item) + (1)) of [data v]) < (item (item) of [data v])> then
       
      set [value v] to (item ((item) + (1)) of [data v])
        Пузырьковая [shape=box, style="filled", fillcolor="#FFCDD2",
      replace item ((item) + (1)) of [data v] with (item (item) of [data v])
                    URL="Сортировка пузырьком",
      replace item (item) of [data v] with (value)
                    label=<<table border="0">
      change [swaps v] by (1)
                        <tr><td><b>Пузырьковая</b></td></tr>
    end
                        <tr><td>O(n²) | O(1) память</td></tr>
  end
                        <tr><td>Стабильная</td></tr>
end
                      </table>>];
</scratchblocks>
       
 
        Вставками [shape=box, style="filled", fillcolor="#EF9A9A",
 
                  URL="Сортировка вставками",
==== Пояснение алгоритма сортировки пузырьком (YouTube) ====
                  label=<<table border="0">
 
                        <tr><td><b>Вставками</b></td></tr>
{{#widget:YouTube|id=QdifzKfT9D4|start=0}}
                        <tr><td>O(n²) | O(1) память</td></tr>
 
                        <tr><td>Адаптивная</td></tr>
=== Сортировка вставками ===
                      </table>>];
 
       
<scratchblocks>
        Выбором [shape=box, style="filled", fillcolor="#E57373",
when green flag clicked
                URL="Сортировка выбором",
set [item v] to [2]
                label=<<table border="0">
repeat until <(length of [data v]) < (item)>
                        <tr><td><b>Выбором</b></td></tr>
  set [insert location v] to ((item) - (1))
                        <tr><td>O(n²) | O(1) память</td></tr>
  repeat until <<(item (insert location) of [data v]) < (item (item) of [data v])> or <(insert location) < [1]>>
                        <tr><td>Нестабильная</td></tr>
     change [insert location v] by (-1)
                      </table>>];
  end
    }
  insert (item (item) of [data v]) at ((insert location) + (1)) of [data v]
      
  delete ((item) + (1)) of [data v]
     subgraph cluster_efficient {
  change [item v] by (1)
        label="Эффективные (O(n log n))";
end
        style="rounded,filled";
</scratchblocks>
        fillcolor="#E8F5E8";
 
       
; Теория:
        Быстрая [shape=box, style="filled", fillcolor="#C8E6C9",
: Сортировка. Алгоритмы сортировки списка. Принципы сортировки пузырьком и вставкой.
                URL="Сортировка быстрая",
; Практика
                label=<<table border="0">
: Ситуации в среде Scratch, когда необходима сортировка списка. Перечислите визуальные блоки Scratch, управляющие сортировкой списка.
                        <tr><td><b>Быстрая (QuickSort)</b></td></tr>
                        <tr><td>O(n log n) среднее</td></tr>
                        <tr><td>O(n²) худшее</td></tr>
                      </table>>];
       
        Слиянием [shape=box, style="filled", fillcolor="#A5D6A7",
                URL="Сортировка слиянием",
                label=<<table border="0">
                        <tr><td><b>Слиянием (MergeSort)</b></td></tr>
                        <tr><td>O(n log n) гарантировано</td></tr>
                        <tr><td>O(n) памяти</td></tr>
                      </table>>];
       
        Пирамидальная [shape=box, style="filled", fillcolor="#81C784",
                      URL="Сортировка пирамидальная",
                      label=<<table border="0">
                        <tr><td><b>Пирамидальная (HeapSort)</b></td></tr>
                        <tr><td>O(n log n)</td></tr>
                        <tr><td>O(1) памяти</td></tr>
                      </table>>];
    }
   
    subgraph cluster_special {
        label="Специальные";
        style="rounded,filled";
        fillcolor="#E3F2FD";
       
        Подсчётом [shape=box, style="filled", fillcolor="#90CAF9",
                  URL="Сортировка подсчётом",
                  label=<<table border="0">
                        <tr><td><b>Подсчётом</b></td></tr>
                        <tr><td>O(n + k)</td></tr>
                        <tr><td>Только целые числа</td></tr>
                      </table>>];
       
        Поразрядная [shape=box, style="filled", fillcolor="#64B5F6",
                    URL="Сортировка поразрядная",
                    label=<<table border="0">
                        <tr><td><b>Поразрядная</b></td></tr>
                        <tr><td>O(nk)</td></tr>
                        <tr><td>Для строк/чисел</td></tr>
                      </table>>];
       
        TimSort [shape=box, style="filled", fillcolor="#42A5F5",
                URL="Сортировка TimSort",
                label=<<table border="0">
                        <tr><td><b>TimSort</b></td></tr>
                        <tr><td>Гибридная</td></tr>
                        <tr><td>Используется в Python/Java</td></tr>
                      </table>>];
    }
      
    // Применения
    Вставками -> TimSort [style="dashed", label="основа для", fontsize=8];
    Быстрая -> Пузырьковая [style="dashed", label="намного быстрее", fontsize=8];
    Слиянием -> Подсчётом [style="dashed", label="для стабильности", fontsize=8];
}
</graphviz>

Текущая версия от 11:19, 19 декабря 2025


Описание Процесс упорядочивания элементов в списке. Алгоритм для упорядочивания элементов в списке.
Область знаний Информатика, Математика
Авторы
Поясняющее видео
Близкие понятия Heap, Куча (структура данных), Алгоритм сортировки
Среды и средства для освоения понятия Scratch, Snap!, Python, Perl

Граф

  • Deepseek
    •  Description
      DeepseekDeepseek.ai — китайская языковая модель на базе архитектуры MoE (Mixture-of-Experts), предоставляющая возможности контекстного поиска в интернете, аналитики загруженных файлов и «глубокого мышления» через собственный движок Deep Think

Источник — http://digida.mgpu.ru/index.php?title=Сортировка&oldid=39109