Алгоритм сортировки методом нахождения локальных экстремумов
Необходимо отсортировать массив удовлетворяющий
условию (Ai)[ a[i]<=a[i+1] ].
( для любого i справедливо а[i]<=a[i+1] )
В цикле проверяем условие,
если a[i] >a[i+1] , то a[i] и a[i+1 ]меняем местами
# include <iostream.h>
const int n=10;
void main()
{
int a[n];
int i, j,r;
//Ввод массива с клавиатуры
cout<<”enter array a”<<endl;
for (i=0; i<n; i++)
{
cout<<”a[“<<i<<”]=”;
cin>>a[i];
}
//Вывод массива на экран
cout<<”array a”<<endl;
for (i=0; i<n; i++)
cout<<a[i]<<’ ‘;
cout<<endl;
for(i=0; i<n-1; i++)
for (j=i+1; j<n; j++)
if (a[i]>a[j])
{
r=a[i]; a[i]=a[j]; a[i]=r;
}
//Вывод массива на экран
cout<<”array a”<<endl;
for (i=0; i<n; i++)
cout<<a[i]<<’ ‘;
cout<<endl;
}
Задача 2.
Алгоритм сортировки методом обмена пар
( метод «пузырька» )
#include<iostream.h>
const int n=5;
void main()
{
cout<<" Bubble Sort "<<endl;
int i;
int r;
int a[n];
cout<<"enter array a:"<<endl;;
for(i=0;i<n;i++)
{
cout<<"a["<<i<<"]=";
cin>>a[i];
}
cout<<endl;
cout<<" array a:"<<endl;
for(i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
// BubbleSort
bool t=true;
while (t)
{
t=false;
for(i=0;i<n-1;i++)
if (a[i]>a[i+1])
{
r=a[i];
a[i]=a[i+1];
a[i+1]=r;
t=true;
}
}
cout<<" After sorting the array a:"<<endl;
for(i=0;i<n;i++)
cout<<a[i]<<' ';
cout<<endl;
}
Задача 3.
Алгоритм сортировки вставкой
#include <iostream>
using namespace std;
const int n=5;
void main()
{
int i,j,temp;;
int a[n];
cout<<"enter array a:"<<endl;
for (i = 0; i<n; i++)
{
cout<<"a["<<i<<"]=";
cin >> a[i];
}
cout<<"array a:"<<endl;
for (i = 0; i<n; i++)
cout<<a[i]<<' ';
cout<<endl;
for (i=0; i<n; i++)
{
temp = a[i];// запоминаем i- элемент
j =i-1;//идем начиная с i-1 элемента
while(j >= 0 && a[j] > temp)
// пока не достигли начала массива
// или не нашли элемент меньше или равного i-ому,
// который хранится в переменной temp
{
a[j + 1] = a[j];
// проталкиваем элемент вправо
j--;
}
a[j + 1] = temp;
// возвращаем i элемент
}
// Выводим отсортированный массив
cout<<"sort array a:"<<endl;
for (i = 0; i<n; i++)
cout<<a[i]<<' ';
cout<<endl;
}
Лекция
Тема: Одномерные массивы (продолжение )
( Т.М. Павловская С/C++ Программирование на языке высокого
Уровня
Тема: Одномерные массивы (стр. 136)
)
Вариант 7
Преобразовать массив таким образом, чтобы в первой половине располагались элементы, стоящие в нечетных позициях, а во второй половине - элементы, стоящие в четных позициях,
//arb2016_pavlovskaya_var7
#include <iostream>
using namespace std;
const int n=7;
void main()
{
int i,temp;;
int a[n];
cout<<"enter array a:"<<endl;
for (i = 0; i<n; i++)
{
cout<<"a["<<i<<"]=";
cin >> a[i];
}
cout<<"array a:"<<endl;
for (i = 0; i<n; i++)
cout<<a[i]<<' ';
cout<<endl;
// if n is even number n=6
/* for(i=1;i<n/2;i=i+1)
{
temp=a[i];
a[i]=a[n-1-i];
a[n-1-i]=temp;
}
*/
// if n is odd number n=7
for(i=0;i<n/2;i=i+2)
{
temp=a[i];
a[i]=a[n-i-2];
a[n-i-2]=temp;
}
cout<<" odd i in begin, even i in end a:"<<endl;
for (i = 0; i<n; i++)
cout<<a[i]<<' ';
cout<<endl;
}
Вариант 8
Преобразовать массив таким образом, чтобы сначала располагались , элементы по модулю не превышающие 1 , а потом все остальные
//arb2016_pavlovskaya_var8
#include <iostream>
#include <cmath>
using namespace std;
const int n=7;
void main()
{
int i,j,temp;;
double a[n];
cout<<"enter array a:"<<endl;
for (i = 0; i<n; i++)
{
cout<<"a["<<i<<"]=";
cin >> a[i];
}
cout<<"array a:"<<endl;
for (i = 0; i<n; i++)
cout<<a[i]<<' ';
cout<<endl;
i=0; j=n-1;
while(i<=j)
{
for( ; fabs(a[i])<=1;i++);
for( ; fabs(a[j])> 1;j--);
if (i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
cout<<"new array a:"<<endl;
for (i = 0; i<n; i++)
cout<<a[i]<<' ';
cout<<endl;
}
Вариант 9
Преобразовать массив таким образом, чтобы элементы равные 0 располагались после всех остальных.
//arb2016_pavlovskaya_var9
#include <iostream>
using namespace std;
const int n=7;
void main()
{
int i,j,temp;;
double a[n];
cout<<"enter array a:"<<endl;
for (i = 0; i<n; i++)
{
cout<<"a["<<i<<"]=";
cin >> a[i];
}
cout<<"array a:"<<endl;
for (i = 0; i<n; i++)
cout<<a[i]<<' ';
cout<<endl;
i=0; j=n-1;
while(i<=j)
{
for( ; a[i]!=0;i++);
for( ; a[j]==0 ;j--);
if (i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
cout<<"new array a:"<<endl;
for (i = 0; i<n; i++)
cout<<a[i]<<' ';
cout<<endl;
}
Лекция
Двумерные массивы.
В С++ можно использовать многомерные массивы. Двумерный массив представляет собой список одномерных массивов.
Объявление двумерного массива, состоящего из целых чисел с размерностью 5*6: int a[5][6].
В двумерном массиве позиция любого элемента определяется двумя индексами. Если представить двумерный массив в виде таблицы данных, то один индекс означает строку, а второй индекс – столбец. Из этого следует, что если доступ к элементам массива представить в порядке , в котором они реально хранятся в памяти, то правый индекс будет изменяться быстрее , чем левый.