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

Необходимо отсортировать массив удовлетворяющий

условию (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].

В двумерном массиве позиция любого элемента определяется двумя индексами. Если представить двумерный массив в виде таблицы данных, то один индекс означает строку, а второй индекс – столбец. Из этого следует, что если доступ к элементам массива представить в порядке , в котором они реально хранятся в памяти, то правый индекс будет изменяться быстрее , чем левый.



Наши рекомендации