Сортировка с помощью включения
Элементы массива делятся на уже готовую последовательность и исходную. При каждом шаге, начиная с I=2, из исходной последовательности извлекается i-ый элемент и вставляется на нужное место готовой последовательности, затем i увеличивается на 1 и т. д.
| готовая | исходная |
В процессе поиска нужного места осуществляются пересылки элементов больше выбранного на одну позицию вправо, т. е. выбранный элемент сравнивают с очередным элементом отсортированной части, начиная с j:=i-1. Если выбранный элемент больше a[i], то его включают в отсортированную часть, в противном случае a[j] сдвигают на одну позицию, а выбранный элемент сравнивают со следующим элементом отсортированной последовательности. Процесс поиска подходящего места заканчивается при двух различных условиях:
- если найден элемент a[j]>a[i];
- достигнут левый конец готовой последовательности.
int i,j,x;
for(i=1;i<n;i++)
{
x=a[i];//запомнили элемент, который будем вставлять
j=i-1;
while(x<a[j]&&j>=0)//поиск подходящего места
{
a[j+1]=a[j];//сдвиг вправо
j--;
}
a[j+1]=x;//вставка элемента
}
Сортировка методом простого выбора
Выбирается минимальный элемент массива и меняется местами с первым элементом массива. Затем процесс повторяется с оставшимися элементами и т. д.
| мин |
int i,min,n_min,j;
for(i=0;i<n-1;i++)
{
min=a[i];n_min=i;//поиск минимального
for(j=i+1;j<n;j++)
if(a[j]<min)
{
min=a[j];
n_min=j;
}
a[n_min]=a[i];//обмен
a[i]=min;
}
Сортировка методом простого обмена
Сравниваются и меняются местами пары элементов, начиная с последнего. В результате самый маленький элемент массива оказывается самым левым элементом массива. Процесс повторяется с оставшимися элементами массива.
 42 | |||||
for(int i=1;i<n;i++)
for(int j=n-1;j>=i;j--)
if(a[j]<a[j-1])
{
int r=a[j];
a[j]=a[j-1];
a[j-1]=r;}
}
Поиск в отсортированном массиве
В отсортированном массиве используется дихотомический (бинарный) поиск. При последовательном поиске требуется в среднем n/2 сравнений, где n – количество элементов в массиве. При дихотомическом поиске требуется не более m сравнений, если n- m-ая степень 2, если n не является степенью 2, то n<k=2m.
Массив делится пополам S:=(L+R)/ 2+1 и определяется в какой части массива находится нужный элемент Х. Так как массив упорядочен, то, если a[S]<X – искомый элемент находится в правой части массива, иначе – находится в левой части. Выбранную часть массива снова надо разделить пополам и т. д., до тех пор, пока границы отрезка L и R не станут равны.
L S R
int b;
cout<<"\nB=?";cin>>b;
int l=0,r=n-1,s;
do
{
s=(l+r)/2;//средний элемент
if(a[s]<b)l=s+1;//перенести леую границу
else r=s;//перенести правую границу
}while(l!=r);
if(a[l]==b)return l;
else return -1;
…
Постановка задачи
1) Сформировать массив из n элементов с помощью датчика случайных чисел (n задается пользователем с клавиатуры).
2) Распечатать полученный массив.
3) Выполнить удаление указанных элементов из массива.
4) Вывести полученный результат.
5) Выполнить добавление указанных элементов в массив.
6) Вывести полученный результат.
7) Выполнить перестановку элементов в массиве.
8) Вывести полученный результат.
9) Выполнить поиск указанных в массиве элементов и подсчитать количество сравнений, необходимых для поиска нужного элемента.
10) Вывести полученный результат.
11) Выполнить сортировку массива указанным методом.
12) Вывести полученный результат.
13) Выполнить поиск указанных элементов в отсортированном массиве и подсчитать количество сравнений, необходимых для поиска нужного элемента.
14) Вывести полученный результат.
Варианты
| Вариант | Удаление | Добавление | Перестановка | Поиск | Сортировка |
| Максимальный элемент | К элементов в начало массива | Перевернуть массив | Первый четный | Простой обмен | |
| Минимальный элемент | К элементов в конец массива | Сдвинуть циклически на M элементов вправо | Первый отрицательный | Простой выбор | |
| Элемент с заданным номером | N элементов, начиная с номера К | Сдвинуть циклически на M элементов влево | Элемент с заданным ключом (значением) | Простое включение | |
| N элементов, начиная с номера K | Элемент с номером К | Поменять местами элементы с четными и нечетными номерами | Элемент равный среднему арифметическому элементов массива | Простой обмен | |
| Все четные элементы | К элементов в начало массива | Четные элементы переставить в начало массива, нечетные - в конец | Первый четный | Простой выбор | |
| Все элементы с четными индексами | К элементов в конец массива | Поменять местами минимальный и максимальный элементы | Первый отрицательный | Простое включение | |
| Все нечетные элементы | N элементов, начиная с номера К | Положительные элементы переставить в начало массива, отрицательные - в конец | Элемент с заданным ключом (значением) | Простой обмен | |
| Все элементы с нечетными индексами | Элемент с номером К | Перевернуть массив | Элемент равный среднему арифметическому элементов массива | Простой выбор | |
| Все элементы больше среднего арифметического элементов массива | К элементов в начало массива | Сдвинуть циклически на M элементов вправо | Первый четный | Простое включение | |
| Максимальный элемент | К элементов в конец массива | Сдвинуть циклически на M элементов влево | Первый отрицательный | Простой обмен | |
| Минимальный элемент | N элементов, начиная с номера К | Поменять местами элементы с четными и нечетными номерами | Элемент с заданным ключом (значением) | Простой выбор | |
| Элемент с заданным номером | Элемент с номером К | Четные элементы переставить в начало массива, нечетные - в конец | Элемент равный среднему арифметическому элементов массива | Простое включение | |
| N элементов, начиная с номера K | К элементов в начало массива | Поменять местами минимальный и максимальный элементы | Первый четный | Простой обмен | |
| Все четные элементы | К элементов в конец массива | Положительные элементы переставить в начало массива, отрицательные - в конец | Первый отрицательный | Простой выбор | |
| Все элементы с четными индексами | N элементов, начиная с номера К | Перевернуть массив | Элемент с заданным ключом (значением) | Простое включение | |
| Все нечетные элементы | Элемент с номером К | Сдвинуть циклически на M элементов вправо | Элемент равный среднему арифметическому элементов массива | Простой обмен | |
| Все элементы с нечетными индексами | К элементов в начало массива | Сдвинуть циклически на M элементов влево | Первый четный | Простой выбор | |
| Все элементы больше среднего арифметического элементов массива | К элементов в конец массива | Поменять местами элементы с четными и нечетными номерами | Первый отрицательный | Простое включение | |
| Максимальный элемент | N элементов, начиная с номера К | Четные элементы переставить в начало массива, нечетные - в конец | Элемент с заданным ключом (значением) | Простой обмен | |
| Минимальный элемент | Элемент с номером К | Поменять местами минимальный и максимальный элементы | Элемент равный среднему арифметическому элементов массива | Простой выбор | |
| Элемент с заданным номером | К элементов в начало массива | Положительные элементы переставить в начало массива, отрицательные - в конец | Первый четный | Простое включение | |
| N элементов, начиная с номера K | К элементов в конец массива | Перевернуть массив | Первый отрицательный | Простой обмен | |
| Все четные элементы | N элементов, начиная с номера К | Сдвинуть циклически на M элементов вправо | Элемент с заданным ключом (значением) | Простой выбор | |
| Все элементы с четными индексами | Элемент с номером К | Сдвинуть циклически на M элементов влево | Элемент равный среднему арифметическому элементов массива | Простое включение | |
| Все нечетные элементы | К элементов в начало массива | Поменять местами элементы с четными и нечетными номерами | Первый четный | Простой обмен |
Методические указания
1. При решении задач использовать псевдодинамические массивы. Псевдодинамические массивы реализуются следующим образом:
1) при определении массива выделяется достаточно большое количество памяти:
const int MAX_SIZE=100;//именованная константа
int mas[MAX_SIZE];
2) пользователь вводит реальное количество элементов массива меньшее N.
int n;
cout<<”\nEnter the size of array<”<<MAX_SIZE<<”:”;cin>>n;
3) дальнейшая работа с массивом ограничивается заданной пользователем размерностью n.
2. Формирование массива осуществляется с помощью датчика случайных чисел. Для этого можно использовать функцию int rand(), которая возвращает псевдослучайное число из диапазона 0..RAND_MAX=32767, описание функции находится в файле <stdlib.h>. В массиве должны быть записаны и положительные и отрицательные элементы. Например, оператор a[I]=rand()%100-50; формирует псевдослучайное число из диапазона [-50;49].
3. Вывод результатов должен выполняться после выполнения каждого задания. Элементы массива рекомендуется выводить в строчку, разделяя их между собой пробелом.
6. Содержание отчета:
1) Постановка задачи (общая и конкретного варианта).
2) Анализ поставленного задания: определить к какому классу задач относится задача и объяснить почему.
3) Текст программы.
4) Результаты тестов.
5) Решение одной из задач с использованием указателей для доступа к элементам массива.
Лабораторная работа №4
Функции и массивы в С++
1. Цель работы:
1) Получение практических навыков при работа со строками, одномерными и двумерными массивами.
2) Получение практических навыков при работе с функциями
3) Получение практических навыков при передаче массивов и строк в функции.
Теоретические сведения
Функция – это именованная последовательность описаний и операторов, выполняющая законченное действие, например, формирование массива, печать массива и т. д.
Любая функция должна быть объявлена и определена.
· Объявление функции (прототип, заголовок) задает имя функции, тип возвращаемого значения и список передаваемых параметров.
· Определение функции содержит, кроме объявления, тело функции, которое представляет собой последовательность описаний и операторов.
тип имя_функции([список_формальных_параметров])
{ тело_функции}
· Тело_функции – это блок или составной оператор. Внутри функции нельзя определить другую функцию.
В теле функции должен быть оператор, который возвращает полученное значение функции в точку вызова. Он может иметь 2 формы:
1) return выражение;
2) return;
Первая форма используется для возврата результата, поэтому выражение должно иметь тот же тип, что и тип функции в определении. Вторая форма используется, если функция не возвращает значения, т. е. имеет тип void. Программист может не использовать этот оператор в теле функции явно, компилятор добавит его автоматически в конец функции перед }.
· Тип возвращаемого значения может быть любым, кроме массива и функции, но может быть указателем на массив или функцию.
· Список формальных параметров – это те величины, которые требуется передать в функцию. Элементы списка разделяются запятыми. Для каждого параметра указывается тип и имя. В объявлении имена можно не указывать.
Для того, чтобы выполнялись операторы, записанные в теле функции, функцию необходимо вызвать. При вызове указываются: имя функции и фактические параметры. Фактические параметры заменяют формальные параметры при выполнении операторов тела функции. Фактические и формальные параметры должны совпадать по количеству и типу.
Объявление функции должно находиться в тексте раньше вызова функции, чтобы компилятор мог осуществить проверку правильности вызова. Если функция имеет тип не void, то ее вызов может быть операндом выражения.
Параметры функции
Основным способом обмена информацией между вызываемой и вызывающей функциями является механизм параметров. Существует два способа передачи параметров в функцию: по адресу и по значению.
- При передаче по значению выполняются следующие действия:
- вычисляются значения выражений, стоящие на месте фактических параметров;
- в стеке выделяется память под формальные параметры функции;
- каждому фактическому параметру присваивается значение формального параметра, при этом проверяются соответствия типов и при необходимости выполняются их преобразования.
void Change(int a,int b)//передача по значению
{
int r=a;
a=b;
b=r;
}
int main()
{
int x=1,y=5;
Change(x,y);
cout<<”x=”<<x<<” y=”<<y; //выведется: x=1 y=5
return 1;
}
- При передаче по адресу в стек заносятся копии адресов параметров, следовательно, у функции появляется доступ к ячейке памяти, в которой находится фактический параметр и она может его изменить.
void Change(int *a,int *b)//передача по адресу
{
int r=*a;
*a=*b;
*b=r;
}
int main()
{
int x=1,y=5;
Change(&x,&y);
cout<<”x=”<<x<<” y=”<<y; //выведется: x=5 y=1
return 1;
}
Для передачи по адресу также могут использоваться ссылки. Ссылка – это синоним имени объекта, указанного при инициализации ссылки.
Формат объявления ссылки
тип & имя =имя_объекта;
Ссылка не занимает дополнительного пространства в памяти, она является просто другим именем объекта.
При передаче по ссылке в функцию передается адрес указанного при вызове параметра, а внутри функции все обращения к параметру неявно разыменовываются.
void Change(int &a,int &b)
{
int r=a;
a=b;
b=r;
}
int main()
{
int x=1,y=5;
Change(x,y);
cout<<”x=”<<x<<” y=”<<y; //выведется: x=5 y=1
return 1;
}
Использование ссылок вместо указателей улучшает читаемость программы, т. к. не надо применять операцию разыменовывания. Использование ссылок вместо передачи по значению также более эффективно, т .к. не требует копирования параметров. Если требуется запретить изменение параметра внутри функции, используется модификатор const. Рекомендуется ставить const перед всеми параметрами, изменение которых в функции не предусмотрено (по заголовку будет понятно, какие параметры в ней будут изменяться, а какие нет).