Сортировка одномерного массива Учитель информатики Александрова Т.П.

Устный опрос: Как описать числовой массив в программе? Назовите основные числовые типы. Как описать массив строковых переменных в программе? Как осуществить ввод массива с клавиатуры? Как осуществить ввод массива с помощью оператора случайных чисел?

Понятие «Сортировка» Сортировка – один из наиболее распространенных процессов обработки данных. Сортировкой числового массива называют расположение его элементов в возрастающем или убывающем по величине порядке. Сортировка символьного массива заключается в расположении элементов, например, по алфавиту или по длине строк. Сортировка массивов включена в качестве стандартной операции во многие системы прикладного обеспечения (MS Word, MS Excel и др). Под сортировкой массива подразумевается процесс перестановки элементов с целью упорядочивания их в соответствии с каким-либо критерием. Существует достаточно много методов (алгоритмов) сортировки массивов. Мы рассмотрим два из них: метод прямого выбора и метод обмена (метод пузырька)

Метод прямого выбора Алгоритм сортировки массива по возрастанию методом прямого выбора может быть представлен так: 1.Просматривая массив с первого и до последнего элемента, найти минимальный и поменять его местами с первым элементом. 2.Просматривая массив со второго и до последнего элемента, найти минимальный и поменять его местами со вторым элементом. 3.И, так далее, до последнего элемента.

Пример работы алгоритма: Исходный массив: 8, 3, 6, 1, 4 ( меняются местами 8 и 1) После первого шага: 1, 3, 6, 8, 4 ( меняются местами 3 и 3) После второго шага: 1, 3, 6, 8, 4 (меняются местами 6 и 4) После третьего шага: 1, 3, 4, 8, 6 (меняются местами 8 и 6) После четвертого шага: 1, 3, 4, 6, 8

Метод прямого выбора Program Vibor; const SIZE = 5; var a: array [1..SIZE] of integer; i,j,buf,k: integer; begin for k:=1 to SIZE do read (a [k]); for i:=1 to SIZE -1 do {поиск минимального элемента в части массива от a[i] до a[SIZE]} begin min:= i; for j:= i + 1 to SIZE do if a [j] < a[min] then min:= j; {поменяем местами a [min] и a [i]} buf:= a [i]; a [i]:= a [min]; a [min]:= buf; end; {выведем массив} writeln (Массив отсортирован^); for k:= 1 to SIZE do write (a [k], ); readln; end.

Алгоритм выбора использует вложенные циклы. Внешний цикл (счетчик шагов) последовательно выбирает номер элемента массива, куда следует записывать найденный в неупорядоченной части массива минимальный элемент. Внутренний цикл перебирает номера неупорядоченных элементов при поиске минимального элемента. Для внешнего цикла достаточно шагов на один меньше, чем элементов в массиве.

Метод простого обмена (пузырьковая сортировка) В основе алгоритма лежит обмен соседних элементов массива. Каждый элемент массива, начиная с первого, сравнивается со следующим и, если он больше следующего, то элементы меняются местами. Таким образом, элементы с меньшим значением продвигаются к началу массива, а элементы с большим значением – к концу массива (всплывают), поэтому этот метод иногда называют методом пузырька. Этот процесс повторяется на единицу меньше раз, чем элементов в массиве.

Пример работы алгоритма простого обмена Исходный массив: 8, 3, 6, 4, 1 (последовательно меняются местами 8 и 3,8 и 6, 8 и 4, 8 и 1) После первого шага: 3, 6, 4, 1, 8 (далее последовательно меняются местами 6 и 4, 6 и 1) После второго шага: 3, 4, 1, 6, 8 (последовательно меняются местами 4 и 1) После третьего шага: 3, 1, 4, 6, 8 (последовательно меняются местами 3 и 1) После четвертого шага: 1, 3, 4, 6, 8

Program Obmen; const SIZE=5 var a: array [1..SIZE] of integer; i,k, buf: integer; begin write (Введите,SIZE: 3,целых в одной строке через пробел); for k:= 1 to SIZE do read (a [k]); for i:= 1 to SIZE - 1do for k:= 1 to SIZE – i do if a [k] > a [k + 1] then begin {обменяем k-й и (k + 1)-й элементы} buf:= a [k]; a [k]:= a [k + 1]; a [k + 1]:= buf; end; writeln (Массив отсортирован.); for k:= 1 to SIZE do write (a [k], ); readln; end. Метод обмена

Практическая часть Задача1. На соревнованиях по прыжкам в длину получен массив результатов b(n). Определить три лучших результата. Массив сформировать с помощью функции RANDOM. Задача2. Составить программу, которая выполняет сортировку фамилий в исходном массиве по алфавиту.

Успехов Вам!