Одномерные массивы Сортировка одномерных массивов. - презентация

1 Одномерные массивы Сортировка одномерных массивов

2 Цели занятия: изучить простые методы сортировки одномерных массивов; овладеть умениями и навыками осуществлять сортировку одномерных массивов; развивать структурного мышления, способностей к формализации, познавательных, интеллектуальных и творческих способностей; развивать понимание сущности и социальной значимости своей будущей профессии, проявление к ней устойчивый интерес; воспитывать информационную культуру, внимательность, дисциплинированность, эстетический вкус при составлении ментальных карт.

3 Понятие «Сортировка» Сортировка - это упорядочивание набора однотипных данных по возрастанию или убыванию. Ключ сортировки - это часть данных, определяющая порядок элементов.

4 С отсортированными данными работать легче, чем с произвольно расположенными: когда элементы отсортированы, их проще найти; на отсортированных данных легче определить, имеются ли пропущенные элементы; проще удостовериться, что все элементы были проверены; легче найти общие элементы двух множеств.

5 Методы сортировки сортировка обменом (пузырьковая); сортировка выбором; сортировка вставкой.

6

7 Й ПРОХОД Метод простого обмена

8 Й ПРОХОД Метод простого обмена

9 Й ПРОХОД Метод простого обмена

10 Й ПРОХОД Метод простого обмена

11 Й ПРОХОД Метод простого обмена

12 Й ПРОХОД Метод простого обмена

13 Й ПРОХОД Метод простого обмена

14 Й ПРОХОД Метод простого обмена

15 Й ПРОХОД Метод простого обмена

16 Й ПРОХОД Метод простого обмена

17 Й ПРОХОД Метод простого обмена

18 Й ПРОХОД Метод простого обмена

19 Й ПРОХОД Метод простого обмена

20 Й ПРОХОД 2-Й ПРОХОД Метод простого обмена

21 Й ПРОХОД 2-Й ПРОХОД Метод простого обмена

22 Й ПРОХОД 2-Й ПРОХОД Метод простого обмена

23 Й ПРОХОД 2-Й ПРОХОД Метод простого обмена

24 Й ПРОХОД 2-Й ПРОХОД Метод простого обмена

25 Й ПРОХОД 2-Й ПРОХОД Метод простого обмена

26 Й ПРОХОД 2-Й ПРОХОД Метод простого обмена

27 Й ПРОХОД 2-Й ПРОХОД Метод простого обмена

28 Й ПРОХОД 2-Й ПРОХОД Метод простого обмена

29 Й ПРОХОД 2-Й ПРОХОД Метод простого обмена

30 Й ПРОХОД 2-Й ПРОХОД Метод простого обмена

31 Й ПРОХОД 2-Й ПРОХОД Метод простого обмена

32 Й ПРОХОД 2-Й ПРОХОД Метод простого обмена

33 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД Метод простого обмена

34 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД Метод простого обмена

35 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД Метод простого обмена

36 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД Метод простого обмена

37 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД Метод простого обмена

38 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД Метод простого обмена

39 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД Метод простого обмена

40 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД Метод простого обмена

41 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД Метод простого обмена

42 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД Метод простого обмена

43 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД Метод простого обмена

44 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД Метод простого обмена

45 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД Метод простого обмена

46 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД Метод простого обмена

47 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД Метод простого обмена

48 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД Метод простого обмена

49 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД Метод простого обмена

50 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД Метод простого обмена

51 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД Метод простого обмена

52 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД 5-Й ПРОХОД Метод простого обмена

53 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД 5-Й ПРОХОД Метод простого обмена

54 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД 5-Й ПРОХОД Метод простого обмена

55 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД 5-Й ПРОХОД Метод простого обмена

56 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД 5-Й ПРОХОД Метод простого обмена

57 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД 5-Й ПРОХОД Метод простого обмена

58 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД 5-Й ПРОХОД 6-Й ПРОХОД Метод простого обмена

59 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД 5-Й ПРОХОД 6-Й ПРОХОД Метод простого обмена

60 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД 5-Й ПРОХОД 6-Й ПРОХОД Метод простого обмена

61 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД 5-Й ПРОХОД 6-Й ПРОХОД Метод простого обмена

62 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД 5-Й ПРОХОД 6-Й ПРОХОД Метод простого обмена

63 Й ПРОХОД 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД 5-Й ПРОХОД 6-Й ПРОХОД Метод простого обмена

64 Метод простого обмена (метод «пузырька») Сортировка методом «пузырька» - это алгоритм попарного сравнения элементов одномерного массива.

65 Исходный массив 2-Й ПРОХОД 3-Й ПРОХОД 4-Й ПРОХОД 5-Й ПРОХОД 6-Й ПРОХОД Й ПРОХОД Отсортированный массив

66 Вывод Время выполнения программы зависит от количества элементов. Чем больше элементов в массиве, тем больше времени необходимо на сортировку его элементов.

67 Метод простого выбора min

68 Метод простого выбора min

69 Метод простого выбора min

70 Метод простого выбора min

71 Метод простого выбора min

72 Метод простого выбора min

73 Метод простого выбора min

74 Метод простого выбора min

75 Метод простого выбора

76 Сортировка методом простого выбора - это алгоритм последовательного обмена минимального и первого элементов неотсортированной части массива.

77 Преимущества метода простого выбора Несмотря на то, что количество сравнений в пузырьковой сортировке и сортировки простым выбором одинаковое, в последней количество обменов в среднем случае намного меньше, чем в пузырьковой сортировке (так как перестановки осуществляются во внешнем цикле).

78 Метод простого включения Сортировка методом простого включения (сортировка вставкой) - это алгоритм последовательного помещения элемента массива в отсортированную части в соответствии с ключом сортировки.

79 Метод простого включения

80 Преимущества метода простого включения прост в реализации; эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим; эффективен на наборах данных, которые уже частично отсортированы; это устойчивый алгоритм сортировки (не меняет порядок элементов, который уже отсортирован); может сортировать массив по мере его получения; не требует временной памяти, даже под стек.

81 Решение задач «Теория без практики мертва, практика без теории слепа» Александр Суворов

82 Задача Массив целых чисел из 14 элементов заполнить случайным образом. Упорядочить массив по убыванию: 1 вариант – методом простого обмена 2 вариант – методом простого выбора 3 вариант - методом простого включения

83

84 Краткие итоги Задачи сортировки массивов имеют широкое прикладное значение. Существует большое количество алгоритмов сортировки массивов, различающихся трудоёмкостью. При оценке трудоёмкости алгоритмов учитываются критерии: количество сравнений и перестановок, время в лучшем и худшем случаях, естественность поведения. К алгоритмам простых сортировок относятся: сортировка методом "пузырька", сортировка методом простого выбора, сортировка методом простого включения. Простые сортировки эффективны на небольших объёмах данных.

85 Домашнее задание 1. Нарисовать ментальную карту "Массивы" в одной из предложенных программ. 2. Подготовиться к зачёту в соответствии со своим вариантом ( ) 1. Нарисовать ментальную карту "Массивы" в одной из предложенных программ. 2. Подготовиться к зачёту в соответствии со своим вариантом ( )