1.47M

Category:

programming

Сортировка выбором. Методы сортировки массивов

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

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

2. Поиск минимального элемента в массиве

K
5
I
1
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
N - количество элементов в массиве;
I - переменная цикла;
K - переменная, в которую записывается индекс (номер)
минимального элемента в массиве.

3. Поиск минимального элемента в массиве

5
I
1
K
1
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
Индекс первого элемента
записывается в переменную K.

4. Поиск минимального элемента в массиве

5
1
I
K
1
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
Сравниваются элемент с индексом I (текущий элемент
массива) и элемент с индексом К.
Индекс меньшего по значению элемента
записывается в переменную K.

5. Поиск минимального элемента в массиве

5
1
I
K
2
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
Сравниваются элемент с индексом I (текущий элемент
массива) и элемент с индексом К.
Индекс меньшего по значению элемента
записывается в переменную K.

6. Поиск минимального элемента в массиве

5
1
K
2
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
I
Сравниваются элемент с индексом I (текущий элемент
массива) и элемент с индексом К.
Индекс меньшего по значению элемента
записывается в переменную K.

7. Поиск минимального элемента в массиве

8. Поиск минимального элемента в массиве

5
1
K
4
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
I
Сравниваются элемент с индексом I (текущий элемент
массива) и элемент с индексом К.
Индекс меньшего по значению элемента
записывается в переменную K.

9. Поиск минимального элемента в массиве

10. Поиск минимального элемента в массиве

11. Поиск минимального элемента в массиве

5
1
K
6
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
I
N-1
Сравниваются элемент с индексом I (текущий элемент
массива) и элемент с индексом К.
Индекс меньшего по значению элемента
записывается в переменную K.

12. Поиск минимального элемента в массиве

5
1
K
6
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
I
Сравниваются элемент с индексом I (текущий элемент
массива) и элемент с индексом К.
Индекс меньшего по значению элемента
записывается в переменную K.

13. Поиск минимального элемента в массиве

14. Поиск минимального элемента в массиве

5
1
K
8
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
I
Сравниваются элемент с индексом I (текущий элемент
массива) и элемент с индексом К.
Индекс меньшего по значению элемента
записывается в переменную K.

15. Поиск минимального элемента в массиве

16. Поиск минимального элемента в массиве

5
1
K
8
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
I
В переменной K записан индекс меньшего
по значению элемента массива.
A[K] – минимальный элемент массива

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

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

18.

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

19.

2
АЛГОРИТМ ПОИСКА
индекса минимального
элемента в массиве
К := 1
I := 2 ( ) N
ДА
A[I]< A[K]
K:=I
Writeln( A[K] )
нет

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

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

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

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

СОРТИРОВКИ МЕТОДОМ ВЫБОРА
(массив целых чисел сортируется по
не убыванию элементов)

23.

K
5
1
I
J
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9

24.

5
1
J
K
8
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
I

25.

0
1
J
K
8
N
3
12
2
7
1
23
5
10
2
3
4
5
6
7
8
9
I

26.

K
0
1
N
3
12
2
7
1
23
5
10
2
3
4
5
6
7
8
9
I
J

27.

0
1
K
6
N
3
12
2
7
1
23
5
10
2
3
4
5
6
7
8
9
J
I

28.

0
1
K
6
N
1
12
2
7
3
23
5
10
2
3
4
5
6
7
8
9
J
I

29.

K
0
1
N
1
12
2
7
3
23
5
10
2
3
4
5
6
7
8
9
I
J

30.

0
1
K
4
N
1
12
2
7
3
23
5
10
2
3
4
5
6
7
8
9
J
I

31.

0
1
K
4
N
1
2
12
7
3
23
5
10
2
3
4
5
6
7
8
9
J
I

32.

K
0
1
N
1
2
12
7
3
23
5
10
2
3
4
5
6
7
8
9
I
J

33.

0
1
K
6
N
1
2
12
7
3
23
5
10
2
3
4
5
6
7
8
9
J
I

34.

0
1
K
6
N
1
2
3
7
12
23
5
10
2
3
4
5
6
7
8
9
J
I

35.

K
0
1
N
1
2
3
7
12
23
5
10
2
3
4
5
6
7
8
9
I
J

36.

0
1
K
8
N
1
2
3
7
12
23
5
10
2
3
4
5
6
7
8
9
J
I

37.

0
1
K
8
N
1
2
3
5
12
23
7
10
2
3
4
5
6
7
8
9
J
I

38.

K
0
1
N
1
2
3
5
12
23
7
10
2
3
4
5
6
7
8
9
I
J

39.

0
1
K
8
N
1
2
3
5
12
23
7
10
2
3
4
5
6
7
8
9
J
I

40.

0
1
K
8
N
1
2
3
5
7
23
12
10
2
3
4
5
6
7
8
9
J
I

41.

K
0
1
N
1
2
3
5
7
23
12
10
2
3
4
5
6
7
8
9
I
J

42.

0
1
K
9
N
1
2
3
5
7
23
12
10
2
3
4
5
6
7
8
9
J
I

43.

0
1
K
9
N
1
2
3
5
7
10
12
23
2
3
4
5
6
7
8
9
J
I

44.

K
0
1
N
1
2
3
5
7
10
12
23
2
3
4
5
6
7
8
9
I
J

45.

0
1
K
8
N
1
2
3
5
7
10
12
23
2
3
4
5
6
7
8
9
I
J
Если K=J, то обмен не нужно делать.

46.

K
0
1
N
1
2
3
5
7
10
12
23
2
3
4
5
6
7
8
9
J
Процесс сортировки завершен за N-1 цикл по переменной
J.

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

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

48.

49.

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

50.

2
J:=1 ( )N-1
3
К := j
I :=J+1( ) N
ДА
A[I]< A[K]
K:=I
L:=A[K]
A[K]:=A[J]
A[J]:=L
нет

51.

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

52.

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

53.

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

54.

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

English Русский Rules