Содержание
- 2. Сортировка объектов Сортировка - в информатике переупорядочение рассматриваемых объектов по некоторому признаку или системе признаков Например,
- 3. Алгоритм сортировки АЛГОРИТМ ДЛЯ УПОРЯДОЧЕНИЯ НЕКОТОРОГО МНОЖЕСТВА ЭЛЕМЕНТОВ Обычно под алгоритмом сортировки подразумевают алгоритм упорядочивания множества
- 4. Классификация алгоритмов сортировок
- 5. Классификация алгоритмов сортировок Устойчивая сортировка не меняет взаимного расположения равных элементов
- 6. Классификация алгоритмов сортировок Естественность поведения – эффективность метода при обработке уже отсортированных, или частично отсортированных данных
- 7. Временная сложность сортировки – основной параметр, характеризующий быстродействие алгоритма Классификация алгоритмов сортировок Временная сложность сортировки –
- 8. Алгоритмы внешней и внутренней сортировки КЛАССИФИКАЦИЯ АЛГОРИТМОВ СОРТИРОВКИ ПО СФЕРЕ ПРИМЕНЕНИЯ Алгоритмы внутренней сортировки оперируют сравнительно
- 9. КЛАССИФИКАЦИЯ АЛГОРИТМОВ СОРТИРОВКИ ПО СФЕРЕ ПРИМЕНЕНИЯ Классификация алгоритмов сортировок
- 10. Оценка алгоритмов сортировки
- 11. Этапы алгоритма сортировки
- 12. Внутренняя сортировка
- 13. Простая вставка Бинарная вставка Простой выбор Стандартный обмен Метод Шелла Метод Хоара Турнирная Пирамидальная Внутренняя сортировка
- 14. Внутренняя сортировка Методы внутренней сортировки
- 15. Оценка сложности сортировки Постановка задачи сортировки в общем виде предполагает, что существуют только два типа действий
- 16. Простые сортировки К простым внутренним сортировкам относят методы, сложность которых пропорциональна квадрату размерности входных данных Иными
- 17. Сортировка Алгоритмы: простые и понятные, но неэффективные для больших массивов метод пузырька метод выбора метод прямой
- 18. Последовательно просматривается массив и сравнивается каждая пара элементов между собой При этом "неправильное" расположение элементов устраняется
- 19. Отсортированная часть 13 6 2 10 8 Первый просмотр 6 13 8 13 13 2 10
- 20. 55 12 42 94 18 67 44 6 нет да да да да да да 55
- 21. Результаты работы алгоритма сортировки обменом
- 22. Сортировка обменом, метод пузырька Для осуществления сортировки нужно выполнить несколько шагов, несколько проходов по массиву На
- 23. Сортировка обменом, метод пузырька Следует обратить внимание на то, что за один проход в начальную часть
- 24. Сортировка обменом, метод пузырька На каждом шаге нужно организовать сравнение двух соседних элементов Так как сравнения
- 25. Метод пузырька, блок-схема Расположим массив сверху вниз, от нулевого элемента – к последнему Шаг сортировки состоит
- 26. Метод пузырька? Другая схема?
- 27. Суть сортировки: Выбирается элемент с наименьшим значением и делается его обмен с первым элементом массива Затем
- 28. На первом шаге ищется минимальный элемент во всем рассматриваемом массиве x[1] x[2] x[3] x[4] x[5] x[6]
- 29. x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8] 43 55 82 42 94 18 6 63
- 30. x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8] 43 55 82 42 94 18 6 63
- 31. x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8] 43 55 82 42 94 18 6 63
- 32. x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8] 43 55 82 42 94 18 6 63
- 33. 13 6 2 10 8 Min 2 Min 6 Min 8 13 Min 10 13 Отсортиро-ванная
- 34. Сортировка выбором / выделением Строим готовую последовательность, начиная с левого конца массива Алгоритм состоит из n-1
- 35. Сортировка прямыми вставками (прямым включением) Сортируемый массив разбивается на два участка: уже «готовый», упорядоченный и ещё
- 36. Сортировка прямыми вставками (прямым включением) Исходное положение: x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8] 43
- 37. Сортировка прямыми вставками (прямым включением) 3 шаг 55 12 42 94 18 67 44 6 12
- 38. Сортировка прямыми вставками (прямым включением) Суть сортировки: Упорядочиваются два элемента массива Вставка третьего элемента в соответствующее
- 39. Сортировка прямыми вставками (прямым включением) 13 6 2 10 8 13 6 8 2 13 6
- 40. Сортировка прямыми вставками На i-м шаге последовательность разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n-1]
- 41. Сортировка прямыми вставками (прямым включением)
- 42. Анализ элементарных алгоритмов сортировок Замечания к определению временной сложности мерой объема входных данных служит количество элементов
- 43. Анализ сортировки обменом Количество сравнений - (n2-n)/2 Общее количество операций – Т(n2) Временная сложность алгоритма BubbleSort
- 44. Анализ сортировки обменом Для реализации алгоритма дополнительная память не требуется Временная сложность данного алгоритма практически не
- 45. Анализ сортировки выбором Количество сравнений - (n2-n)/2 Общее количество операций – Т(n2) Временная сложность алгоритма SelectSort
- 46. Анализ сортировки выбором Для реализации алгоритма дополнительная память не требуется Временная сложность данного алгоритма практически не
- 47. Анализ сортировки вставками Для массива 1 2 3 4 5 6 7 8 потребуется n-1 сравнение
- 48. Анализ сортировки вставками Для реализации алгоритма дополнительная память не требуется почти отсортированный массив будет досортирован очень
- 49. Анализ элементарных алгоритмов сортировок
- 50. Сравнение методов простой сортировки N – количество элементов, M – количество пересылок, C – количество сравнений
- 51. Выбор метода сортировки При сортировке небольших массивов (менее 100 элементов) лучше использовать метод «Всплывающего пузырька» Если
- 52. Сортировка вставкой Не эффективный метод, так как включение элемента связано со сдвигом всех предшествующих элементов на
- 53. Сортировка обменом Очень медленен и малоэффективен. На практике, даже с улучшениями, работает, слишком медленно, поэтому почти
- 55. Скачать презентацию