Учебно-методическии комплекс дисциплины «Структуры и алгоритм обработки данных» (стр. 15 )

Для этого необходимо выполнить следующую последовательность действий:

1. Определить минимальный элемент массива;

2. Поменять его местами с первым элементом;

3. Определить минимальный элемент среди оставшихся;

4. Поменять его местами со вторым элементом и т. д.;

Эта последовательность действий должна выполняться до тех пор, пока не будет определён последний минимальный элемент.

Всю операцию по упорядочиванию массива можно разбить на более простые задачи.

Первая - поиск минимального элемента. Предлагаемый фрагмент программы напомнит Вам, как это делается.

min:=m[1]; {допустим, что 1-й элемент - минимален}

t:=1; {и его номер = 1}

FOR i:=1 TO 30 DO

if m[i]><m[t] then t:=j; {условие для определение минимума}

buf:=m[t]; {замена}

m[t]:=m[i];

m[i]:=buf;

END;

Описанный метод сортировки массивов можно применять как для сортировки массивов по возрастанию, так и для сортировки массивов по убыванию. Для этого просто необходимо определять не минимальный элемент массива, а максимальный. В тексте программы это выражается заменой в некоторых местах знака "<" на знак ">".

Алгоритм пузырьковой сортировки

Алгоритм так называемой "пузырьковой" сортировки более оригинален и в большинстве случаев более эффективен. При использовании этого алгоритма весь массив просматривается несколько раз подряд. При каждом таком просмотре сравниваются последовательно только соседние элементы массива: сначала первый со вторым, потом второй с третьим, и в конце предпоследний с последним. Если при сравнении окажется, что предыдущий элемент больше следующего, они меняются местами описанным выше способом. Так в результате одного последовательного просмотра элементы, значение которых больше, "всплывают" образно говоря на поверхность, т. е. ближе к концу массива. Если провести такой последовательный просмотр массива несколько раз, то "тяжёлые" элементы окончательно "всплывут" и массив окажется отсортированным. Остаётся нерешённым ещё один вопрос. Сколько раз необходимо выполнять такой просмотр? Ведь может оказаться, что и одного просмотра будет достаточно. Столько, сколько нужно для полной сортировки, т. е. пока при просмотре элементы не будут меняться местами. Для этого удобно организовать логическую переменную ind, и присваивать ей значение ложь в случае, если замена происходила хотя бы один раз. Если значением этой переменной останется истина, то просмотры необходимо прекратить.

НЕ нашли? Не то? Что вы ищете?

Предлагаемый Вам ниже фрагмент программы реализован на основе метода пузырьковой сортировки. Он выполняет полную сортировку массива состоящего из 40 элементов.

REPEAT

ind:=true; {предположим, что массив уже отсортирован}

FOR i:=1 TO 39 DO {цикл для организации просмотра}

if m[i]>m[i+1] then {сравнение двух соседних элементов}

begin

buf:=m[i]; {меняем соседние элементы местами}

m[i]:=m[i+1];

m[i+1]:=buf;

ind:=false; {как оказалось, массив неотсортирован}

end;

UNTIL ind; {выполняем просмотры пока ind=false}

Задания для самостоятельного выполнения

1. Организуйте массив, содержащий 20 различных целых чисел. После этого элементы массива упорядочиваются по убыванию и содержимое отсортированного массива выводится на экран.

2. Организуйте массив, содержащий 20 различных целых чисел. После этого 10 первых элементов массива упорядочиваются по возрастанию, а 10 последних элементов по убыванию. Содержимое отсортированного таким образом массива выводится на экран.

3. Организуйте массив, содержащий 15 различных целых чисел. После этого отдельно первых 5 элементов, вторых 5 элементов и последних 5 элементов сортируются по возрастанию. Содержимое отсортированного таким образом массива выводится на экран.

4. Создайте массив, содержащий 10 различных целых чисел. Содержимое массива сортируется по возрастанию, и после этого определяются минимальный и максимальный элементы массива.

5. Организуйте массив, содержащий 20 различных символов. Отсортируйте его по возрастанию.

6. Организуйте массив содержащий 20 целых чисел. Отсортируйте отдельно элементы с чётными индексами по возрастанию, и элементы с нечётными индексами по убыванию.

7. Создайте массив содержащий 20 целых чисел. Отсортируйте его по возрастанию. После этого определите и выведите на экран сумму элементов с чётными индексами и сумму элементов с нечётными индексами.

8. Создайте массив, содержащий 15 целых чисел. Отдельно первых 5 элементов массива, вторых 5 элементов и последних 5 элементов отсортируйте по убыванию. Определите и выведите на экран сумму каждой пятёрки отсортированного таким образом массива.

9. Создайте массив, содержащий 15 различных символов. Отсортируйте его по убыванию. После этого определите и выведите на экран "наименьший" и "наибольший" символы.

10. Создайте массив, содержащий 10 различных символов. Первую половину массива отсортируйте по возрастанию, а вторую по убыванию. Отсортированный массив выведите на экран.

11. Создайте массив А, содержащий 8 различных символов. Отсортируйте его по возрастанию. Организуйте и выведите на экран целочисленный массив В, заполнив его числами, полученными преобразованием символов массива А в целые числа.

12. Создайте целочисленный массив А, содержащий 10 различных чисел. Отсортируйте первую половину массива А по возрастанию, а вторую по убыванию. Организуйте и выведите на экран символьный массив В, заполнив его символами, полученными преобразованием чисел массива А в символы.

13. Создайте массив, содержащий 20 различных целых чисел. Отсортируйте его по возрастанию. После этого замените все элементы массива на противоположные и выведите содержимое обработанного массива на экран.

14. Создайте массив, содержащий 20 различных целых чисел. Отсортируйте первую половину массива по возрастанию, а вторую по убыванию. Все чётные элементы массива увеличить в три раза, а нечётные в 2 раза. Содержимое обработанного таким образом массива вывести на экран.

САМОСТОЯТЕЛЬНАЯ РАБОТА СТУДЕНТА

СРСП № 1

Тема: Задачи сортировки. Алгоритмы сортировки: пузырьковая сортировка.

Цель: Создание программы и ее компиляция