Лабораторная работа. Методы сортировки массивов

Цель: получить практические навыки использования различных алгоритмов сортировки массивов в С++.

 

Общие сведения

Во многих задачах бывает необходимо переставить элементы массива таким образом, чтобы они располагались в порядке возрастания или убывания. Такие массивы называются упорядо­ченными, а процесс их получения — сортировкой.

4.1.1 Сортировка простым выбором.

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

4.1.2 Метод пузырьковой сортировки.

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

Можно уменьшить количество проходов сортировки, выполняя их не (N-1)² раз, а пока массив не будет отсортирован. Определить этот факт достаточно просто: если массив уже отсортирован, то в процессе прохода в нем не происходит никаких перестановок. Перед началом просмотра нужно установить признак отсутствия перестановок (флаг). В случае, если производится хотя бы одна перестановка, флаг изменяет свое значение. Если к моменту завершения прохода значение флага осталось первоначальным, значит, массив отсортирован и дальнейшие проходы не нужны.

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

Задание к лабораторной работе

Решить задачу, соответствующую варианту, выбранному по таблице 4.1. Построить блок-схему программы и организовать ввод данных, если это необходимо, с помощью генератора случайных чисел.

Таблица 4.1 – Варианты заданий

Вариант	Задание
	Дана целочисленная прямоугольная матрица А(8,8). Методом простой сортировки расположить элементы в ее строках по возрастанию.
	Дана целочисленная прямоугольная матрица В(10,10). Методом пузырьковой сортировки без оптимизации расположить элементы в ее столбцах по возрастанию.
	Дана целочисленная матрица К(6,8). Методом пузырьковой сортировки с оптимизацией по времени выполнения каждого прохода расположить элементы по убыванию в столбцах.
	Дана целочисленная матрица В(10,7). Методом пузырьковой сортировки с оптимизацией по времени выполнения каждого прохода расположить элементы по возрастанию в строках.
	Дана целочисленная матрица А(8,7). Переписать все положительные элементы в вектор. Методом пузырьковой сортировки без оптимизации расположить элементы по возрастанию.
	Переписать все положительные элементы матрицы Х(10,10) в вектор Y. Используя метод пузырьковой сортировки с оптимизацией по количеству проходов, расположить по возрастанию.
	Переписать все ненулевые элементы матрицы А(6,5) в вектор В. Используя метод пузырьковой сортировки с оптимизацией по количеству проходов, расположить по убыванию.
	Дана целочисленная прямоугольная матрица С(9,9). Методом простой сортировки расположить элементы в ее столбцах по убыванию.
	Переписать все ненулевые элементы матрицы А(8,5) в вектор В. Используя метод обменной сортировки с признаком завершения, расположить по убыванию.
	Дана целочисленная матрица А(6,9). Переписать все отрицательные элементы в вектор. Методом пузырьковой сортировки без оптимизации расположить элементы по убыванию.
	Дана целочисленная матрица Р(7,5). Методом пузырьковой сортировки с оптимизацией по времени выполнения каждого прохода расположить элементы по убыванию в строках.
	Дана целочисленная матрица А(5,9). Переписать все элементы в вектор по столбцам. Методом пузырьковой сортировки без оптимизации расположить элементы по возрастанию.
	Дана целочисленная матрица С(6,7). Переписать все элементы в вектор по строкам. Методом обменной сортировки с признаком завершения расположить элементы по возрастанию.
	Дана целочисленная матрица Х(6,6). Переписать все элементы в вектор по столбцам. Методом обменной сортировки с признаком завершения расположить элементы по убыванию.
	Дана целочисленная прямоугольная матрица А(10,10). Методом простой сортировки расположить элементы в ее столбцах по возрастанию.

 

4.3 Контрольные вопросы

4.3.1 Перечислите известные Вам методы сортировки.

4.3.2 В чем заключается суть метода сортировки простым выбором?

4.3.3 Приведите блок-схему метода сортировки простым выбором.

4.3.4 Перечислите отличительные особенности метода пузырьковой сортировки?

4.3.5 В чем смысл оптимизации метода пузырьковой сортировки?

4.3.6 Как можно уменьшить количество проходов сортировки при использовании метода пузырьковой сортировки?

4.3.7 С какой целью используется признак отсутствия перестановок при оптимизации метода пузырьковой сортировки?

4.3.8 В чем заключается суть оптимизации метода пузырьковой сортировки по времени выполнения каждого прохода?

4.3.9 Приведите блок-схему алгоритма оптимизации метода пузырьковой сортировки по времени выполнения каждого прохода.

4.3.10 Приведите пример алгоритма обменной сортировки с признаком завершения.

 

Лабораторная работа. Обработка символьных данных

Цель: получить практические навыки обработки символьной информации – строк.

 

Общие сведения

Строка представляет собой массив значений типа char, завершающийся нулевым байтом ‘\0’, что следует учитывать при объявлении строки, т.е. указывать не N, а N+1 элемент. При инициализации строк используются традиционные методы объявления.

Для определения константы, равной длине инициализированной строковой переменной, можно воспользоваться функцией sizeof().

Для ввода символьных переменных и строк в C предназначены функции scanf() (ввод до первого пробельного символа) или gets() из библиотеки <stdio.h>. С++ дополнительно предоставляет пользователю две функции cin,get и cin.getline из библиотеки <iostream.h>. Для вывода в этих же библиотеках существуют аналогичные функции.

При работе со строками чаще всего используются функции библиотеки <string.h>, в частности:

а) склеивание – последовательное объединение нескольких строк:

strcat (str1, str2);

б) копирование строк:

strcpy(str1, str2);

в) сравнение строк:

strcmp(str1,str2);

г) длина строки:

lenth=strlen(str1);

д) преобразование строчных символов в прописные:

strlwr(str1);

е) преобразование прописных символов в строчные:

strupr(str1);

ж) заполнение строки некоторым символом:

strset(str1, ’символ’);

и) получить код символа:

n=int(a);

Задания к лабораторной работе

Решить задачу, соответствующую варианту, выбранному по таблице 5.1. Построить блок-схему программы и организовать ввод данных пользователем.

 

Таблица 5.1 – Варианты заданий

Вариант	Задание
	Удвоить в строке s каждое вхождение буквы Z.
	Заменить в строке s каждую первую букву слов, начинающихся с гласной буквы на прописную.
	Определяет, сколько во введенной строке s слов, состоящих не более чем из четырех букв.
	Вывести на экран введенное предложение, меняя местами каждые два соседних слова.
	Вывести на экран все слова предложения, начинающиеся с гласных букв.
	Из строки удалить среднюю букву, если длина строки нечетная, иначе – удалить две средние буквы. Средней считается буква, размещенная строго по центру строки.
	Определить позицию начала в строке s слова с номером n.
	Определить длину слова с номером n в строке s.
	Подсчитать количество букв в слове с номером n строки s.
	Вывести предложение на экран, записав все его слова в обратном порядке.
	Заменить в строке s все вхождения подстроки str1 на подстроку str2.
	Удалить из строки s подстроку s1, начиная с позиции n, длиной l.
	Вставить в строку s подстроку s1, начиная с позиции n.
	Подсчитать количество слов в строке s.
	Скопировать подстроку s в строку s1 n раз.

 

 

5.3 Контрольные вопросы

5.3.1 Что представляет собой строка?

5.3.2 Как объявляются строковые переменные?

5.3.3 Назовите основные особенности строк.

5.3.4 Как можно определить длина инициализированной строковой переменной?

5.3.5 Как осуществляется ввод строк?

5.3.6 Приведите пример ввода строки фиксированной длины с использованием библиотеки <stdio.h>.

5.3.7 Какие функции предлагаются для вывода строк?

5.3.8 Приведите пример построчного ввода символьных данных.

5.3.9 Приведите пример посимвольного ввода строки.

5.3.10 Какие основные функции предусмотрены для работы со строками?