Содержание
- 2. Задача сортировки (sorting problem)
- 3. Сортировка выбором. Selection Sort. На каждой итерации i, найти индекс (min ) минимального значения поменять местами
- 4. Сортировка выбором. Реализация. (см. Example5, Project SelectionSort) 1. перемещаемся по массиву вправо i++; 2. находим индекс
- 5. Сортировка выбором. Анализ. Сравнений: (N-1)+(N-2)+…1+0 ~ N2/2 Перестановок: N Сложность алгоритма: O(N2) Время работы алгоритма: не
- 6. Сортировка вставками. Insertion Sort. двигаемся по массиву элементов слева на право на каждой итерации i меняем
- 7. Сортировка вставками. Demo. i j i j i j i j i j i j i
- 8. Сортировка вставками. Реализация. 1. перемещаемся по массиву слева направо i++; 2. двигаемся справа-налево от i-го элемента
- 9. Сортировка вставками. Анализ. Сравнений: ~1/4 N2 в среднем Перестановок: ~1/4 N2 в среднем Сложность алгоритма: O(N2)
- 10. Сортировка простыми обменами. Bubble Sort. Алгоритм состоит из повторяющихся проходов по массиву За каждый проход элементы
- 11. Bubble sort. Demo. Swap (6,9) Don’t swap Swap (2,4) Swap (2,8) Конец 1-го прохода Конец 2-го
- 12. Bubble Sort. Реализация. 1. Выполняем i-ый проход, перестановок не было int i=0; bool swapped=false; 2. Сравниваем
- 14. Скачать презентацию