Методы сортировки массивов. Сортировка методом «Пузырька»

1. МЕТОДЫ СОРТИРОВКИ МАССИВОВ

СОРТИРОВКА МЕТОДОМ
«ПУЗЫРЬКА»
Кондраткова
Татьяна Алексеевна
ГБОУ Лицей № 82 СПб

2. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
3
2
1
2
12
5
7
4
23
10
1

3. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
3
1
12
2
5
2
7
N
4
23
10
1

4. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
3
1
2
12
5
2
7
N
4
23
10
1

5. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
1
2
12
5
7
4
23
10
1

6. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
I
12
5
7
4
23
10
1

7. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
12
I
5
7
4
23
10
1

8. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
12
I
5
7
N
4
23
10
1

9. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
12
I
5
7
N
4
23
10
1

10. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
5
I
12
7
4
23
10
1

11. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
5
I
K
12
7
4
23
10
1

12. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
5
12
I
7
4
23
10
1

13. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
5
12
I
7
N
4
23
10
1

14. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
5
7
12
I
N
4
23
10
1

15. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
5
7
I
12
4
23
10
1

16. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
5
7
I
K
12
4
23
10
1

17. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
5
7
12
I
4
23
10
1

18. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
5
7
4
12
I
N
23
10
1

19. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
5
4
7
N
12
I
23
10
1

20. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
5
7
4
I
12
23
10
1

21. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
5
7
4
I
K
12
23
10
1

22. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
5
4
7
N
12
I
K
23
10
1

23. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
5
4
7
I
K
N
12
23
10
1

24. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
5
4
7
I
K
12
23
10
1

25. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
5
4
7
I
K
12
23
10
1

26. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
5
4
7
I
K
N
12
23
10
1

27. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
5
4
7
I
K
N
12
23
10
1

28. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
4
5
7
I
K
12
23
10
1

29. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
4
5
7
I
K
12
23
10
1

30. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
4
5
7
12
I
23
10
1

31. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
4
5
7
12
23
I
10
1

32. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
4
5
10
7
N
12
23
I
1

33. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
4
5
10
7
N
23
12
I
1

34. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
4
5
7
12
10
I
23
1

35. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
4
5
7
12
10
I
K
23
1

36. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
4
5
10
7
N
23
12
I
K
1

37. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
4
5
10
7
N
12
I
K
23
1

38. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
4
5
7
10
12
I
K
23
1

39. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
4
5
7
10
12
I
K
23
1

40. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
4
5
7
10
12
23
I
1

41. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
4
5
1
7
N
10
12
23
I

42. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
4
5
1
7
N
10
12
23
I

43. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
4
5
7
10
12
1
I
23

44. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
4
5
7
10
12
1
I
K
23

45. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
4
5
1
7
N
10
12
23
I
K

46. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
4
5
1
7
N
10
12
I
K
23

47. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
4
5
7
10
1
12
I
K
23

48. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
4
5
7
10
1
12
I
K
23

49. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
4
5
1
7
N
10
12
I
K
23

50. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
4
5
1
7
N
10
12
I
K
23

51. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
4
5
7
1
10
12
I
K
23

52. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
4
5
7
1
10
12
I
K
23

53. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
4
5
1
N
7
10
12
I
K
23

54. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
4
5
1
N
7
10
12
I
K
23

55. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
4
5
1
7
10
12
I
K
23

56. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
4
5
1
7
10
12
I
K
23

57. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
4
1
5
N
7
10
12
I
K
23

58. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
4
1
5
N
7
10
12
I
K
23

59. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
4
1
5
7
10
12
I
K
23

60. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
4
1
5
7
10
12
I
K
23

61. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
4
1
5
N
7
10
12
I
K
23

62. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
4
1
5
N
7
10
12
I
K
23

63. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
1
4
5
7
10
12
I
K
23

64. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
3
1
4
5
7
10
12
I
K
23

65. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
4
1
5
N
7
10
12
I
K
23

66. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
4
1
5
N
7
10
12
I
K
23

67. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
1
3
4
5
7
10
12
I
K
23

68. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
2
1
3
4
5
7
10
12
I
K
23

69. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
4
1
5
N
7
10
12
I
K
23

70. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
2
3
4
1
5
N
7
10
12
I
K
23

71. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
1
2
3
4
5
7
10
12
I
K
23

72. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
1
K
2
3
4
5
7
10
12
I
23

73. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
1
2
3
4
5
7
10
12
23
I

74. ПРОДВИЖЕНИЕ ЭЛЕМЕНТОВ

L
N
1
2
3
4
5
7
10
12
23

75. Словесное описание метода Будем сортировать массив по неубыванию значений элементов

П1 Сравнить A[1] и A[2], если элементы стоят не в порядке сортировка, то
поменять их местами (Для обмена используем вспомогательную
переменную L).
П2 Предположим, что часть элементов массива от A[1] до A[I] уже
упорядочена. Элемент A[I] сравнивается с элементом A[I+1].
Если A[I] > A[I+1], то меняем элементы местами и переходим к П3.
Иначе переходим к следующей паре элементов I:=I+1 и повторяем П2
пока I<=N-1 (т.е. пока не сравним два последних элемента массива).
П3 (В П3 мы попадаем потому, что элементы A[I] и
A[I+1] поменялись местами. На
месте I оказался элемент с другим значением. Его надо поставить на своё место в
упорядоченной группе элементов от A[1] до A[I-1]).
Организуем цикл в обратном направлении по переменной K. K:=I.
Если A[K]>=A[K-1], то I:=I+1 и переходим к П2. Иначе меняем
элементы A[K] и A[K-1] местами, и переходим к следующей паре K:=K-1.
П3 повторяем пока не дойдем до начала массива или не перейдём к П2.

76. Описание переменных

program linsort;
TYPE
Описание переменных
{секция описания типов}
MASS=
{заголовок программы, не обязателен}
array [1..30] of integer;
var
{объявляется тип}
{секция описания переменных}
N:1..30;
A: MASS;
I:1..30;
L:integer;
K:0..30;
CS: integer;
CP: integer;
{размер массива }
{массив из N целых чисел}
{переменная цикла }
{переменная для обмена}
{для обратного цикла}
{счётчик числа сравнений}
{счётчик числа перестановок}

77. Порядок работы:

Разработка, отладка и тестирование программы:
Программа должна:
Сформировать массив (ввод данных с клавиатуры);
Вывести массив на экран для просмотра данных;
Произвести сортировку массива по алгоритму метода «Пузырька»;
Вывести массив на экран для просмотра результата.
После того, как Вы убедились, что программа работает правильно
Определить эффективность метода:
Поставить счётчики в программу;
Запустить программу на выполнение;
Снять показания счётчиков на первом входном массиве;
Записать показания счётчиков в бланк лабораторной работы;
Запустить программу и снять показания счётчиков на втором и третьем
входных массивах.
Описать дополнительное рабочее поле ОЗУ в бланке лабораторной
работы.

78. РАЗРАБОТКА АЛГОРИТМА

МЕТОДА «ПУЗЫРЬКА»
(массив целых чисел сортируется по
неубыванию элементов)

79.

Блок формирования массива
НАЧАЛО
Запросить
размер массива
Ввести
размер массива
Цикл для каждого
элемента массива
Запросить
элемент массива
Ввести
элемент массива
1
BEGIN
Write(’ N= ’);
ReadLn(N);
FOR I:=1 TO N DO
begin
Write(’ A[ ’ , I , ’ ]= ’);
ReadLn(A[ I ])
end;

80.

Блок печати массива
1
Пропустить
строку на экране
Цикл для каждого
элемента массива
Вывести
элемент массива
Пропустить
строку на экране
2
WriteLn;
FOR I:=1 TO N DO
Write(A[ I ] , ’ ’);
WriteLn;

81.

АЛГОРИТМ МЕТОДА
«ПУЗЫРЬКА»
2
I:=1 () N-1
K:=I
ДА
A[k]>A[k+1]
AND k<>0
НЕТ
L :=A[K+1]
A[K+1]:=A[K]
A[K] :=L
K:=K-1
3

82.

ОСНОВНАЯ ЧАСТЬ ПРОГРАММЫ
FOR I:=1 TO N-1 DO
BEGIN
K:=I;
DO
WHILE (A[K]>A[K+1]) AND (K<>0)
begin
L:=A[K+1];
A[K+1]:=A[K];
A[K]:=L;
K:=K-1;
end;
END;

83.

После завершения сортировки ещё раз вывести на экран
значения элементов массива, чтобы проверить, что
сортировка прошла успешно.
3
Пропустить
строку на экране
WriteLn;
Цикл для каждого
элемента массива
Вывести
элемент массива
FOR I:=1 TO N DO
Write(A[ I ] , ’ ’);
ReadLn;
END. { конец программы}
Ждать нажатия
ENTER
конец

84.

Куда ставить счётчики?
CS:=0;
CP:=0;
FOR I:=1 TO N-1 DO
BEGIN
K:=I;
Обнулить счётчики
до начала сортировки
CS:=CS+1;
Увеличить на 1
WHILE (A[K]>A[K+1] ) AND (K<>0) DO значение счётчика
begin
числа сравнений
CS:=CS+1;
L:=A[K+1];
A[K+1]:=A[K];
A[K]:=L;
K:=K-1;
CP:=CP+3;
END;
end;
WriteLn(’ CS=’ ,CS);
WriteLn(’ CP=’ ,CP);
Увеличить на 3
значение счётчика
числа перестановок
Вывести на экран
значения счётчиков
после завершения
сортировки

85.

Внимание!
Переменные-счётчики нужны только для
проведения эксперимента.
Они не влияют на алгоритм сортировки и во
время сортировки не задействованы.
Эти переменные не должны учитываться
как дополнительная рабочая память.