Способы сортировки в массивах данных.

Для реализации алгоритма любого способа сортировки требуется прохождение не менее двух вложенных циклов.

4.2.1. Пузырьковая сортировка (попарные перестановки) выполняется многократными перестановками каждых двух соседних элементов, нарушающих порядок; процесс завершается, когда достигается упорядоченность массива.

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

Блок-схема алгоритма перестановок элементов массива (сортировка по возрастанию):

Также алгоритм пузырьковой сортировки можно реализовать, используя в качестве внешнего цикла цикл с постусловием (переменная f используется в качестве признака перестановок):

4.2.2. Сортировка простого выбора (минимума/максимума) выполняется перестановками каждого элемента с минимальным/максимальным (в зависимости от признака порядка) среди следующих за ним элементов.

Блок-схема алгоритма перестановок элементов массива (сортировка по возрастанию):

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

1. Чем является переменная в программе?

2. Что означает унарная операция «&», к каким объектам она применима?

3. Какое значение может принимать адрес?

4. Чем является указатель, что он содержит?

5. Для чего используются указатели?

6. Что означает унарная операция «*», что является ее результатом?

7. На объект какого типа может ссылаться указатель?

8. Что означает указатель на тип void?

9. Что такое статическая структура данных?

10. Чем характеризуются переменные статических структур?

11. Что представляет собой массив данных?

12. На каком этапе выделяется память под элементы массива?

13. Меняется ли объем памяти, выделенный под массив, во время выполнения программы?

14. Как занести в указатель адрес первого элемента массива?

15. На что ссылается любой указатель?

16. Что является результатом операции указатель+i?

17. Чем отличаются операции p++ и *p++, если p – указатель?

18. Чем отличаются операции (*p)++ и *(++p), если p – указатель?

19. Что означает линейный поиск в массиве данных?

20. Что называется сортировкой информационной структуры?

21. Какие существуют признаки порядка?

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

23. Как выполнить сортировку массива простым выбором?

III. Практическая часть.

1. Выполнение общего задания.

Задача 1.

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

Вариант 1 (используется обращение к элементам массива по имени)

2. Математическая модель и описательный алгоритм: для введенного (входного) массива данных:1 -5 0 -9 5 7 0 -2 4 0,выходной массив:1 5 7 4.

• Объявить входной массив, размерность которого задать константой с: int mas[c];

• выходной массив может состоять из такого же количества элементов, как входной (если все элементы положительные), поэтому объявить: int mas_new[c];

• в цикле с постусловием n≤0 или n>c ввести количество элементов массива 0<n≤с;

• в цикле с параметром 0≤i<n ввести элементы входного массива mas[i];

• переменная j=0 – счетчик количества элементов выходного массива;

• в цикле с параметром 0≤i<n для каждого элемента mas[i] проверять условие: если mas[i]>0, то mas_new[j]=mas[i] и j=j+1;

• если j≠0, то во входном массиве есть положительные элементы, значит, выходной массив создан, тогда в цикле с параметром 0≤i<n вывести элементы mas_new[i]; иначе вывести «нет элементов>0».

3. Блок-схема алгоритма программы:

4. Текст программы:

#include <stdio.h>

#include <conio.h>

int main()

{

const c=15;

int n,j=0,mas[c],mas_new[c];

do

{

printf(“\n input n=”);

scanf(“%d”,&n); // ввод количества элементов входного массива

}

while (n<=0 || n>c);

printf(“\n input massiv:\n”);

for (int i=0;i<n;i++)

scanf(“%d”,&mas[i]); // ввод элементов входного массива

printf(“\n output massiv:\n”);

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

printf(“%d “,mas[i]); // вывод элементов входного массива

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

if (mas[i]>0)

{

mas_new[j]=mas[i]; // создание выходного массива

j++;

}

if (j!=0)

{

printf(“\n output massiv:\n”);

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

printf(“%d “,mas_new[i]); // вывод элементов выходного массива

}

else printf(“\n there are no elements>0\n”);

getch();

return 0;

}

Вариант 2 (используется обращение к элементам массива по адресу)

2. Математическая модель и описательный алгоритм: входной массив элементов:1 -5 0 -9 5 7 0 -2 4 0,выходной массив:1 5 7 4.

• Объявить массивы, размерность которых задать константой c: int mas[c], mas_new[c];

• в цикле с постусловием n≤0 или n>c ввести количество элементов массива 0<n≤с;

• установить указатели на первые элементы массивов: p=&mas[0], p_new=&mas_new[0];

• в цикле с параметром 0≤i<n ввести значения элементов входного массива по адресу p, устанавливая после каждого прохода цикла указатель на следующий элемент: p= p+1;

• j=0 (счетчик элементов выходного массива), установить указатель снова на первый элемент входного массива: p=p-n;

• в цикле с параметром 0≤i<n проверять условие: если *p>0, то *p_new=*p, j=j+1 и p_new=p_new+1; p=p+1;

• если j≠0, то выходной массив создан, тогда установить указатель на первый элемент выходного массива: p_new=p_new-j, в цикле с параметром 0≤i<n вывести значения элементов выходного массива *p_new; иначе вывести «there are no elements>0».

3. Блок-схема алгоритма программы:

4. Текст программы:

#include <stdio.h>

#include <conio.h>

int main()

{

const c=15;

int n,j=0,mas[c],mas_new[c],*p,*p_new;

do

{

printf(“\n input n=”);

scanf(“%d”,&n); // ввод количества элементов в массиве

}

while (n<=0 || n>c);

p=&mas[0];

p_new=&mas_new[0];

printf(“\n input massiv:\n”);

for (int i=0;i<n;i++)

{

scanf(“%d”,p); // ввод элементов массива

p++;

}

p-=n;printf(“\n output massiv:\n”);

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

{

printf(“%d “,*p); // вывод элементов массива

p++;

}

p-=n;

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

{

if (*p>0)

{

*p_new=*p; // создание нового массива

p_new++;

j++;

}

p++;

}

if (j!=0)

{

p_new-=j;

printf(“\n output massiv:\n”);

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

{

printf(“%d “,*p_new); // вывод элементов нового массива

p_new++;

}

}

else printf(“\n there are no elements>0\n”);

getch(); return 0;

}

5. Тестирование:

Теоретически рассчитанное выходное значение	Практически полученное выходное значение
Тест 1: входной массив: n=10; mas[n]: 1 -5 0 -9 5 7 0 -2 4 0
j=4; mas_new[j]: 1 5 7 4	j=4; mas_new[j]: 1 5 7 4
Тест 2: входной массив: n=10; mas[n]: -1 -5 0 -9 -5 -7 0 -2 -4 0
«нет элементов>0»	«нет элементов>0»

Задача 2.

1. Постановка задачи: разработать алгоритм нахождения в введенном массиве из n элементов последнего наименьшего элемента, обмена местами его с третьим элементом и вывода полученного массива. Написать программу, реализующую разработанный алгоритм.

2. Математическая модель и описательный алгоритм: входной массив х:-5 8 0 4 -5 7 9 0 9 -1(индексы элементов массива: 0 1 2 3 4 5 6 7 8 9); последний наименьший элемент в массиве x[4]=-5; третий элемент в массиве x[2]=0;выходной массив x после перестановки элементов: -5 8 -5 4 0 7 9 0 9 -1 (0 1 2 3 4 5 6 7 8 9).

• Объявить массив, размерность которого задать константой c: int x[c];

• в цикле с постусловием n≤0 или n>c ввести количество элементов массива 0<n≤с;

• указатель p установить на нулевой элемент: p=&x[0];

• в цикле с параметром 0≤i<n ввести значения элементов входного массива по адресу p, p=p+1;

• указатель p установить снова на нулевой элемент: p=p-n; в цикле с параметром 0≤i<n вывести значения элементов введенного массива *p, p=p+1;

• p уменьшить на единицу (p=p-1), потому что после выхода из цикла вывода значений элементов массива p=n;

• переменной min присвоить значение последнего элемента массива, используя операцию разыменования: min=*p,

• в цикле с параметром i от n-2 и до 0 (i=i-1), начиная с предпоследнего элемента (p=p-1), сравнивать min с текущим элементом: если *p<min, то min и индекс минимального элемента k переопределять: min=*p, k=i;

• чтобы поменять местами третий элемент с найденным, необходимо переопределить значения по адресам, используя операцию разыменования: *(p+n-1-k) =*(p+2), *(p+2)=min;

• в цикле с параметром 0≤i<n вывести значения элементов выходного массива *p, p=p+1.

3. Блок-схема алгоритма программы:

4. Текст программы:

#include <stdio.h>

#include <conio.h>

void main()

{

const c=20;

int x[c],i,k=0,min,*p,n;

do

{

printf("\nInput number of elements of massiv n=");

scanf("%d",&n);

}

while (n<=0 || n>c);

p=&x[0];

printf("\nInput elements of massive:\n");

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

{

printf("x[%d]=",i);

scanf("%d",p);

p++;

}

p-=n;

printf("\nOutput massiv:\n");

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

{

printf("%d ",*p);

p++;

}

p--; min=*p;

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

{

p--;

if (*p<min)

{

min=*p;

k=i;

}

}

*(p+k)=*(p+2);

*(p+2)=min;

printf("\nOutput massiv:\n");

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

{

printf("%d ",*p);

p++;

}

getch();

return;

}

5. Тестирование:

Теоретически рассчитанное выходное значение	Практически полученное выходное значение
Тест 1: входной массив: n=10; x[n]: -5 8 0 4 -5 7 9 0 9 -1
x[n]: -5 8 -5 4 0 7 9 0 9 -1	x[n]: -5 8 -5 4 0 7 9 0 9 -1
Тест 2: входной массив: n=7; x[n]: 1 0 5 9 1 0 4
вых. массив x[n]: 1 0 0 9 1 5 4	вых. массив x[n]: 1 0 0 9 1 5 4

Задача 3.

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

2. Математическая модель и описательный алгоритм: входной массив a: 9 0 -3 6 -3 2 8 9;входной массив индексов ai: 0 1 2 3 4 5 6 7;выходной массив после перестановок (после сортировки по неубыванию, когда a_j+1≥a_j): -3 -3 0 2 6 8 9 9;выходной массив индексов: 2 4 1 5 3 6 0 7.

• В цикле с постусловием n≤0 или n>c ввести количество n элементов массива;

• p=&a[0], в указатель pi занести адрес нулевого элемента массива индексов pi=&ai[0];

• в цикле с параметром 0≤i<n ввести значения элементов по адресу p, p=p+1 и сформировать массив индексов *pi=i, pi=pi+1;

• p=p-n; в цикле с параметром 0≤i<n вывести значения элементов массива *p, p=p+1;

• для пузырьковой сортировки массива во внешнем цикле с параметром 0≤i<n-1 установить указатели p=p-n+i, pi=pi-n+i; во вложенном цикле с параметром 0≤j<n-1-i переставлять рядом стоящие элементы при нарушении признака порядка (неубывание – a_j+1≥a_j): если *(p+1)<*p, то менять элементы местами, используя дополнительную переменную b, вместе с элементами массива переставлять элементы массива индексов, чтобы отследить правильность сортировки по заданному признаку порядка, затем p=p+1, pi=pi+1;

• в цикле с параметром 0≤i<n вывести значения элементов отсортированного массива *p, p=p+1;

• в цикле с параметром 0≤i<n вывести значения элементов массива индексов после соответствующих перестановок *pi, pi=pi+1.

3. Блок-схема алгоритма программы:

4. Текст программы:

#include <stdio.h>

#include <conio.h>

void main()

{

const c=10;

int i,j,b,n,a[c],ai[c],*p,*pi;

do

{

printf("\nInput number of elements of massiv n=");

scanf("%d",&n);

}

while (n<=0 || n>c);

p=&a[0]; pi=&ai[0];

printf("\nInput elements of massive:\n");

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

{

printf("a[%d]=",i);

scanf("%d",p);

*pi=i; p++; pi++;

}

p-=n; printf("\nOutput massiv:\n");

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

{

printf("%d ",*p); p++;

}

for (i=0;i<n-1;i++)

{

p=p-n+i; pi=pi-n+i;

for (j=0;j<n-1-i;j++)

{

if (*(p+1)<*p)

{

b=*(p+1);

*(p+1)=*p; *p=b;

b=*(pi+1);

*(pi+1)=*pi; *pi=b;

}

p++; pi++;

}

}

p--; pi--; printf("\nOutput massiv:\n");

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

{

printf("%d ",*p); p++;

}

printf("\n");

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

{

printf("%d ",*pi); pi++;

}

getch();

return;

}

5. Тестирование:

Теоретически рассчитанное выходное значение	Практически полученное выходное значение
Тест: входной массив: n=8; a[n]: 9 0 -3 6 -3 2 8 9
вых. массив a[n]: -3 -3 0 2 6 8 9 9 массив идексов ai[n]: 2 4 1 5 3 6 0 7	вых. массив a[n]: -3 -3 0 2 6 8 9 9 массив индексов ai[n]: 2 4 1 5 3 6 0 7

2. Выполнение индивидуального задания.

Постановка задачи.

Разработать алгоритм и написать программу по индивидуальному заданию.

2. Входные и выходные данные.

Все действующие в программе переменные должны быть объявлены.

Недопустимо задавать исходные (входные) данные с помощью операторов присваивания. Ввод данных с клавиатуры должен предваряться выводом соответствующего сообщения.

3. Математическая модель и описательный алгоритм задачи.

Блок-схема алгоритма.

Представить алгоритм задачи в виде блок-схемы.

Текст программы.

Разработанный алгоритм реализуется на языке программирования высокого уровня Cи.

Тестирование.

Результаты тестирования представить в виде таблицы.

IV. Требования к разработке программы.

Программа должна содержать следующие три составные части:

• ввод исходных данных;
• обработку данных;
• вывод результатов.

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

V. Требования к защите индивидуальных заданий.

ИМЕТЬ отчет, который включает:

1. постановку задачи;

2. математическую модель и описательный алгоритм задачи;

3. блок-схему алгоритма;

4. текст программы;

5. результаты тестирования.

ЗНАТЬ ответы на контрольные вопросы.

VI. Варианты индивидуальных заданий.

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

Вариант №1

1. Поменять знак у элементов массива, номер которых кратен 3, вывести полученный массив.

2. Найти и вывести номер минимального элемента среди элементов массива, меньших введенного значения x.

Вариант №2

1. Заменить все положительные четные элементы массива единицами, вывести полученный массив.

2. Найти и вывести номер первого максимального элемента среди отрицательных элементовмассива.

Вариант №3

1. Заменить все положительные нечетные элементы массива нулями, подсчитать их количество, вывести это значение и полученный массив.

2. Найти и вывести номер максимального элемента среди положительных четных по значению элементов массива.

Вариант №4

1. Заменить все положительные элементы массива минимальным элементом, вывести полученный массив.

2. Найти и вывести номер первого максимального элемента среди отрицательных элементов массива.

Вариант №5

1. Заменить все положительные элементы массива максимальным элементом, вывести полученный массив.

2. Найти и вывести номер последнего максимального значения среди положительных элементов массива.

Вариант №6

1. Заменить каждый 5-й элемент массива максимальным элементом, вывести полученный массив.

2. Найти и вывести номер последнего минимального элемента среди элементов, меньших введенного значения x.

Вариант №7

1. Поменять знак у элементов массива, кратных 5, вывести полученный массив.

2. Найти и вывести номер последнего элемента среди элементов массива, лежащих в диапазоне введенных значений [c,d].

Вариант №8

1. Заменить все отрицательные нечетные по значению элементы массива единицами, вывести полученный массив.

2. Найти и вывести номер последнего минимального элемента среди четных по значению положительных элементов массива.

Вариант №9

1. Заменить все положительные нечетные по значению элементы массива нулями, вывести полученный массив.

2. Найти и вывести номер последнего минимального элемента среди элементов массива, меньших введенного значения x.

Вариант №10

1. Заменить все положительные нечетные по значению элементы массива минимальным элементом, вывести полученный массив.

2. Найти и вывести номер первого максимального элемента среди элементов массива, лежащих в диапазоне от a до b.

Вариант №11

1. Заменить каждый 3-й элемент массива минимальным элементом, вывести полученный массив.

2. Найти и вывести номер максимального положительного элемента массива, кратного 7.

Вариант №12

1. Заменить все отрицательные четные элементы массива нулями, подсчитать их количество, вывести это значение и полученный массив.

2. Найти и вывести номер минимального положительного элемента.

Вариант №13

1. Заменить каждый 4-й элемент массива минимальным элементом, вывести полученный массив.

2. Найти и вывести номер первого максимального значения среди элементов, меньших введенного значения t.

Вариант №14

1. Заменить каждый 7-й элемент массива минимальным элементом, вывести полученный массив.

2. Найти и вывести номер последнего максимального элемента среди элементов массива, лежащих в диапазоне введенных значений [с,d].

Вариант №15

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

2. Найти и вывести номер последнего максимального элемента среди положительных элементов массива.

Вариант №16

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

2. Найти и вывести номер первого максимального элемента среди элементов массива, больших введенного значения x.

Вариант №17

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

2. Найти и вывести номер первого минимального положительного элемента массива.

Вариант №18

1. Подсчитать сумму элементов массива, номер которых кратен 3-м, изменить знак этих элементов на противоположный, вывести значение суммы и полученный массив.

2. Упорядочить массив по возрастанию, используя пузырьковую сортировку, вывести полученный массив и массив индексов после перестановок.

Вариант №19

1. Найти и вывести номер максимального элемента среди четных по значению элементов массива.

2. Упорядочить массив по убыванию, используя пузырьковую сортировку, вывести полученный массив и массив индексов после перестановок.

Вариант №20

1. Найти и вывести номер максимального элемента массива среди элементов, кратных введенному значению k.

2. Упорядочить массив по невозрастанию, используя пузырьковую сортировку, вывести полученный массив и массив индексов после перестановок.

Вариант №21*

1. Подсчитать сумму и произведение всех отрицательных нечетных элементов массива, заменить их нулями, вывести значения суммы, произведения и полученный массив.

2. Упорядочить массив по неубыванию, используя сортировку простого выбора, вывести полученный массив и массив индексов после перестановок.

Вариант №22*

1. Подсчитать сумму четных по номеру элементов массива, заменить ее значением последний элемент, найти номер первого минимального положительного элемента, вывести его и полученный массив.

2. Упорядочить массив по возрастанию, используя сортировку простого выбора, вывести полученный массив и массив индексов после перестановок.

Вариант №23*

1. Найти и вывести номер первого максимального элемента среди отрицательных четных по значению элементов массива.

2. Упорядочить массив по невозрастанию, используя сортировку простого выбора, вывести полученный массив и массив индексов после перестановок.

Вариант №24*

1. Сделать переворот массива так, чтобы первый элемент стал последним, а последний – первым, вывести полученный массив. Дополнительный массив не использовать.

2. Упорядочить массив по убыванию, используя сортировку простого выбора, вывести полученный массив и массив индексов после перестановок.

Вариант №25*

1. Найти и вывести номер последнего максимального элемента среди нечетных по значению элементов массива.

2. Упорядочить массив по неубыванию, используя сортировку простого выбора, вывести полученный массив и массив индексов после перестановок.