Лабораторная работа №6 (программирование алгоритмов сортировки массивов)

Содержание

Постановка задания

Задание для всех вариантов звучит так (или, возможно, немного изменено, так как могут быть разные издания учебного пособия):

Задается размер массива $n$ и затем с клавиатуры вводится вещественный массив заданного размера. Решить задачу с применением указателя на массив и функций:
ввода количества элементов и элементов массива с клавиатуры;
построчного вывода элементов массива на экран;
обработки массива в соответствии с заданием.
В главной функции предусмотреть использование указателей на массив для динамического выделения памяти. При обработке заданного массива не разрешается использовать дополнительные массивы.

Варианты заданий

*Вариант*	*Задание*
1.	Упорядочить массив таким образом, чтобы его элементы возрастали по четным номерам и убывали по нечетным.
2.	Упорядочить массив таким образом, чтобы его элементы возрастали до середины и затем до конца убывали.
3.	Переставить элементы массива таким образом, чтобы сначала были расположены отрицательные элементы по возрастанию, затем нули, а после — остальные элементы.
4.	Удалить все отрицательные элементы массива и расположить оставшиеся по убыванию.
5.	Упорядочить элементы массива по возрастанию, удалив все повторяющиеся элементы.
6.	Осуществить циклический сдвиг элементов массива на заданное число $k$, которое может быть положительным и отрицательным. Если $k > 0$, то последние $k$ элементов массива перемещаются на первые $k$ мест.
7.	Удалить из массива наиболее повторяющееся число и отсортировать остальные элементы по возрастанию.
8.	В одномерном массиве найти минимальный элемент среди элементов с нечетными номерами и максимальный элемент среди элементов с четными номерами. Отсортировать по неубыванию элементы массива, расположенные между этими элементами, включая оба числа.
9.	Упорядочить массив таким образом: первым поставить минимальный элемент, вторым — максимальный, затем минимальный из оставшихся элементов и максимальный из оставшихся и т.д.
10.	Вводятся два массива. Получить результирующий отсортированный массив, состоящий из неповторяющихся элементов двух массивов.
11.	Удалить из массива повторяющиеся отрицательные элементы и упорядочить оставшиеся по невозрастанию.
12.	Отсортировать по убыванию элементы массива, находящиеся между первым минимальным и последним максимальными элементами.
13.	Отсортировать по возрастанию элементы массива, находящиеся между первым и последним нулевыми элементами.
14.	Отсортировать по возрастанию элементы массива, находящиеся до минимального элемента.
15.	Отсортировать по убыванию элементы массива, находящиеся после максимального элемента.
16.	Отсортировать элементы массива, находящиеся между первым нулевым и первым максимальным элементами.
17.	Удалить из массива все минимальные элементы, оставшиеся отсортировать по возрастанию.
18.	Удалить из массива все отрицательные элементы, находящиеся между первым и вторым нулевыми элементами, и отсортировать оставшиеся по возрастанию.
19.	Преобразовать массив таким образом, чтобы в первой его половине располагались элементы, стоящие в нечетных позициях, а во второй половине — элементы, стоящие в четных позициях.
20.	Преобразовать массив таким образом, чтобы сначала стояли все минимальные элементы, затем все максимальные элементы, а после них — остальные элементы.
21.	Отсортировать элементы массива, находящиеся между первым минимальным и последним отрицательным максимальным элементами, включая оба числа.
22.	Отсортировать элементы массива, находящиеся между первым максимальным и последним положительным максимальным элементами, включая оба числа.
23.	Отсортировать элементы массива, находящиеся между первым минимальным и последним отрицательным максимальным элементами, включая оба числа.
24.	Отсортировать элементы таким образом, чтобы нечетные элементы были расположены по возрастанию, а четные элементы — по убыванию.
25.	Отсортировать элементы массива таким образом, чтобы положительные элементы были расположены по возрастанию, отрицательные элементы — по убыванию, а нулевые остались на своих местах.

Лабораторная работа $№6$ предполагает написание программы на языке Си. При заказе работы своего варианта вы получите качественно написанную и хорошо прокомментированную программу.

Дополнительно заказав алгоритм решения вашей задачи (мы крайне рекомендуем это сделать), получите аккуратно оформленный отчет-алгоритм, поясняющий все тонкости решения поставленной задачи.

Образец выполнения (вариант №12)

Условие задания

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

Алгоритм решения задачи

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

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

➡ Как найти первый минимальный элемент, а, точнее, индекс первого минимального элемента?

Для решения этой подзадачи опишем отдельную функцию в программе.
Запустим сканирование всех элементов массива от последнего к первому (обычно в процессе обработки массива его элементы просматривают, начиная с $1$-го, и двигаются к конечному). И будем просто нестрого сравнивать значение текущего элемента на равенство с минимальным из уже проверенных элементов. Это позволит найти последний минимальный при движении с конца в начало, но этот элемент будет являться первым минимальным, то есть иметь самый меньший индекс из всех минимальных элементов.

➡ Как найти последний максимальный элемент, а, точнее, индекс последнего максимального элемента?

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

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

Реализуем сортировку строго по примеру, данному в методическом пособию, хотя, очевидно, что методов сортировки элементов массива существует безумное множество. Лабораторная работа №6. Степанов. Си. Программирование. МГТУ им.Баумана. Пример сортировки элементов массива между первым минимальным и последним максимальным элементами

Необходимые программные функции для кодирования

Ниже представлен список необходимых функций, требующихся для успешного решения поставленной задачи (самое главное — помнить о том, что функция должна строго решать какую-то конкретную одну задачу).

№	Название функции	Назначение функции
1.	*GetIndexFirstMin*	Получение индекса первого минимального элемента массива.
2.	GetIndexLastMax	Получение индекса последнего максимального элемента массива.
3.	FillVector	Ввод количества элементов исходного массива и заполнение элементов массива вводом с клавиатуры.
4.	PrintVector	Построчный вывод элементов массива на экран.
5.	SortVector	Сортировка по убыванию элементов массива, находящихся между первым минимальным и последним максимальным элементами.
6.	main	Главная функция программы (точка входа).

Единственное, очень желательно было бы разбить функцию FillVector на две подфункции: ввод количества элементов и заполнение элементов массива, т к все-таки это разные действия. Но составители требуют, чтобы эти действия выполнялись в рамках одной функции. Хорошо, реализуем так, как требуют в постановке задания.

😡 Также составители хотят, чтобы студенты использовали для динамического выделения памяти оператор new, а для удаления динамической памяти оператор delete.

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

В языке Си для динамического перераспределения памяти используют функции malloc, calloc, realloc и free. По идее, именно эти функции и нужно бы применять…

Реализация задачи на языке Си

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

#include <stdio.h> // для ввода, вывода (scanf, printf)

#include <locale.h> // для руссификации (setlocale)

#include <conio.h> // для задержки программы (getch)

#define MAX 30 // максимально возможное количество элементов

//-------------------------------------------------------------------------------

// ввод количества элементов исходного массива и заполнение элементов массива вводом с клавиатуры.

// pcount - количество элементов массива

//-------------------------------------------------------------------------------

float* FillVector(int *pcount)

{

int i;

float* vector;

{

printf("Введите количество элементов массива из отрезка [1 .. %d]: ", MAX);

scanf("%d", pcount);

}

while((*pcount < 1) || (*pcount > MAX));

// выделяем динамическую память под одномерный массив дробных чисел

vector = new float[*pcount];

printf("\nВам предстоит ввести с клавиатуры %d вещественных чисел.\n", *pcount);

for(i = 0; i < *pcount; i++)

{

printf("\t- введите %d-й элемент массива: ", (i + 1));

scanf("%f", &(*(vector + i)));

}

return vector;

}

//-------------------------------------------------------------------------------

// построчный вывод элементов массива на экран

// pvector - одномерный массив дробных чисел, элементы которого печатаются

// pcount - количество элементов массива

// pmessage - сообщение, которое выдается на экран перед печатью

//-------------------------------------------------------------------------------

void PrintVector(const float pvector[], const int pcount, const char* pmessage)

{

int i;

printf(pmessage);

for(i = 0; i < pcount; i++)

printf("%8.3f", *(pvector + i));

printf("\n");

}

//-------------------------------------------------------------------------------

// получение индекса первого минимального элемента массива

// pvector - одномерный массив дробных чисел

// pcount - количество элементов массива

// в качестве ответа нужно вернуть индекс 1-го минимального элемента

//-------------------------------------------------------------------------------

int GetIndexFirstMin(const float pvector[], const int pcount)

{

int i;

int index = pcount - 1;

for(i = (pcount - 2); i >= 0; i--)

if(pvector[i] <= pvector[index])

index = i;

return index;

}

//-------------------------------------------------------------------------------

// получение индекса последнего максимального элемента массива

// pvector - одномерный массив дробных чисел

// pcount - количество элементов массива

// в качестве ответа нужно вернуть индекс последнего максимального элемента

//-------------------------------------------------------------------------------

int GetIndexLastMax(const float pvector[], const int pcount)

{

int i;

int index = 0;

for(i = 1; i < pcount; i++)

if(pvector[i] >= pvector[index])

index = i;

return index;

}

//-------------------------------------------------------------------------------

// сортировка по убыванию элементов массива,

// находящихся между первым минимальным и последним максимальным элементами

// pvector - сортируемый одномерный массив дробных чисел

// pstart - индекс первого элемента, который подлежит сортировке

// pend - индекс последнего элемента, который подлежит сортировке

// используется сортировка методом "пузырька" или обменом

//-------------------------------------------------------------------------------

void SortVector(float *pvector, const int pstart, const int pend)

{

int i, j;

int bb = 1;

float buf;

i = pend;

while(bb)

{

bb = 0;

for(j = pstart; j < i; j++)

if(*(pvector + j) < *(pvector + j + 1))

{

buf = *(pvector + j);

*(pvector + j) = *(pvector + j + 1);

*(pvector + j + 1) = buf;

bb = 1;

}

i--;

}

//-------------------------------------------------------------------------------

// главная функция программы (точка входа).

//-------------------------------------------------------------------------------

int main(void)

{

float *vector = NULL; // динамический одномерный вещественный массив

int countElement; // активное количество элементов массива

int indexFirstMin; // индекс первого минимального элемента

int indexLastMax; // индекс последнего максимального элемента

setlocale(LC_ALL, "rus"); // руссификация диалогов в программе

vector = FillVector(&countElement);

PrintVector(vector, countElement, "\nИсходный массив имеет вид: ");

indexFirstMin = GetIndexFirstMin(vector, countElement);

indexLastMax = GetIndexLastMax(vector, countElement);

printf("\nНомер первого минимального элемента: %d\n", indexFirstMin + 1);

printf("Номер последнего максимального элемента: %d\n", indexLastMax + 1);

SortVector(vector, indexFirstMin + 1, indexLastMax - 1);

PrintVector(vector, countElement, "\nОтсортированный массив имеет вид: ");

delete []vector; // удаляем память из-под массива

printf("\n\nДля завершения работы программы нажмите клавишу ENTER...");

getch(); // задержка программы, чтобы можно было просмотреть результаты

return 0; // завершение работы программы и передача управления в ОС

}

//-------------------------------------------------------------------------------

Результаты работы программы

№ теста	Смысл	Результат
1.	Все элементы равны друг другу (отсортированный массив равен исходному)
2.	Первый минимальный и последний максимальный соседние элементы (отсортированный массив равен исходному)
3.	Между первым минимальным и последним максимальным элементом стоят $3$ элемента, но они изначально идут по убыванию (отсортированный массив равен исходному)
4.	Между первым минимальным и последним максимальным стоят $4$ элемента (происходит сортировка «внутренних» элементов массива)

Стоимость заказа работы

💡 Стоимость одной программы из любого варианта составляет $200$ рублей.
💡 Стоимость алгоритма (в виде отчета в формате *.doc из любого варианта составляет $200$ рублей (заказывается опционально на ваше усмотрение, чтобы детально разобраться с решением лабораторной работы, например, не прибегая к консультации репетитора).

Для оформления заказа пишите на почту: proglabs@mail.ru.
Время нашего ответа обычно составляет не более 10 минут.

Лабораторная работа №6 (программирование алгоритмов сортировки массивов)

Постановка задания

Варианты заданий