Похожие презентации:
Сортировка выбором. Методы сортировки массивов
1. МЕТОДЫ СОРТИРОВКИ МАССИВОВ
СОРТИРОВКА ВЫБОРОМКондраткова
Татьяна Алексеевна
ГБОУ Лицей № 82 СПб
2. Поиск минимального элемента в массиве
K5
I
1
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
N - количество элементов в массиве;
I - переменная цикла;
K - переменная, в которую записывается индекс (номер)
минимального элемента в массиве.
3. Поиск минимального элемента в массиве
5I
1
K
1
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
Индекс первого элемента
записывается в переменную K.
4. Поиск минимального элемента в массиве
51
I
K
1
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
Сравниваются элемент с индексом I (текущий элемент
массива) и элемент с индексом К.
Индекс меньшего по значению элемента
записывается в переменную K.
5. Поиск минимального элемента в массиве
51
I
K
2
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
Сравниваются элемент с индексом I (текущий элемент
массива) и элемент с индексом К.
Индекс меньшего по значению элемента
записывается в переменную K.
6. Поиск минимального элемента в массиве
51
K
2
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
I
Сравниваются элемент с индексом I (текущий элемент
массива) и элемент с индексом К.
Индекс меньшего по значению элемента
записывается в переменную K.
7. Поиск минимального элемента в массиве
51
K
2
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
I
Сравниваются элемент с индексом I (текущий элемент
массива) и элемент с индексом К.
Индекс меньшего по значению элемента
записывается в переменную K.
8. Поиск минимального элемента в массиве
51
K
4
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
I
Сравниваются элемент с индексом I (текущий элемент
массива) и элемент с индексом К.
Индекс меньшего по значению элемента
записывается в переменную K.
9. Поиск минимального элемента в массиве
51
K
4
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
I
Сравниваются элемент с индексом I (текущий элемент
массива) и элемент с индексом К.
Индекс меньшего по значению элемента
записывается в переменную K.
10. Поиск минимального элемента в массиве
51
K
4
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
I
Сравниваются элемент с индексом I (текущий элемент
массива) и элемент с индексом К.
Индекс меньшего по значению элемента
записывается в переменную K.
11. Поиск минимального элемента в массиве
51
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. Поиск минимального элемента в массиве
51
K
6
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
I
Сравниваются элемент с индексом I (текущий элемент
массива) и элемент с индексом К.
Индекс меньшего по значению элемента
записывается в переменную K.
13. Поиск минимального элемента в массиве
51
K
6
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
I
Сравниваются элемент с индексом I (текущий элемент
массива) и элемент с индексом К.
Индекс меньшего по значению элемента
записывается в переменную K.
14. Поиск минимального элемента в массиве
51
K
8
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
I
Сравниваются элемент с индексом I (текущий элемент
массива) и элемент с индексом К.
Индекс меньшего по значению элемента
записывается в переменную K.
15. Поиск минимального элемента в массиве
51
K
8
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
I
Сравниваются элемент с индексом I (текущий элемент
массива) и элемент с индексом К.
Индекс меньшего по значению элемента
записывается в переменную K.
16. Поиск минимального элемента в массиве
51
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.
K5
1
I
J
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
24.
51
J
K
8
N
3
12
2
7
1
23
0
10
2
3
4
5
6
7
8
9
I
25.
01
J
K
8
N
3
12
2
7
1
23
5
10
2
3
4
5
6
7
8
9
I
26.
K0
1
N
3
12
2
7
1
23
5
10
2
3
4
5
6
7
8
9
I
J
27.
01
K
6
N
3
12
2
7
1
23
5
10
2
3
4
5
6
7
8
9
J
I
28.
01
K
6
N
1
12
2
7
3
23
5
10
2
3
4
5
6
7
8
9
J
I
29.
K0
1
N
1
12
2
7
3
23
5
10
2
3
4
5
6
7
8
9
I
J
30.
01
K
4
N
1
12
2
7
3
23
5
10
2
3
4
5
6
7
8
9
J
I
31.
01
K
4
N
1
2
12
7
3
23
5
10
2
3
4
5
6
7
8
9
J
I
32.
K0
1
N
1
2
12
7
3
23
5
10
2
3
4
5
6
7
8
9
I
J
33.
01
K
6
N
1
2
12
7
3
23
5
10
2
3
4
5
6
7
8
9
J
I
34.
01
K
6
N
1
2
3
7
12
23
5
10
2
3
4
5
6
7
8
9
J
I
35.
K0
1
N
1
2
3
7
12
23
5
10
2
3
4
5
6
7
8
9
I
J
36.
01
K
8
N
1
2
3
7
12
23
5
10
2
3
4
5
6
7
8
9
J
I
37.
01
K
8
N
1
2
3
5
12
23
7
10
2
3
4
5
6
7
8
9
J
I
38.
K0
1
N
1
2
3
5
12
23
7
10
2
3
4
5
6
7
8
9
I
J
39.
01
K
8
N
1
2
3
5
12
23
7
10
2
3
4
5
6
7
8
9
J
I
40.
01
K
8
N
1
2
3
5
7
23
12
10
2
3
4
5
6
7
8
9
J
I
41.
K0
1
N
1
2
3
5
7
23
12
10
2
3
4
5
6
7
8
9
I
J
42.
01
K
9
N
1
2
3
5
7
23
12
10
2
3
4
5
6
7
8
9
J
I
43.
01
K
9
N
1
2
3
5
7
10
12
23
2
3
4
5
6
7
8
9
J
I
44.
K0
1
N
1
2
3
5
7
10
12
23
2
3
4
5
6
7
8
9
I
J
45.
01
K
8
N
1
2
3
5
7
10
12
23
2
3
4
5
6
7
8
9
I
J
Если K=J, то обмен не нужно делать.
46.
K0
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.
Блок формирования массиваНАЧАЛО
Запросить
размер массива
Ввести
размер массива
Цикл для каждого
элемента массива
Запросить
элемент массива
Ввести
элемент массива
1
BEGIN
Write(’ N= ’);
ReadLn(N);
FOR I:=1 TO N DO
begin
Write(’ A[ ’ , I , ’ ]= ’);
ReadLn(A[ I ])
end;
49.
Блок печати массива1
Пропустить
строку на экране
Цикл для каждого
элемента массива
Вывести
элемент массива
Пропустить
строку на экране
2
WriteLn;
FOR I:=1 TO N DO
Write(A[ I ] , ’ ’);
WriteLn;
50.
2J:=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.
Внимание!Переменные-счётчики нужны только для
проведения эксперимента.
Они не влияют на алгоритм сортировки и во
время сортировки не задействованы.
Эти переменные не должны учитываться
как дополнительная рабочая память.