Максимальный и минимальный элементы массива.сортировка

Пример 1. Поменять местами максимальный и минимальный элементы массива

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

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

#include < iostream.h>

#include < iomanip.h>

#include < math.h>

main()

{ const int n=10;

int i, j, k, max, min, tmp, m[n]={6, 3, 1, 5, 9, -1, -9};

max=m[0];

min=m[0];

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

{ if(m[i]> max)

{ max=m[i]; j=i; }

if(m[i]< min)

{ min=m[i]; k=i; }

}

tmp=m[k];

m[k]=m[j];

m[j]=tmp;

cout< < min< < max;

}

Пример 2. Поиск максимального и минимального элементов в массиве в сочетании с условием отбора.

Поскольку необходим поиск min и max среди элементов массива, удовлетворяющих заданному условию, то величина первого такого элемента заранее неизвестна. Начальное значение переменной, в которой хранится min (max) должно быть заведомо большим (меньшим), чем любой из элементов массива, удовлетворяющих заданному условию. В качестве начального значения может служить максимально возможная величина, представимая в ЭВМ для типа данных элементов массива. Эти значения имеют именованные константы, определеные в библиотеках limits.h для целых типов и float.h для вещественных типов.

Программа, печатающая значения именованных констант

#include < iostream.h>

#include< iomanip.h>

#include< limits.h>

#include< float.h>

main()

{cout< < " LONG_MIN " < < LONG_MIN< < " LONG_MAX " < < LONG_MAX< < endl;

cout< < " FLT_MIN " < < FLT_MIN< < " FLT_MAX " < < FLT_MAX< < endl;

cout< < " DBL_MIN " < < DBL_MIN< < " DBL_MAX " < < DBL_MAX< < endl;

cout< < " LDBL_MIN " < < LDBL_MIN< < " LDBL_MAX " < < LDBL_MAX< < endl;

cout< < " FLT_DIG " < < FLT_DIG< < " FLT_EPSILON " < < FLT_EPSILON< < endl;

Программа поиска минимального положительного элемента в массиве

#include < iostream.h>

#include < iomanip.h>

#include < math.h>

#include < float.h>

main()

{ const int n=10;

double i, j, k, max, min, tmp, m[n]={6., 3., 1., 5., 9., -1., -9.};

min=DBL_MAX;

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

{ if(m[i]> 0 & & m[i]< min)

min=m[i];

}

cout< < min;

}

Пример 3. Сортировка массива методом “пузырька”

Вариант 1. Последовательным просмотром элементов массива m c индексом i от 0 до n-1 найдем наименьшее i, такое, что m[i]> m[i+1]. Поменяем местами m[i] и m[i+1] и возобновим просмотр с элемента m[i+1] и т. д. В результате самое большое число передвинется на последнее место. Следующие просмотры необходимо начинать с элемента с индексом 0, уменьшив на 1 количество просматриваемых элементов. Массив будет упорядочен после просмотра в котором участвовали первый и второй элементы.

#include < iostream.h>

#include < iomanip.h>

#include < math.h>

main()

{int i, j, n, k, max, min, tmp, m[10]={6, 3, 1, 5, 9, -1, -9, 7, 2, 0};

n=10;

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

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

if(m[j]> m[j+1])

{ tmp=m[j];

m[j]=m[j+1];

m[j+1]=tmp; }

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

cout< < setw(3)< < m[i];

}

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

#include < iostream.h>

#include < iomanip.h>

#include < math.h>

main()

{ const int n=10;

int i, j, k, tmp, m[n]={6, 3, 1, 5, 9, -1, -9, 7, 2, 0};

i=1;

while(i> 0)

{ i=0;

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

if(m[j]> m[j+1])

{ tmp=m[j];

m[j]=m[j+1];

m[j+1]=tmp;

i=1;

}

}

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

cout< < setw(3)< < m[i];

}

Пример 4. Бинарный поиск в упорядоченном массиве

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

#include< iostream.h>

#include< iomanip.h>

#include< conio.h>

void main()

{ clrscr();

const int n=9;

float m[n]={1, 2, 3, 4, 5, 6, 7, 8, 9};

float x;

int end=1;

cin> > x;

int i=0, j=n, k;

while (j> i & & end! =0)

{ k=(i+j)/2;

if(m[k]> x)

j=k;

else if(m[k]< x)

i=k;

else end=0;

}

if(end==0) cout< < k;

else cout< < " no" < < endl;

}