Слайд 1Сортировка элементов линейного массива
Презентация 9-19
Слайд 2Заполнение массива
Функция y = RND(1) генерирует случайное число из интервала (0,1)
RND(1)*10- случайное
число из интервала (0,10)
INT(RND(1)*100) – случайное целое число из интервала
(0,100)
INT(RND(1)*50+80) – случайное целое число из интервала (80, 130)
RANDOMIZE TIMER– обновление базы случайных чисел
Слайд 3Заполнение массива
Заполнение массива произвольными целыми числами из промежутка (0; 100)
RANDOMIZE
TIMER
INPUT “Количество элементов”; K
DIM A(K)
FOR I=1 TO K
A(I)=INT(RND(1)*100)
PRINT “A(”; I;
“)=”; A(I)
NEXT I
Слайд 4Сортировка элементов массива
Сортировка – один из наиболее распространенных процессов обработки данных.
Сортировкой
числового массива называют расположение его элементов в возрастающем или убывающем по
величине порядке.
Слайд 5Сортировка элементов массива
Под сортировкой массива подразумевается процесс перестановки элементов с целью
упорядочивания их в соответствии с каким-либо критерием.
Существует достаточно много методов
(алгоритмов) сортировки массивов. Рассмотрим метод прямого выбора.
Слайд 6Метод прямого выбора
Алгоритм сортировки массива по возрастанию методом прямого выбора
может быть представлен так:
Просматривая массив с первого элемента, найти
минимальный и поменять его местами с первым элементом.
Просматривая массив со второго элемента, найти минимальный и поменять его местами со вторым элементом.
И, так далее, до последнего элемента.
Слайд 7Метод прямого выбора
Алгоритм использует вложенные циклы.
Внешний цикл (счетчик шагов)
последовательно выбирает номер элемента массива, куда следует записывать найденный в
неупорядоченной части массива минимальный элемент.
Внутренний цикл перебирает номера неупорядоченных элементов при поиске минимального элемента.
Для внешнего цикла достаточно шагов на один меньше, чем элементов в массиве.
Слайд 8Метод прямого выбора
Фрагмент программы, реализующий сортировку массива по возрастанию методом
прямого выбора
For i =1 To n–1
For j = i+1
To n
If a(i) > a(j) Then Swap a(i), a(j)
Next j
Next i
Слайд 9Метод прямого выбора
Пример работы алгоритма:
Исходный массив: 8, 3, 6, 1,
4 (последовательно меняются местами 8 и 3, 3 и 1)
После
первого шага: 1, 8, 6, 3, 4 (меняются местами 8 и 6, 6 и 3)
После второго шага: 1, 3, 8, 6, 4 (меняются местами 8 и 6, 6 и 4)
После третьего шага: 1, 3, 4, 8, 6 (меняются местами 8 и 6)
После четвертого шага: 1, 3, 4, 6, 8
Слайд 10Задачи
1. Составить программу сортировки числового массива по убыванию методом «пузырька».
Массив задать случайными числами в интервале от 0 до 100.
2.
На соревнованиях по прыжкам в длину получен массив b(n). Определить три лучших результата. Массив сформировать с помощью функции RND (диапазон прыжков от 120см до 200см).
