Отчет по алгоритмике

Отчет по алгоритмике. Сортировки

Перов Роман 8.1

Сортировка пузырьком (bubble sort)

Алгоритм:

За каждый проход по массиву элементы сравниваются попарно

Если порядок элементов в паре нарушен, то они меняются местами

Поход по массиву осуществляется N-1 раз, но если все элементы окажутся на своих местах ранее, то повторные проходы больше не нужны

Реализация:

#include

#include

#include

#include

using namespace std;

void rand_in (int A[], int n)

{

int i=0;

while(i

{

A[i]=-10+rand()%20;

cout<

i++;

}

cout<

}

int main()

{

srand(time(NULL));

int n=0;

int t1;

int t2;

cin>>n;

int Array[n];

int l=0;

int i=n-1;

int a=0;

rand_in (Array, n);

t1 = GetTickCount();

while(i>=0)

{

while(l

{

if(Array[l]>Array[+1])

{

a=Array[l];

Array[l]=Array[l+1];

Array[l+1]=a;

}

l=l+1;

}

i—;

l=0;

}

i=0;

t2 = GetTickCount();

while(i

{

cout<

i++;

}

cout<

cout<

}

Сортировка всавками (Insertion sort)

Алгоритм:

Выбираем один из элементов

Находим позицию, где выбранный элемент будет больше предыдущего, но меньше последующего

Вставляем выбранный элемент в данную позицию

Реализация:

#include

#include

#include

#include

#include

using namespace std;

void rand_in (int A[], int n)

{

int i=0;

while(i

{

A[i]=-10+rand()%20;

cout<

i++;

}

cout<

}

int main()

{

srand(time(NULL));

int n=0;

cin>>n;

int Array[n];

rand_in (Array, n);

int i=1;

int l=i-1;

int val=0;

int t1;

int t2;

t1 = GetTickCount();

while(i

{

val=Array[i];

while((l>=0)&&(val

{

Array[l+1]=Array[l];

l—;

}

Array[l+1]=val

;

i++;

l=i-1;

}

i=0;

while(i

{

cout<

i++;

}

t2 = GetTickCount();

cout<

cout<

}

Сортировка выбором (Selection sort)

Алгоритм:

находим номер минимального значения в текущем списке

Производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции)

Теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы

Реализация:

#include

#include

#include

#include

#include

using namespace std;

int minimum(int Array[],int N,int a,int b)

{

int i=0;

int N=0;

i=a;

N=i;

while(i

{

if(Array[i]

{

N=i;

}

i=i+1;

}

return N;

}

void rand_in (int A[], int n)

{

int i=0;

while(i

{

A[i]=-10+rand()%20;

cout<

i++;

}

cout<

}

void Zamena(int Array[],int x,int y)

{

int p=Array[x];

Array[x]=Array[y];

Array[y]=p;

}

int main()

{

int n=0;

cin>>n;

int Array[n];

rand_in (Array, n);

srand(time(NULL));

int t1;

int t2;

t1 = GetTickCount();

for(int i=0;i

{

int a=0;

cout<

int b=n;

while(a

{

int r=minimum(Array,n,a,b);

Zamena(Array,a,r);

a=a+1;

}

for(int i=0;i

{

cout<

}

t2 = GetTickCount();

cout<

return 0;

}

}

Сортировка Расческой

Алгоритм:

Попарно сравниваются все элементы на одном расстоянии друг от друга



Страницы: 1 | 2 | Весь текст


Предыдущий:

Следующий: