Информатика. Тема 6. Численные методы решения задач.

4.26M

Category:

informatics

Численные методы решения задач

1. ИНФОРМАТИКА

Тема 6.
Численные методы решения задач.

2. Информатика. Тема 6. Численные методы решения задач.

6.1. Сортировка данных
Сортировка – один из основных алгоритмов обработки
информации, состоящий в переупорядочении по нужному
признаку заданной последовательности величин.
Дональд Кнут – американский ученый,
преподаватель и идеолог программирования

3. Информатика. Тема 6. Численные методы решения задач.

Постановка задачи:
1) Имеется N элементов R1, R2,…, RN, которые называются записями.
2) Каждая запись Rj, имеет ключ Kj.
3) На множестве ключей вводится отношение порядка < (меньше), что
для трех разных ключей a, b, c выполняются следующие условия:
• справедливо одно и только одно соотношение: a < b, a = b, a > b.
• если a < b и b < c, то a < c.
Задача сортировки – найти такую перестановку записей
p(1), p(2),…, p(N), после которой ключи расположились в
неубывающем порядке KP(1) ≤ KP(2) ≤ KP(N).
Сортировка называется устойчивой, если она удовлетворяет
дополнительному условию, что записи с одинаковыми ключами
остаются в прежнем порядке, т.е. p(i) < p(j), если KP(i) = KP(j) и i < j.

4. Информатика. Тема 6. Численные методы решения задач.

Сортировку разделяют на два класса: внутреннюю, когда все
записи хранятся в быстрой оперативной памяти, и внешнюю, когда
они там не помещаются.
Эффективность алгоритма сортировки можно оценить двумя
показателями: количеством сравнений и количеством обменов.
Алгоритмы сортировки данных можно разделить на четыре группы:
• сортировка подсчетом,
• сортировка вставками,
• сортировка посредством выбора,
• обменная сортировка.
K1
K2
K3
K4
K5
503 087 512 061 908
K6
K7
K8
170 897 275
K9
K10
K11
K12
653 426 154 509
K13
K14
K15
K16
612 677 765 703

5. Информатика. Тема 6. Численные методы решения задач.

6.1.1. Сортировка подсчетом
При сортировке подсчетом используется вспомогательный массив
C(1), C(2),…, C(N), элементы которого изначально равны нулю.
Все ключи попарно сравниваются.
Если ключ Ki больше Kj, то элемент C(i) увеличивается на единицу.
В противном случае на единицу увеличивается элемент C(j).
После завершения сравнений величина C(j) + 1 определяет
окончательное положение записи Rj.

6. Информатика. Тема 6. Численные методы решения задач.

6.1.1. Сортировка подсчетом
C
K1
K2
K3
K4
K5
K6
K7
K8
K9
K10 K11 K12 K13 K14 K15 K16
503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703
нач
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

7. Информатика. Тема 6. Численные методы решения задач.

6.1.1. Сортировка подсчетом
C
K1
K2
K3
K4
K5
K6
K7
K8
K9
K10 K11 K12 K13 K14 K15 K16
503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703
нач
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
i =N
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0

8. Информатика. Тема 6. Численные методы решения задач.

9. Информатика. Тема 6. Численные методы решения задач.

10. Информатика. Тема 6. Численные методы решения задач.

11. Информатика. Тема 6. Численные методы решения задач.

12. Информатика. Тема 6. Численные методы решения задач.

13. Информатика. Тема 6. Численные методы решения задач.

14. Информатика. Тема 6. Численные методы решения задач.

15. Информатика. Тема 6. Численные методы решения задач.

6.1.1. Сортировка подсчетом
C
K1
K2
K3
K4
K5
K6
K7
K8
K9
K10 K11 K12 K13 K14 K15 K16
503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703
нач
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
i =N
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
7

16. Информатика. Тема 6. Численные методы решения задач.

17. Информатика. Тема 6. Численные методы решения задач.

18. Информатика. Тема 6. Численные методы решения задач.

19. Информатика. Тема 6. Численные методы решения задач.

20. Информатика. Тема 6. Численные методы решения задач.

21. Информатика. Тема 6. Численные методы решения задач.

22. Информатика. Тема 6. Численные методы решения задач.

23. Информатика. Тема 6. Численные методы решения задач.

24. Информатика. Тема 6. Численные методы решения задач.

25. Информатика. Тема 6. Численные методы решения задач.

26. Информатика. Тема 6. Численные методы решения задач.

27. Информатика. Тема 6. Численные методы решения задач.

28. Информатика. Тема 6. Численные методы решения задач.

29. Информатика. Тема 6. Численные методы решения задач.

30. Информатика. Тема 6. Численные методы решения задач.

31. Информатика. Тема 6. Численные методы решения задач.

32. Информатика. Тема 6. Численные методы решения задач.

33. Информатика. Тема 6. Численные методы решения задач.

34. Информатика. Тема 6. Численные методы решения задач.

35. Информатика. Тема 6. Численные методы решения задач.

36. Информатика. Тема 6. Численные методы решения задач.

37. Информатика. Тема 6. Численные методы решения задач.

38. Информатика. Тема 6. Численные методы решения задач.

6.1.1. Сортировка подсчетом
C
K1
K2
K3
K4
K5
K6
K7
K8
K9
K10 K11 K12 K13 K14 K15 K16
503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703
нач
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
i =N
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
12
N-1
0
0
0
0
2
0
2
0
0
0
0
0
0
0
13
12
N-2
0
0
0
0
3
0
3
0
0
0
0
0
0
11
13
12
N-3
0
0
0
0
4
0
4
0
1
0
0
0
9
11
13
12
N-4
0
0
1
0
5
0
5
0
2
0
0
7
9
11
13
12

39. Информатика. Тема 6. Численные методы решения задач.

40. Информатика. Тема 6. Численные методы решения задач.

41. Информатика. Тема 6. Численные методы решения задач.

6.1.2. Сортировка вставками
Пусть записи R1, R2,…, Rj-1 размещены так, что K1 ≤ K2 ≤ Kj-1.
То есть считается, что предыдущие записи уже упорядочены.
Требуется разместить запись Rj.
Ключ Kj сравнивается по очереди с ключами Kj-1, Kj-2, Kj-3 … до тех
пор, пока не будет определено, что запись Rj необходимо вставить
между записями Ri и Ri+1.
Тогда записи Ri+1, Ri+2,…, Rj-1 сдвигаются.
Запись Rj занимает место (i+1).

42. Информатика. Тема 6. Численные методы решения задач.

Сортировка простыми вставками
503 087 512 061
908 170 897
275 653 426 154
509 612 677 765 703
087 503 512 061
908 170 897
275 653 426 154
509 612 677 765 703
Число сравнений – 1, число обменов – 1.

43. Информатика. Тема 6. Численные методы решения задач.

Сортировка простыми вставками
087 503 512 061
908 170 897
275 653 426 154
509 612 677 765 703
087 503 512 061
908 170 897
275 653 426 154
509 612 677 765 703
Число сравнений – 2, число обменов – 1.

44. Информатика. Тема 6. Численные методы решения задач.

Сортировка простыми вставками
087 503 512 061
908 170 897
275 653 426 154
509 612 677 765 703
087 503 512 061
908 170 897
275 653 426 154
509 612 677 765 703
087 503 512 061
908 170 897
275 653 426 154
509 612 677 765 703
061 087 503 512
908 170 897
275 653 426 154
509 612 677 765 703
Число сравнений – 5, число обменов – 4.

45. Информатика. Тема 6. Численные методы решения задач.

Сортировка простыми вставками
061 087 503 512
908 170 897
275 653 426 154
509 612 677 765 703
061 087 503 512
908 170 897
275 653 426 154
509 612 677 765 703
Число сравнений – 6, число обменов – 4.

46. Информатика. Тема 6. Численные методы решения задач.

Сортировка простыми вставками
061 087 503 512
908 170 897
275 653 426 154
509 612 677 765 703
061 087 503 512
908 170 897
275 653 426 154
509 612 677 765 703
061 087 503 512
908 170 897
275 653 426 154
509 612 677 765 703
061 087 503 512
908 170 897
275 653 426 154
509 612 677 765 703
061 087 170 503
512 908 897
275 653 426 154
509 612 677 765 703
Число сравнений – 9, число обменов – 7.

47. Информатика. Тема 6. Численные методы решения задач.

Сортировка простыми вставками
061 087 170 503
512 908 897
275 653 426 154
509 612 677 765 703
061 087 170 503
512 908 897
275 653 426 154
509 612 677 765 703
061 087 170 503
512 897 908
275 653 426 154
509 612 677 765 703
Число сравнений – 11, число обменов – 8.

48. Информатика. Тема 6. Численные методы решения задач.

Сортировка простыми вставками
061 087 170 503
512 897 908
275 653 426 154
509 612 677 765 703
061 087 170 503 512 897 908 275 653 426 154 509 612 677 765 703
061 087 170 503
512 897 908
275 653 426 154
509 612 677 765 703
061 087 170 503
512 897 908
275 653 426 154
509 612 677 765 703
061 087 170 503
512 897 908
275 653 426 154
509 612 677 765 703
061 087 170 275
503 512 897
908 653 426 154
509 612 677 765 703
Число сравнений – 16, число обменов – 12.

49. Информатика. Тема 6. Численные методы решения задач.

Сортировка простыми вставками
061 087 170 275
503 512 897
908 653 426 154
509 612 677 765 703
061 087 170 275
503 512 897
908 653 426 154
509 612 677 765 703
061 087 170 275 503 512 897 908 653 426 154 509 612 677 765 703
061 087 170 275
503 512 653
897 908 426 154
509 612 677 765 703
Число сравнений – 19, число обменов – 14.

50. Информатика. Тема 6. Численные методы решения задач.

061 087 170 275
503 512 653
897 908 426 154
509 612 677 765 703
061 087 170 275
503 512 653
897 908 426 154
509 612 677 765 703
061 087 170 275
503 512 653
897 908 426 154
509 612 677 765 703
061 087 170 275
503 512 653
897 908 426 154
509 612 677 765 703
061 087 170 275
503 512 653
897 908 426 154
509 612 677 765 703
061 087 170 275
503 512 653
897 908 426 154
509 612 677 765 703
061 087 170 275
503 512 653
897 908 426 154
509 612 677 765 703
061 087 170 275
426 503 512
653 897 908 154
509 612 677 765 703
Число сравнений – 25, число обменов – 19.

51. Информатика. Тема 6. Численные методы решения задач.

Сортировка простыми вставками
061 087 170 275
426 503 512
653 897 908 154
509 612 677 765 703
061 087 170 275
426 503 512
653 897 908 154
509 612 677 765 703
061 087 170 275
426 503 512
653 897 908 154
509 612 677 765 703
061 087 170 275
426 503 512
653 897 908 154
509 612 677 765 703
061 087 170 275
426 503 512
653 897 908 154
509 612 677 765 703
…
061 087 170 275 426 503 512 653 897 908 154 509 612 677 765 703
061 087 154 170
275 426 503
512 653 897 908
509 612 677 765 703
Число сравнений – 34, число обменов – 27.

52. Информатика. Тема 6. Численные методы решения задач.

Сортировка простыми вставками
061 087 154 170
275 426 503
512 653 897 908
509 612 677 765 703
061 087 154 170
275 426 503
512 653 897 908
509 612 677 765 703
061 087 154 170
275 426 503
512 653 897 908
509 612 677 765 703
061 087 154 170
275 426 503
512 653 897 908
509 612 677 765 703
061 087 154 170
275 426 503
512 653 897 908
509 612 677 765 703
061 087 154 170
275 426 503
509 512 653 897
908 612 677 765 703
Число сравнений – 39, число обменов – 31.

53. Информатика. Тема 6. Численные методы решения задач.

Сортировка простыми вставками
061 087 154 170
275 426 503
509 512 653 897
908 612 677 765 703
061 087 154 170
275 426 503
509 512 653 897
908 612 677 765 703
061 087 154 170
275 426 503
509 512 653 897
908 612 677 765 703
061 087 154 170
275 426 503
509 512 653 897
908 612 677 765 703
061 087 154 170
275 426 503
509 512 612 653
897 908 677 765 703
Число сравнений – 43, число обменов – 34.

54. Информатика. Тема 6. Численные методы решения задач.

Сортировка простыми вставками
061 087 154 170
275 426 503
509 512 612 653
897 908 677 765 703
061 087 154 170
275 426 503
509 512 612 653
897 908 677 765 703
061 087 154 170
275 426 503
509 512 612 653
897 908 677 765 703
061 087 154 170
275 426 503
509 512 612 653
677 897 908 765 703
Число сравнений – 46, число обменов – 36.

55. Информатика. Тема 6. Численные методы решения задач.

Сортировка простыми вставками
061 087 154 170
275 426 503
509 512 612 653
677 897 908 765 703
061 087 154 170
275 426 503
509 512 612 653
677 897 908 765 703
061 087 154 170
275 426 503
509 512 612 653
677 897 908 765 703
061 087 154 170
275 426 503
509 512 612 653
677 765 897 908 703
Число сравнений – 49, число обменов – 38.

56. Информатика. Тема 6. Численные методы решения задач.

Сортировка простыми вставками
061 087 154 170
275 426 503
509 512 612 653
677 765 897 908 703
061 087 154 170
275 426 503
509 512 612 653
677 765 897 908 703
061 087 154 170
275 426 503
509 512 612 653
677 765 897 908 703
061 087 154 170
275 426 503
509 512 612 653
677 765 897 908 703
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
Число сравнений – 53, число обменов – 41.

57. Информатика. Тема 6. Численные методы решения задач.

Сортировка бинарными вставками
061 087 170 275
426 503 512
653 897 908 154
509 612 677 765 703
061 087 170 275
426 503 512
653 897 908 154
509 612 677 765 703
061 087 170 275
426 503 512
653 897 908 154
509 612 677 765 703
061 087 154 170
275 426 503
512 653 897 908
509 612 677 765 703

58. Информатика. Тема 6. Численные методы решения задач.

Сортировка двухпутевыми вставками
ключи 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703
503
087 503
087 503 512
061 087 503 512
061 087 503 512 908
061 087 170 503 512 908
061 087 170 503 512 897 908
·····
·····
·····
·····
·····
·····
·····
·····
·····
·····
·····
·····
·····
·····
·····
·····
·····
061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908

59. Информатика. Тема 6. Численные методы решения задач.

6.1.3. Сортировка выбором
При сортировке записей R1, R2,…, RN
1) Находится запись Rj, имеющая наибольший ключ Kj.
2) Происходит обмен записей Rj и RN.
3) Процедура поиска наибольшего ключа повторяется для записей
R1, R2,…, RN-1. Подобная процедура повторяется (N-1) раз.

60. Информатика. Тема 6. Численные методы решения задач.

Сортировка выбором
503 087 512 061
908 170 897
275 653 426 154
509 612 677 765 703
503 087 512 061 703 170 897 275 653 426 154 509 612 677 765 908
Число сравнений – 15, число обменов – 1.

61. Информатика. Тема 6. Численные методы решения задач.

Сортировка выбором
503 087 512 061
703 170 897
275 653 426 154
509 612 677 765 908
503 087 512 061
703 170 765
275 653 426 154
509 612 677 897 908
Число сравнений – 29, число обменов – 2.

62. Информатика. Тема 6. Численные методы решения задач.

Сортировка выбором
503 087 512 061
703 170 765
275 653 426 154
509 612 677 897 908
503 087 512 061
703 170 677
275 653 426 154
509 612 765 897 908
Число сравнений – 42, число обменов – 3.

63. Информатика. Тема 6. Численные методы решения задач.

Сортировка выбором
503 087 512 061
703 170 677
275 653 426 154
509 612 765 897 908
503 087 512 061
612 170 677
275 653 426 154
509 703 765 897 908
Число сравнений – 54, число обменов – 4.

64. Информатика. Тема 6. Численные методы решения задач.

Сортировка выбором
503 087 512 061
612 170 677
275 653 426 154
509 703 765 897 908
503 087 512 061
612 170 509
275 653 426 154
677 703 765 897 908
Число сравнений – 65, число обменов – 5.

65. Информатика. Тема 6. Численные методы решения задач.

Сортировка выбором
503 087 512 061
612 170 509
275 653 426 154
677 703 765 897 908
503 087 512 061
612 170 509
275 154 426 653
677 703 765 897 908
Число сравнений – 75, число обменов – 6.

66. Информатика. Тема 6. Численные методы решения задач.

Сортировка выбором
503 087 512 061
612 170 509
275 154 426 653
677 703 765 897 908
503 087 512 061
426 170 509
275 154 612 653
677 703 765 897 908
Число сравнений – 84, число обменов – 7.

67. Информатика. Тема 6. Численные методы решения задач.

Сортировка выбором
503 087 512 061
426 170 509
275 154 612 653
677 703 765 897 908
503 087 154 061
426 170 509
275 512 612 653
677 703 765 897 908
Число сравнений – 92, число обменов – 8.

68. Информатика. Тема 6. Численные методы решения задач.

Сортировка выбором
503 087 154 061
426 170 509
275 512 612 653
677 703 765 897 908
503 087 154 061
426 170 275
509 512 612 653
677 703 765 897 908
Число сравнений – 99, число обменов – 9.

69. Информатика. Тема 6. Численные методы решения задач.

Сортировка выбором
503 087 154 061
426 170 275
509 512 612 653
677 703 765 897 908
275 087 154 061
426 170 503
509 512 612 653
677 703 765 897 908
Число сравнений – 105, число обменов – 10.

70. Информатика. Тема 6. Численные методы решения задач.

Сортировка выбором
275 087 154 061
426 170 503
509 512 612 653
677 703 765 897 908
275 087 154 061
170 426 503
509 512 612 653
677 703 765 897 908
Число сравнений – 110, число обменов – 11.

71. Информатика. Тема 6. Численные методы решения задач.

Сортировка выбором
275 087 154 061
170 426 503
509 512 612 653
677 703 765 897 908
170 087 154 061
275 426 503
509 512 612 653
677 703 765 897 908
Число сравнений – 114, число обменов – 12.

72. Информатика. Тема 6. Численные методы решения задач.

Сортировка выбором
170 087 154 061
275 426 503
509 512 612 653
677 703 765 897 908
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
Число сравнений – 117, число обменов – 13.

73. Информатика. Тема 6. Численные методы решения задач.

Сортировка выбором
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
Число сравнений – 119, число обменов – 13.

74. Информатика. Тема 6. Численные методы решения задач.

Сортировка выбором
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908
Число сравнений – 120, число обменов – 13.

75. Информатика. Тема 6. Численные методы решения задач.

6.1.4. Сортировка обменом
Простейший обменный алгоритм называется «пузырек».
При сортировке записей R1, R2,…, RN алгоритмом «пузырек»
1) Сравниваются ключи двух соседних записей Rj и Rj-1.
2) Если ключ Kj меньше ключа Kj-1 записи Rj и Rj-1 обмениваются.

76. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
503 087 512 061
908 170 897
275 653 426 154
509 612 677 765 703
087 503 512 061
908 170 897
275 653 426 154
509 612 677 765 703
Число сравнений – 1, число обменов – 1.

77. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 503 512 061
908 170 897
275 653 426 154
509 612 677 765 703
087 503 512 061
908 170 897
275 653 426 154
509 612 677 765 703
087 503 061 512
908 170 897
275 653 426 154
509 612 677 765 703
Число сравнений – 3, число обменов – 2.

78. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 503 061 512
908 170 897
275 653 426 154
509 612 677 765 703
087 503 061 512
908 170 897
275 653 426 154
509 612 677 765 703
087 503 061 512
170 908 897
275 653 426 154
509 612 677 765 703
Число сравнений – 5, число обменов – 3.

79. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 503 061 512
170 908 897
275 653 426 154
509 612 677 765 703
087 503 061 512
170 897 908
275 653 426 154
509 612 677 765 703
Число сравнений – 6, число обменов – 4.

80. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 503 061 512
170 897 908
275 653 426 154
509 612 677 765 703
087 503 061 512
170 897 275
908 653 426 154
509 612 677 765 703
Число сравнений – 7, число обменов – 5.

81. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 503 061 512
170 897 275
908 653 426 154
509 612 677 765 703
087 503 061 512
170 897 275
653 908 426 154
509 612 677 765 703
Число сравнений – 8, число обменов – 6.

82. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 503 061 512
170 897 275
653 908 426 154
509 612 677 765 703
087 503 061 512
170 897 275
653 426 908 154
509 612 677 765 703
Число сравнений – 9, число обменов – 7.

83. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 503 061 512
170 897 275
653 426 908 154
509 612 677 765 703
087 503 061 512
170 897 275
653 426 154 908
509 612 677 765 703
Число сравнений – 10, число обменов – 8.

84. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 503 061 512
170 897 275
653 426 154 908
509 612 677 765 703
087 503 061 512
170 897 275
653 426 154 509
908 612 677 765 703
Число сравнений – 11, число обменов – 9.

85. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 503 061 512
170 897 275
653 426 154 509
908 612 677 765 703
087 503 061 512
170 897 275
653 426 154 509
612 908 677 765 703
Число сравнений – 12, число обменов – 10.

86. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 503 061 512
170 897 275
653 426 154 509
612 908 677 765 703
087 503 061 512
170 897 275
653 426 154 509
612 677 908 765 703
Число сравнений – 13, число обменов – 11.

87. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 503 061 512
170 897 275
653 426 154 509
612 677 908 765 703
087 503 061 512
170 897 275
653 426 154 509
612 677 765 908 703
Число сравнений – 14, число обменов – 12.

88. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 503 061 512
170 897 275
653 426 154 509
612 677 765 908 703
087 503 061 512
170 897 275
653 426 154 509
612 677 765 703 908
Число сравнений – 15, число обменов – 13.

89. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 503 061 512
170 897 275
653 426 154 509
612 677 765 703 908
087 503 061 512
170 897 275
653 426 154 509
612 677 765 703 908
087 061 503 512
170 897 275
653 426 154 509
612 677 765 703 908
Число сравнений – 17, число обменов – 14.

90. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 061 503 512
170 897 275
653 426 154 509
612 677 765 703 908
087 061 503 512
170 897 275
653 426 154 509
612 677 765 703 908
087 061 503 170
512 897 275
653 426 154 509
612 677 765 703 908
Число сравнений – 19, число обменов – 15.

91. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 061 503 170
512 897 275
653 426 154 509
612 677 765 703 908
087 061 503 170
512 897 275
653 426 154 509
612 677 765 703 908
087 061 503 170
512 275 897
653 426 154 509
612 677 765 703 908
Число сравнений – 21, число обменов – 16.

92. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 061 503 170
512 275 897
653 426 154 509
612 677 765 703 908
087 061 503 170
512 275 653
897 426 154 509
612 677 765 703 908
Число сравнений – 22, число обменов – 17.

93. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 061 503 170
512 275 653
897 426 154 509
612 677 765 703 908
087 061 503 170
512 275 653
426 897 154 509
612 677 765 703 908
Число сравнений – 23, число обменов – 18.

94. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 061 503 170
512 275 653
426 897 154 509
612 677 765 703 908
087 061 503 170
512 275 653
426 154 897 509
612 677 765 703 908
Число сравнений – 24, число обменов – 19.

95. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 061 503 170
512 275 653
426 154 897 509
612 677 765 703 908
087 061 503 170
512 275 653
426 154 509 897
612 677 765 703 908
Число сравнений – 25, число обменов – 20.

96. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 061 503 170
512 275 653
426 154 509 897
612 677 765 703 908
087 061 503 170
512 275 653
426 154 509 612
897 677 765 703 908
Число сравнений – 26, число обменов – 21.

97. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 061 503 170
512 275 653
426 154 509 612
897 677 765 703 908
087 061 503 170
512 275 653
426 154 509 612
677 897 765 703 908
Число сравнений – 27, число обменов – 22.

98. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 061 503 170
512 275 653
426 154 509 612
677 897 765 703 908
087 061 503 170
512 275 653
426 154 509 612
677 765 897 703 908
Число сравнений – 28, число обменов – 23.

99. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 061 503 170
512 275 653
426 154 509 612
677 765 897 703 908
087 061 503 170
512 275 653
426 154 509 612
677 765 703 897 908
Число сравнений – 29, число обменов – 24.

100. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
087 061 503 170
512 275 653
426 154 509 612
677 765 703 897 908
061 087 503 170
512 275 653
426 154 509 612
677 765 703 897 908
Число сравнений – 30, число обменов – 25.

101. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 503 170
512 275 653
426 154 509 612
677 765 703 897 908
061 087 503 170
512 275 653
426 154 509 612
677 765 703 897 908
061 087 170 503
512 275 653
426 154 509 612
677 765 703 897 908
Число сравнений – 32, число обменов – 26.

102. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 170 503
512 275 653
426 154 509 612
677 765 703 897 908
061 087 170 503
512 275 653
426 154 509 612
677 765 703 897 908
061 087 170 503
275 512 653
426 154 509 612
677 765 703 897 908
Число сравнений – 34, число обменов – 27.

103. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 170 503
275 512 653
426 154 509 612
677 765 703 897 908
061 087 170 503
275 512 653
426 154 509 612
677 765 703 897 908
061 087 170 503
275 512 426
653 154 509 612
677 765 703 897 908
Число сравнений – 36, число обменов – 28.

104. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 170 503
275 512 426
653 154 509 612
677 765 703 897 908
061 087 170 503
275 512 426
154 653 509 612
677 765 703 897 908
Число сравнений – 37, число обменов – 29.

105. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 170 503
275 512 426
154 653 509 612
677 765 703 897 908
061 087 170 503
275 512 426
154 509 653 612
677 765 703 897 908
Число сравнений – 38, число обменов – 30.

106. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 170 503
275 512 426
154 509 653 612
677 765 703 897 908
061 087 170 503
275 512 426
154 509 612 653
677 765 703 897 908
Число сравнений – 39, число обменов – 31.

107. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 170 503
275 512 426
154 509 612 653
677 765 703 897 908
061 087 170 503
275 512 426
154 509 612 653
677 765 703 897 908
061 087 170 503
275 512 426
154 509 612 653
677 765 703 897 908
061 087 170 503
275 512 426
154 509 612 653
677 703 765 897 908
Число сравнений – 42, число обменов – 32.

108. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 170 503
275 512 426
154 509 612 653
677 703 765 897 908
061 087 170 503
275 512 426
154 509 612 653
677 703 765 897 908
061 087 170 503
275 512 426
154 509 612 653
677 703 765 897 908
061 087 170 503
275 512 426
154 509 612 653
677 703 765 897 908
061 087 170 275
503 512 426
154 509 612 653
677 703 765 897 908
Число сравнений – 46, число обменов – 33.

109. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 170 275
503 512 426
154 509 612 653
677 703 765 897 908
061 087 170 275
503 512 426
154 509 612 653
677 703 765 897 908
061 087 170 275
503 426 512
154 509 612 653
677 703 765 897 908
Число сравнений – 48, число обменов – 34.

110. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 170 275
503 426 512
154 509 612 653
677 703 765 897 908
061 087 170 275
503 426 154
512 509 612 653
677 703 765 897 908
Число сравнений – 49, число обменов – 35.

111. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 170 275
503 426 154
512 509 612 653
677 703 765 897 908
061 087 170 275
503 426 154
509 512 612 653
677 703 765 897 908
Число сравнений – 50, число обменов – 36.

112. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 170 275
503 426 154
509 512 612 653
677 703 765 897 908
061 087 170 275
503 426 154
509 512 612 653
677 703 765 897 908
061 087 170 275
503 426 154
509 512 612 653
677 703 765 897 908
061 087 170 275
503 426 154
509 512 612 653
677 703 765 897 908
061 087 170 275
503 426 154
509 512 612 653
677 703 765 897 908
Число сравнений – 54, число обменов – 36.

113. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 170 275
503 426 154
509 512 612 653
677 703 765 897 908
061 087 170 275
503 426 154
509 512 612 653
677 703 765 897 908
061 087 170 275
503 426 154
509 512 612 653
677 703 765 897 908
061 087 170 275
503 426 154
509 512 612 653
677 703 765 897 908
061 087 170 275
503 426 154
509 512 612 653
677 703 765 897 908
061 087 170 275
426 503 154
509 512 612 653
677 703 765 897 908
Число сравнений – 59, число обменов – 37.

114. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 170 275 426 503 154 509 512 612 653 677 703 765 897 908
061 087 170 275
426 154 503
509 512 612 653
677 703 765 897 908
Число сравнений – 60, число обменов – 38.

115. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 170 275 426 154 503 509 512 612 653 677 703 765 897 908
061 087 170 275
426 154 503
509 512 612 653
677 703 765 897 908
061 087 170 275
426 154 503
509 512 612 653
677 703 765 897 908
061 087 170 275
426 154 503
509 512 612 653
677 703 765 897 908
061 087 170 275
426 154 503
509 512 612 653
677 703 765 897 908
061 087 170 275
426 154 503
509 512 612 653
677 703 765 897 908
Число сравнений – 65, число обменов – 38.

116. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 170 275 426 154 503 509 512 612 653 677 703 765 897 908
061 087 170 275
426 154 503
509 512 612 653
677 703 765 897 908
061 087 170 275
426 154 503
509 512 612 653
677 703 765 897 908
061 087 170 275
426 154 503
509 512 612 653
677 703 765 897 908
061 087 170 275
426 154 503
509 512 612 653
677 703 765 897 908
061 087 170 275
154 426 503
509 512 612 653
677 703 765 897 908
Число сравнений – 70, число обменов – 39.

117. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 170 275 154 426 503 509 512 612 653 677 703 765 897 908
061 087 170 275
154 426 503
509 512 612 653
677 703 765 897 908
061 087 170 275
154 426 503
509 512 612 653
677 703 765 897 908
061 087 170 275
154 426 503
509 512 612 653
677 703 765 897 908
061 087 170 275
154 426 503
509 512 612 653
677 703 765 897 908
061 087 170 275
154 426 503
509 512 612 653
677 703 765 897 908
Число сравнений – 75, число обменов – 39.

118. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 170 275 154 426 503 509 512 612 653 677 703 765 897 908
061 087 170 275
154 426 503
509 512 612 653
677 703 765 897 908
061 087 170 275
154 426 503
509 512 612 653
677 703 765 897 908
061 087 170 275
154 426 503
509 512 612 653
677 703 765 897 908
061 087 170 154
275 426 503
509 512 612 653
677 703 765 897 908
Число сравнений – 79, число обменов – 40.

119. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 170 154 275 426 503 509 512 612 653 677 703 765 897 908
061 087 170 154
275 426 503
509 512 612 653
677 703 765 897 908
061 087 170 154
275 426 503
509 512 612 653
677 703 765 897 908
061 087 170 154
275 426 503
509 512 612 653
677 703 765 897 908
061 087 170 154
275 426 503
509 512 612 653
677 703 765 897 908
061 087 170 154
275 426 503
509 512 612 653
677 703 765 897 908
Число сравнений – 84, число обменов – 40.

120. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 170 154 275 426 503 509 512 612 653 677 703 765 897 908
061 087 170 154
275 426 503
509 512 612 653
677 703 765 897 908
061 087 170 154
275 426 503
509 512 612 653
677 703 765 897 908
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
Число сравнений – 87, число обменов – 41.

121. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908
Число сравнений – 92, число обменов – 41.

122. Информатика. Тема 6. Численные методы решения задач.

Сортировка «пузырьком»
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
Число сравнений – 99, число обменов – 41.

123. Информатика. Тема 6. Численные методы решения задач.

6.1.5. Сортировка методом Шелла
При сортировке «пузырьком» сравниваются ключи соседних записей
(шаг сортировки равен единице).
Быстродействие можно повысить, применяя сортировку с
убывающим шагом.
Дональд Шелл – американский ученый в области информатики

124. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 8)
503 087 512 061
908 170 897
275 653 426 154
509 612 677 765 703
503 087 154 061
612 170 765
275 653 426 512
509 908 677 897 703
Число сравнений – 8, число обменов – 3.

125. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 4)
503 087 154 061
612 170 765
275 653 426 512
509 908 677 897 703
503 087 154 061
612 170 765
275 653 426 512
509 908 677 897 703
Число сравнений – 11, число обменов – 3.

126. Информатика. Тема 6. Численные методы решения задач.

127. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 4)
503 087 154 061
612 170 765
275 653 426 512
509 908 677 897 703
503 087 154 061
612 170 512
275 653 426 765
509 908 677 897 703
Число сравнений – 18, число обменов – 4.

128. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 4)
503 087 154 061
612 170 512
275 653 426 765
509 908 677 897 703
503 087 154 061
612 170 512
275 653 426 765
509 908 677 897 703
Число сравнений – 21, число обменов – 4.

129. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 2)
503 087 154 061 612 170 512 275 653 426 765 509 908 677 897 703
154 087 503 061
612 170 512
275 653 426 765
509 908 677 897 703
154 087 503 061
612 170 512
275 653 426 765
509 908 677 897 703
154 087 503 061
512 170 612
275 653 426 765
509 908 677 897 703
154 087 503 061
512 170 612
275 653 426 765
509 908 677 897 703
154 087 503 061
512 170 612
275 653 426 765
509 908 677 897 703
154 087 503 061
512 170 612
275 653 426 765
509 908 677 897 703
154 087 503 061
512 170 612
275 653 426 765
509 897 677 908 703
Число сравнений – 30, число обменов – 7.

130. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 2)
154 087 503 061
512 170 612
275 653 426 765
509 897 677 908 703
154 061 503 087
512 170 612
275 653 426 765
509 897 677 908 703
154 061 503 087
512 170 612
275 653 426 765
509 897 677 908 703
154 061 503 087
512 170 612
275 653 426 765
509 897 677 908 703
154 061 503 087
512 170 612
275 653 426 765
509 897 677 908 703
154 061 503 087
512 170 612
275 653 426 765
509 897 677 908 703
154 061 503 087 512 170 612 275 653 426 765 509 897 677 908 703
154 061 503 087
512 170 612
275 653 426 765
509 897 677 908 703
Число сравнений – 37, число обменов – 8.

131. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 1)
154 061 503 087
512 170 612
275 653 426 765
509 897 677 908 703
061 154 503 087
512 170 612
275 653 426 765
509 897 677 908 703
Число сравнений – 38, число обменов – 9.

132. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 1)
061 154 503 087
512 170 612
275 653 426 765
509 897 677 908 703
061 154 503 087
512 170 612
275 653 426 765
509 897 677 908 703
Число сравнений – 39, число обменов – 9.

133. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 1)
061 154 503 087
512 170 612
275 653 426 765
509 897 677 908 703
061 154 503 087
512 170 612
275 653 426 765
509 897 677 908 703
061 154 503 087
512 170 612
275 653 426 765
509 897 677 908 703
061 087 154 503
512 170 612
275 653 426 765
509 897 677 908 703
Число сравнений – 42, число обменов – 11.

134. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 1)
061 087 154 503
512 170 612
275 653 426 765
509 897 677 908 703
061 087 154 503
512 170 612
275 653 426 765
509 897 677 908 703
Число сравнений – 43, число обменов – 11.

135. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 1)
061 087 154 503
512 170 612
275 653 426 765
509 897 677 908 703
061 087 154 503
512 170 612
275 653 426 765
509 897 677 908 703
061 087 154 503
512 170 612
275 653 426 765
509 897 677 908 703
061 087 154 170
503 512 612
275 653 426 765
509 897 677 908 703
Число сравнений – 46, число обменов – 13.

136. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 1)
061 087 154 170
503 512 612
275 653 426 765
509 897 677 908 703
061 087 154 170
503 512 612
275 653 426 765
509 897 677 908 703
Число сравнений – 47, число обменов – 13.

137. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 1)
061 087 154 170
503 512 612
275 653 426 765
509 897 677 908 703
061 087 154 170
503 512 612
275 653 426 765
509 897 677 908 703
061 087 154 170 503 512 612 275 653 426 765 509 897 677 908 703
061 087 154 170
503 512 612
275 653 426 765
509 897 677 908 703
061 087 154 170
275 503 512
612 653 426 765
509 897 677 908 703
Число сравнений – 51, число обменов – 16.

138. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 1)
061 087 154 170
275 503 512
612 653 426 765
509 897 677 908 703
061 087 154 170
275 503 512
612 653 426 765
509 897 677 908 703
Число сравнений – 52, число обменов – 16.

139. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 1)
061 087 154 170
275 503 512
612 653 426 765
509 897 677 908 703
061 087 154 170
275 503 512
612 653 426 765
509 897 677 908 703
061 087 154 170
275 503 512
612 653 426 765
509 897 677 908 703
061 087 154 170
275 503 512
612 653 426 765
509 897 677 908 703
061 087 154 170
275 503 512
612 653 426 765
509 897 677 908 703
061 087 154 170
275 426 503
512 612 653 765
509 897 677 908 703
Число сравнений – 57, число обменов – 20.

140. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 1)
061 087 154 170 275 426 503 512 612 653 765 509 897 677 908 703
061 087 154 170
275 426 503
512 612 653 765
509 897 677 908 703
Число сравнений – 58, число обменов – 20.

141. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 1)
061 087 154 170 275 426 503 512 612 653 765 509 897 677 908 703
061 087 154 170 275 426 503 512 612 653 765 509 897 677 908 703
061 087 154 170
275 426 503
512 612 653 765
509 897 677 908 703
061 087 154 170
275 426 503
512 612 653 765
509 897 677 908 703
061 087 154 170
275 426 503
512 612 653 765
509 897 677 908 703
061 087 154 170
275 426 503
509 512 612 653
765 897 677 908 703
Число сравнений – 63, число обменов – 24.

142. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 1)
061 087 154 170 275 426 503 509 512 612 653 765 897 677 908 703
061 087 154 170
275 426 503
509 512 612 653
765 897 677 908 703
Число сравнений – 64, число обменов – 24.

143. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 1)
061 087 154 170 275 426 503 509 512 612 653 765 897 677 908 703
061 087 154 170 275 426 503 509 512 612 653 765 897 677 908 703
061 087 154 170
275 426 503
509 512 612 653
765 897 677 908 703
061 087 154 170
275 426 503
509 512 612 653
677 765 897 908 703
Число сравнений – 67, число обменов – 26.

144. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 1)
061 087 154 170 275 426 503 509 512 612 653 677 765 897 908 703
061 087 154 170
275 426 503
509 512 612 653
677 765 897 908 703
Число сравнений – 68, число обменов – 26.

145. Информатика. Тема 6. Численные методы решения задач.

Сортировка методом Шелла (шаг сортировки равен 1)
061 087 154 170 275 426 503 509 512 612 653 677 765 897 908 703
061 087 154 170 275 426 503 509 512 612 653 677 765 897 908 703
061 087 154 170
275 426 503
509 512 612 653
677 765 897 908 703
061 087 154 170
275 426 503
509 512 612 653
677 765 897 908 703
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
Число сравнений – 72, число обменов – 29.

146. Информатика. Тема 6. Численные методы решения задач.

6.1.6. «Быстрая» сортировка
В 1962 году Ч.Э.Р. Хоар предложил обменную сортировку с
разделением, которую назвал quicksort (быстрая сортировка).
Чарльз Энтони Ричард Хоар –
английский ученый в области
информатики

147. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
503 087 512 061
908 170 897
275 653 426 154
509 612 677 765 703
503 087 512 061
908 170 897
275 653 426 154
509 612 677 765 703
503 087 512 061
908 170 897
275 653 426 154
509 612 677 765 703
503 087 512 061
908 170 897
275 653 426 154
509 612 677 765 703
503 087 512 061
908 170 897
275 653 426 154
509 612 677 765 703
503 087 512 061
908 170 897
275 653 426 154
509 612 677 765 703
154 087 512 061
908 170 897
275 653 426 503
509 612 677 765 703
Число сравнений – 6, число обменов – 1.

148. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
154 087 512 061
908 170 897
275 653 426 503
509 612 677 765 703
154 087 512 061
908 170 897
275 653 426 503
509 612 677 765 703
154 087 503 061
908 170 897
275 653 426 512
509 612 677 765 703
Число сравнений – 8, число обменов – 2.

149. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
154 087 503 061 908 170 897 275 653 426 512 509 612 677 765 703
154 087 426 061
908 170 897
275 653 503 512
509 612 677 765 703
Число сравнений – 9, число обменов – 3.

150. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
154 087 426 061 908 170 897 275 653 503 512 509 612 677 765 703
154 087 426 061
908 170 897
275 653 503 512
509 612 677 765 703
154 087 426 061
503 170 897
275 653 908 512
509 612 677 765 703
Число сравнений – 11, число обменов – 4.

151. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
154 087 426 061 503 170 897 275 653 908 512 509 612 677 765 703
154 087 426 061
503 170 897
275 653 908 512
509 612 677 765 703
154 087 426 061
275 170 897
503 653 908 512
509 612 677 765 703
Число сравнений – 13, число обменов – 5.

152. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
154 087 426 061 275 170 897 503 653 908 512 509 612 677 765 703
154 087 426 061
275 170 897
503 653 908 512
509 612 677 765 703
154 087 426 061
275 170 503
897 653 908 512
509 612 677 765 703
Число сравнений – 15, число обменов – 6.

153. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
154 087 426 061 275 170 503 897 653 908 512 509 612 677 765 703
154 087 426 061
275 170 503
897 653 908 512
509 612 677 765 703
154 087 426 061
275 170 503
897 653 908 512
509 612 677 765 703
061 087 426 154
275 170 503
897 653 908 512
509 612 677 765 703
Число сравнений – 18, число обменов – 7.

154. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
061 087 426 154 275 170 503 897 653 908 512 509 612 677 765 703
061 087 426 154
275 170 503
897 653 908 512
509 612 677 765 703
061 087 154 426
275 170 503
897 653 908 512
509 612 677 765 703
Число сравнений – 20, число обменов – 8.

155. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
061 087 154 426
275 170 503
897 653 908 512
509 612 677 765 703
061 087 154 426
275 170 503
897 653 908 512
509 612 677 765 703
Число сравнений – 21, число обменов – 8.

156. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
061 087 154 426
275 170 503
897 653 908 512
509 612 677 765 703
061 087 154 170
275 426 503
897 653 908 512
509 612 677 765 703
Число сравнений – 22, число обменов – 9.

157. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
061 087 154 170 275 426 503 897 653 908 512 509 612 677 765 703
061 087 154 170
275 426 503
897 653 908 512
509 612 677 765 703
Число сравнений – 23, число обменов – 9.

158. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
061 087 154 170 275 426 503 897 653 908 512 509 612 677 765 703
061 087 154 170
275 426 503
897 653 908 512
509 612 677 765 703
Число сравнений – 24, число обменов – 9.

159. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
061 087 154 170 275 426 503 897 653 908 512 509 612 677 765 703
061 087 154 170
275 426 503
703 653 908 512
509 612 677 765 897
Число сравнений – 25, число обменов – 10.

160. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
061 087 154 170 275 426 503 703 653 908 512 509 612 677 765 897
061 087 154 170
275 426 503
703 653 908 512
509 612 677 765 897
061 087 154 170
275 426 503
703 653 897 512
509 612 677 765 908
Число сравнений – 27, число обменов – 11.

161. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
061 087 154 170 275 426 503 703 653 897 512 509 612 677 765 908
061 087 154 170
275 426 503
703 653 765 512
509 612 677 897 908
Число сравнений – 28, число обменов – 12.

162. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
061 087 154 170 275 426 503 703 653 765 512 509 612 677 897 908
061 087 154 170
275 426 503
703 653 765 512
509 612 677 897 908
061 087 154 170
275 426 503
703 653 765 512
509 612 677 897 908
061 087 154 170
275 426 503
703 653 765 512
509 612 677 897 908
061 087 154 170
275 426 503
703 653 765 512
509 612 677 897 908
Число сравнений – 32, число обменов – 12.

163. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
061 087 154 170 275 426 503 703 653 765 512 509 612 677 897 908
061 087 154 170
275 426 503
677 653 765 512
509 612 703 897 908
Число сравнений – 33, число обменов – 13.

164. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
061 087 154 170 275 426 503 677 653 765 512 509 612 703 897 908
061 087 154 170
275 426 503
677 653 765 512
509 612 703 897 908
061 087 154 170
275 426 503
677 653 703 512
509 612 765 897 908
Число сравнений – 35, число обменов – 14.

165. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
061 087 154 170
275 426 503
677 653 703 512
509 612 765 897 908
061 087 154 170
275 426 503
677 653 612 512
509 703 765 897 908
Число сравнений – 36, число обменов – 15.

166. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
061 087 154 170 275 426 503 677 653 612 512 509 703 765 897 908
061 087 154 170
275 426 503
677 653 612 512
509 703 765 897 908
061 087 154 170
275 426 503
677 653 612 512
509 703 765 897 908
Число сравнений – 38, число обменов – 15.

167. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
061 087 154 170 275 426 503 677 653 612 512 509 703 765 897 908
061 087 154 170
275 426 503
509 653 612 512
677 703 765 897 908
Число сравнений – 39, число обменов – 16.

168. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
061 087 154 170 275 426 503 509 653 612 512 677 703 765 897 908
061 087 154 170
275 426 503
509 653 612 512
677 703 765 897 908
061 087 154 170
275 426 503
509 653 612 512
677 703 765 897 908
061 087 154 170
275 426 503
509 653 612 512
677 703 765 897 908
Число сравнений – 42, число обменов – 16.

169. Информатика. Тема 6. Численные методы решения задач.

170. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
061 087 154 170 275 426 503 509 653 612 512 677 703 765 897 908
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
Число сравнений – 46, число обменов – 17.

171. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
Число сравнений – 47, число обменов – 17.

172. Информатика. Тема 6. Численные методы решения задач.

Быстрая сортировка
061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908
061 087 154 170
275 426 503
509 512 612 653
677 703 765 897 908
Число сравнений – 48, число обменов – 17.

173. Информатика. Тема 6. Численные методы решения задач.

6.1.7. Сравнение алгоритмов сортировки
Эффективность алгоритма сортировки характеризуется несколькими
параметрами:
1.Время сортировки
2.Память
3.Устойчивость
4.Естественность поведения
Время работы алгоритма сортировки зависит от количества
сравнений ключей и количества перестановок записей.
Поскольку исходные данные распределены случайно, то следует
говорить о минимальном, максимальном и среднем числе сравнений
и перестановок.

174. Информатика. Тема 6. Численные методы решения задач.

Сравнение алгоритмов сортировки
Алгоритм
Метод
подсчета
Метод
выбора
Число сравнений
N ( N 1)
2
N ( N 1)
2
Число перестановок
0; N ( N 1)
4
N ( N 1)
2
i 1
N
i
i 1
N
Метод
простых
вставок
N ( N 1) N ( N 1)
N-1;
0;
2
4
N ( N 1)
4
N ( N 1)
2
Обмен
«пузырьком»
Среднее значение –
N ( N 1)
4
N ( N 1)
2
0;
N 2 N (ln N ln 2 1)
O( N )
2
где γ – постоянная Эйлера,
γ≈0,577

175. Информатика. Тема 6. Численные методы решения задач.

Сравнение алгоритмов сортировки
Алгоритм
Метод Шелла
(1,4,13,40,…)
½·(3k – 1)
Число сравнений
Среднее значение –
1,2
N
Метод Шелла Среднее значение –
(1,3,7,15,31…)
1,2
2k – 1
N
Обмен
«пузырьком»
Среднее значение –
N log 2 N
Число перестановок
1, 66 N 1,25
или
0,33 N (ln N )2 1, 26 N ln N
1, 22 N
1,26
0, 29 N (ln N )2 1, 26 N ln N
Среднее значение –
N log 2 N
6

English Русский Rules