Сортировка элементов массива Практическая работа №4
Выучить § 2. 2.6 (стр. 80-82), выполнить № 8 стр. 85 Домашнее задание
Сортировка Сортировка – это перестановка элементов массива в заданном порядке (по возрастанию, убыванию, другим условиям). Задача: переставить элементы массива в порядке возрастания. Методы (их много) : метод пузырька метод выбора метод вставки
Метод выбора Идея: найти минимальный элемент и поставить на первое место (поменять местами с A[1] ) из оставшихся найти минимальный элемент и поставить на второе место (поменять местами с A[ 2 ] ), и т.д. 4 3 1 2 1 3 4 2 1 2 4 3 1 2 3 4
Этот приём основан на следующих принципах: 1. Выбираем элемент с наименьшим ключом. 2. Он меняется местами с первым элементом а [1]. 3. Затем этот процесс повторяется с оставшимися N-1 элементами, N-2 элементами и т.д. до тех пор, пока не останется один самый большой элемент. Алгоритм формулируется следующим образом: для k от 1 до N-1 нц найти nmin – индекс наименьшего из a[k],…a[N]; поменять местами a[nmin] и a[k] кц ; 44 55 12 42 94 18 06 67 06 55 12 42 94 18 44 67 06 12 55 42 94 18 44 67 06 12 18 42 94 55 44 67 06 12 18 42 94 55 44 67 06 12 18 42 44 55 94 67 06 12 18 42 44 55 94 67 06 12 18 42 44 55 67 94 Метод выбора
Метод выбора нужно N-1 раз поиск минимального от A[k] до A[N] переставляем for k:=1 to N-1 do begin nMin=k; for i:=k+1 to N do if A[i]<A[nMin] then nMin:=i; c:=A[k]; A[k]:=A[nMin]; A[nMin]:=c; end;
{ Процесс сортировки } for k:=1 to N-1 do begin nMin=k; for i:=k+1 to N do if A[i]<A[nMin] then nMin:=i; c:=A[ k ]; A[ k ]:=A[nMin]; A[nMin]:=c; end; { Отсортировано } Метод выбора – фрагмент программы
Задание Создать в личной папке файл sort. pas Составить программу, которая заданные числа вводит в массив и сортирует массив по неубыванию. Протестировать при учителе программу. Сохранить исходный текст программы.
Начало Конец Сортировка массива Ввод массива Вывод массива Укрупнённый алгоритм
Ввод массива с клавиатуры ( вспомним) Описан массив var a:array[1.. 50 ] of integer; write(' Количество чисел? ' ) ; readln(N); for i:=1 to N do begin write('a[', i, ']='); readln( a[i] ) end; Количество чисел? 5 a[1] = a[2] = a[3] = a[4] = a[5] = 7 12 34 56 13 Почему write ? ? Цель : Ввести в массив N чисел
Вывод массива на экран var a: array[1..50] of integer; for i:=1 to N do writeln ('a[',i,']=',a[i]); a[1]= 3 5 a[2]=144 a[3]=1316 a[4]=3466 a[5]=169 Почему writeln ? ? Можно в строку через пробел (2 вариант) Массив A: 3 5 144 1316 3466 169 writeln (' Массив A:'); for i:=1 to N do write(a[i], ' ' ); Почему write ? ? Имеем: Описан массив. Значения N и элементам присвоены. Цель: Вывести N элементов массива на экран
