Лабораторная рбота №7
Лабораторная работа №7
Задачи на сортировку одномерных массивов
Теоретические сведения
Сортировка — это процесс упорядочивания элементов массива по возрастанию или убыванию. Основные методы сортировки:
· Метод пузырька
· Метод выбора
· Метод вставок
· Быстрая сортировка
· Сортировка слиянием
Задание 1: Сортировка методом пузырька.
Напишите программу, которая сортирует одномерный массив методом пузырька. Введите массив из 10 элементов и выведите его в отсортированном виде.
Цель: освоить сортировку методом пузырька.
Принцип работы
1. Сравниваются два соседних элемента
2. Если они стоят в неправильном порядке — меняются местами
3. Процесс повторяется до полной сортировки массива
Алгоритм сортировки
1. Проход по массиву от начала до конца
2. Сравнение каждой пары соседних элементов
3. Обмен элементов, если они стоят в неправильном порядке
4. Повторение процесса до полной сортировки
Пример реализации
pascal
program BubbleSort;
const
SIZE = 10; // Размер массива
var
arr: array[1..SIZE] of Integer; // Массив для сортировки
i, j, temp: Integer; // Вспомогательные переменные
begin
// Ввод элементов массива
writeln('Введите ', SIZE, ' элементов массива:');
for i := 1 to SIZE do
begin
write('Элемент ', i, ': ');
readln(arr[i]);
end;
// Вывод исходного массива
writeln('Исходный массив:');
for i := 1 to SIZE do
write(arr[i]:4);
writeln;
// Сортировка методом пузырька
for i := 1 to SIZE - 1 do
begin
for j := 1 to SIZE - i do
begin
if arr[j] > arr[j + 1] then
begin
// Обмен элементов
temp := arr[j];
arr[j] := arr[j + 1];
arr[j + 1] := temp;
end;
end;
end;
// Вывод отсортированного массива
writeln('Отсортированный массив:');
for i := 1 to SIZE do
write(arr[i]:4);
writeln;
end.
Пояснение работы программы
1. Ввод данных:
· Пользователь вводит 10 элементов массива
· Значения сохраняются в массив arr
2. Сортировка:
· Внешний цикл выполняется SIZE-1 раз
· Внутренний цикл сравнивает соседние элементы
· При необходимости происходит обмен элементов
3. Вывод результатов:
· Отображается исходный массив
· Отображается отсортированный массив
Пример работы программы
Введите 10 элементов массива:
Элемент 1: 5
Элемент 2: 2
Элемент 3: 9
Элемент 4: 1
Элемент 5: 5
Элемент 6: 6
Элемент 7: 3
Элемент 8: 8
Элемент 9: 7
Элемент 10: 4
Исходный массив:
5 2 9 1 5 6 3 8 7 4
Отсортированный массив:
1 2 3 4 5 5 6 7 8 9
Оптимизации алгоритма
1. Можно добавить флаг, показывающий, был ли обмен элементов
2. Если обменов не было — массив уже отсортирован
3. Можно прекратить сортировку раньше
Практические задания
1. Модифицировать программу для сортировки по убыванию
2. Добавить подсчет количества обменов
3. Реализовать оптимизированную версию с флагом
4. Создать функцию для сортировки массива
1. Сравнить соседние элементы
2. При нарушении порядка поменять их местами
3. Повторять до полной сортировки
Задание 2: Сортировка выбором.
Создайте программу, которая сортирует массив методом выбора. Введите массив из 15 элементов и выведите его в порядке возрастания.
Теоретические сведения
Сортировка выбором — это алгоритм сортировки, который находит минимальный элемент в неотсортированной части массива и перемещает его в начало.
Принцип работы
1. На каждом шаге находится минимальный элемент
2. Минимальный элемент меняется местами с первым элементом текущей части
3. Процесс повторяется для оставшейся части массива
Алгоритм сортировки
1. Проход по массиву от начала до конца
2. Поиск минимального элемента в неотсортированной части
3. Обмен найденного элемента с первым элементом текущей части
4. Повторение процесса для оставшейся части
Пример реализации
pascal
program SelectionSort;
const
SIZE = 15; // Размер массива
var
arr: array[1..SIZE] of Integer; // Массив для сортировки
i, j, minIndex, temp: Integer; // Вспомогательные переменные
begin
// Ввод элементов массива
writeln('Введите ', SIZE, ' элементов массива:');
for i := 1 to SIZE do
begin
write('Элемент ', i, ': ');
readln(arri);
end;
// Вывод исходного массива
writeln('Исходный массив:');
for i := 1 to SIZE do
write(arri:4);
writeln;
// Сортировка методом выбора
for i := 1 to SIZE - 1 do
begin
// Предполагаем, что первый элемент — минимальный
minIndex := i;
// Поиск минимального элемента
for j := i + 1 to SIZE do
begin
if arrj < arr[minIndex] then
minIndex := j;
end;
// Обмен элементов
if minIndex <> i then
begin
temp := arri;
arri := arr[minIndex];
arr[minIndex] := temp;
end;
end;
// Вывод отсортированного массива
writeln('Отсортированный массив:');
for i := 1 to SIZE do
write(arri:4);
writeln;
end.
Пояснение работы программы
1. Ввод данных:
· Пользователь вводит 15 элементов массива
· Значения сохраняются в массив arr
2. Сортировка:
· Внешний цикл проходит по всем элементам, кроме последнего
· Внутренний цикл ищет минимальный элемент в неотсортированной части
· Найденный минимальный элемент меняется местами с первым элементом текущей части
3. Вывод результатов:
· Отображается исходный массив
· Отображается отсортированный массив
Пример работы программы
Введите 15 элементов массива:
Элемент 1: 45
Элемент 2: 23
Элемент 3: 12
Элемент 4: 89
Элемент 5: 34
Элемент 6: 67
Элемент 7: 29
Элемент 8: 1
Элемент 9: 56
Элемент 10: 78
Элемент 11: 32
Элемент 12: 90
Элемент 13: 43
Элемент 14: 21
Элемент 15: 65
Исходный массив:
45 23 12 89 34 67 29 1 56 78 32 90 43 21 65
Отсортированный массив:
1 12 21 23 29 32 34 43 45 56 65 67 78 89 90
Особенности метода
· Устойчивость: метод неустойчив
· Сложность: O(n²) в худшем и среднем случае
· Память: требует O(1) дополнительной памяти
Практические задания
1. Модифицировать программу для сортировки по убыванию
2. Добавить подсчет количества обменов
3. Реализовать сортировку в виде отдельной функции
4. Сравнить эффективность с методом пузырька на разных размерах массива
Задание 3: Сортировка вставками.
Напишите алгоритм сортировки вставками. Введите массив из 20 элементов и отсортируйте его по убыванию.
Цель: освоить сортировку методом вставок.
Теоретические сведения
Сортировка вставками — это алгоритм сортировки, который строит отсортированную последовательность путём вставки каждого следующего элемента в уже отсортированную часть массива.
Принцип работы
1. Первый элемент считается отсортированным
2. Каждый следующий элемент вставляется на правильное место
3. Процесс повторяется до полной сортировки массива
Алгоритм сортировки
1. Проход по массиву от второго элемента
2. Сохранение текущего элемента
3. Поиск места для вставки
4. Сдвиг элементов для создания свободного места
5. Вставка элемента на найденное место
Пример реализации
pascal
program InsertionSort;
const
SIZE = 20; // Размер массива
var
arr: array[1..SIZE] of Integer; // Массив для сортировки
i, j, current, temp: Integer; // Вспомогательные переменные
begin
// Ввод элементов массива
writeln('Введите ', SIZE, ' элементов массива:');
for i := 1 to SIZE do
begin
write('Элемент ', i, ': ');
readln(arri);
end;
// Вывод исходного массива
writeln('Исходный массив:');
for i := 1 to SIZE do
write(arri:5);
writeln;
// Сортировка методом вставок (по убыванию)
for i := 2 to SIZE do
begin
current := arri;
j := i - 1;
// Сдвиг элементов для поиска места вставки
while (j >= 1) and (arr[j] < current) do
begin
arr[j + 1] := arr[j];
j := j - 1;
end;
// Вставка элемента
arr[j + 1] := current;
end;
// Вывод отсортированного массива
writeln('Отсортированный массив (по убыванию):');
for i := 1 to SIZE do
write(arri:5);
writeln;
end.
Пояснение работы программы
1. Ввод данных:
· Пользователь вводит 20 элементов массива
· Значения сохраняются в массив arr
2. Сортировка:
· Первый элемент считается отсортированным
· Для каждого следующего элемента:
o Сохраняется текущий элемент
o Находится правильное место в отсортированной части
o Происходит сдвиг элементов
o Вставляется элемент на найденное место
3. Вывод результатов:
· Отображается исходный массив
· Отображается отсортированный массив по убыванию
Пример работы программы
Введите 20 элементов массива:
Элемент 1: 45
Элемент 2: 23
Элемент 3: 12
Элемент 4: 89
Элемент 5: 34
Элемент 6: 67
Элемент 7: 29
Элемент 8: 1
Элемент 9: 56
Элемент 10: 78
Элемент 11: 32
Элемент 12: 90
Элемент 13: 43
Элемент 14: 21
Элемент 15: 65
Элемент 16: 88
Элемент 17: 77
Элемент 18: 66
Элемент 19: 55
Элемент 20: 44
Исходный массив:
45 23 12 89 34 67 29 1 56 78 32 90 43 21 65 88 77 66 55 44
Отсортированный массив (по убыванию):
90 89 88 78 77 67 66 65 56 55 45 44 43 34 32 29 23 21 12 1
Особенности метода
· Устойчивость: метод устойчив
· Сложность: O(n²) в худшем и среднем случае
· Память: требует O(1) дополнительной памяти
· Эффективность: хорошо работает на почти отсортированных массивах
Практические задания
1. Модифицировать программу для сортировки по возрастанию
2. Добавить подсчет количества сравнений и обменов
3. Реализовать сортировку в виде отдельной функции
4. Сравнить эффективность с другими методами сортировки
5. Оптимизировать алгоритм для случая почти отсортированного массива
Задание 4: Сортировка четных и нечетных элементов.
Создайте программу, которая разделяет массив на четные и нечетные элементы, сортируя их отдельно. Введите массив из 12 элементов и выведите два отсортированных массива.
Теоретические сведения
Разделение массива — это процесс разбиения исходного массива на две группы по определенному критерию (в данном случае — четность элементов).
Принцип работы
1. Проход по исходному массиву
2. Разделение элементов на четные и нечетные
3. Сортировка каждой группы отдельно
4. Вывод результатов
Алгоритм решения
1. Создать два вспомогательных массива
2. Разделить элементы по четности
3. Отсортировать каждый массив
4. Вывести результаты
Пример реализации
pascal
program SortEvenOdd;
const
SIZE = 12; // Размер исходного массива
var
arr: array[1..SIZE] of Integer; // Исходный массив
even: array[1..SIZE] of Integer; // Массив для четных
odd: array[1..SIZE] of Integer; // Массив для нечетных
i, j, k, temp: Integer;
evenCount, oddCount: Integer;
begin
// Ввод элементов массива
writeln('Введите ', SIZE, ' элементов массива:');
for i := 1 to SIZE do
begin
write('Элемент ', i, ': ');
readln(arri);
end;
// Разделение на четные и нечетные
evenCount := 0;
oddCount := 0;
for i := 1 to SIZE do
begin
if arri mod 2 = 0 then
begin
evenCount := evenCount + 1;
even[evenCount] := arri;
end
else
begin
oddCount := oddCount + 1;
odd[oddCount] := arri;
end;
end;
// Сортировка четных элементов (по возрастанию)
for i := 1 to evenCount - 1 do
for j := 1 to evenCount - i do
if even[j] > even[j + 1] then
begin
temp := even[j];
even[j] := even[j + 1];
even[j + 1] := temp;
end;
// Сортировка нечетных элементов (по возрастанию)
for i := 1 to oddCount - 1 do
for j := 1 to oddCount - i do
if odd[j] > odd[j + 1] then
begin
temp := odd[j];
odd[j] := odd[j + 1];
odd[j + 1] := temp;
end;
// Вывод результатов
writeln('Исходный массив:');
for i := 1 to SIZE do
write(arri:5);
writeln;
writeln('Отсортированные четные элементы:');
for i := 1 to evenCount do
write(even[i]:5);
writeln;
writeln('Отсортированные нечетные элементы:');
for i := 1 to oddCount do
write(odd[i]:5);
writeln;
end.
Пояснение работы программы
1. Ввод данных:
· Пользователь вводит 12 элементов массива
· Значения сохраняются в массив arr
2. Разделение элементов:
· Создаются два вспомогательных массива
· Элементы разделяются по четности
· Подсчитывается количество четных и нечетных элементов
3. Сортировка:
· Каждый массив сортируется методом пузырька
· Сортировка выполняется по возрастанию
4. Вывод результатов:
· Отображается исходный массив
· Отображаются отсортированные четные элементы
· Отображаются отсортированные нечетные элементы
Пример работы программы
Введите 12 элементов массива:
Элемент 1: 5
Элемент 2: 8
Элемент 3: 3
Элемент 4: 12
Элемент 5: 7
Элемент 6: 2
Элемент 7: 9
Элемент 8: 10
Элемент 9: 4
Элемент 10: 6
Элемент 11: 1
Элемент 12: 11
Исходный массив:
5 8 3 12 7 2 9 10 4 6 1 11
Отсортированные четные элементы:
2 4 6 8 10 12
Отсортированные нечетные элементы:
1 3 5 7 9 11
Особенности реализации
· Проверка четности: используется операция mod 2
· Сортировка: применяется простой метод пузырька
· Память: используются дополнительные массивы
Задание 5: Сортировка с использованием указателей.
Напишите программу, которая сортирует массив методом пузырька, используя указатели. Введите массив из 8 элементов и выведите его в отсортированном виде.
Теоретические сведения
Сортировка с указателями — это реализация алгоритма сортировки, где доступ к элементам массива осуществляется через указатели, а не через индексы.
Принцип работы
1. Использование указателей для доступа к элементам
2. Применение алгоритма пузырька
3. Обмен значений через разыменование указателей
Алгоритм решения
1. Создать указатель на начало массива
2. Реализовать алгоритм пузырька через указатели
3. Выполнить сортировку
4. Вывести результат
Пример реализации
pascal
program BubbleSortWithPointers;
const
SIZE = 8; // Размер массива
type
PInteger = ^Integer; // Тип указателя на целое число
var
arr: array1..SIZE of Integer; // Исходный массив
i, j: Integer; // Счетчики
temp: Integer; // Временная переменная для обмена
p1, p2: PInteger; // Указатели
begin
// Ввод элементов массива
writeln('Введите ', SIZE, ' элементов массива:');
for i := 1 to SIZE do
begin
write('Элемент ', i, ': ');
readln(arri);
end;
// Вывод исходного массива
writeln('Исходный массив:');
for i := 1 to SIZE do
write(arri:5);
writeln;
// Сортировка методом пузырька через указатели
p1 := @arr1; // Указатель на первый элемент
for i := 1 to SIZE - 1 do
begin
p1 := @arr1; // Возвращаем указатель в начало
for j := 1 to SIZE - i do
begin
p2 := p1 + SizeOf(Integer); // Следующий элемент
if p1^ > p2^ then
begin
// Обмен значений через указатели
temp := p1^;
p1^ := p2^;
p2^ := temp;
end;
p1 := p1 + SizeOf(Integer); // Переходим к следующему элементу
end;
end;
// Вывод отсортированного массива
writeln('Отсортированный массив:');
for i := 1 to SIZE do
write(arri:5);
writeln;
end.
Пояснение работы программы
1. Ввод данных:
· Пользователь вводит 8 элементов массива
· Значения сохраняются в массив arr
2. Сортировка:
· Создаются два указателя (p1 и p2)
· p1 указывает на текущий элемент
· p2 указывает на следующий элемент
· Происходит сравнение и обмен значений через разыменование указателей
3. Вывод результатов:
· Отображается исходный массив
· Отображается отсортированный массив
Пример работы программы
Введите 8 элементов массива:
Элемент 1: 45
Элемент 2: 23
Элемент 3: 12
Элемент 4: 89
Элемент 5: 34
Элемент 6: 67
Элемент 7: 29
Элемент 8: 1
Исходный массив:
45 23 12 89 34 67 29 1
Отсортированный массив:
1 12 23 29 34 45 67 89
Особенности реализации
· Работа с памятью: прямое обращение к памяти через указатели
· Эффективность: аналогична обычной реализации пузырька
· Безопасность: требуется аккуратное управление указателями
Практические задания
1. Модифицировать программу для сортировки по убыванию
2. Добавить подсчет количества обменов
3. Реализовать оптимизированную версию с флагом
4. Создать функцию для сортировки массива через указатели
5. Сравнить производительность с обычной реализацией пузырька