Анализ скорости работы алгоритмов сортировки. Лабораторная18.ОАиП.211-721.Захарова.О.Н. Московский политехнический университет высшая школа печати и медиаиндустрии

• Название: Московский политехнический университет высшая школа печати и медиаиндустрии
• Анкор: Анализ скорости работы алгоритмов сортировки
• Дата: 10.01.2022
• Размер: 1.22 Mb.
• Имя файла: Лабораторная18.ОАиП.211-721.Захарова.О.Н.doc
• Тип: Лабораторная работа; #326920

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ




МОСКОВСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ВЫСШАЯ ШКОЛА ПЕЧАТИ И МЕДИАИНДУСТРИИ
Институт Принтмедиа и информационных технологий

Кафедра Информатики и информационных технологий


направление подготовки

09.03.02 «Информационные системы и технологии»

ЛАБОРАТОРНАЯ РАБОТА № 18
Дисциплина: Основы алгоритмизации и программирования

____________________________________________________________________

Тема: "Алгоритм сортировки «Быстрая»"

__________________________________________________________________
Выполнил(а): студент(ка) группы 211-721
Захарова О. Н.

(Фамилия И.О.)


Дата, подпись ________________ __зах_

(Дата) (Подпись)

Проверил: _________________________ ___________

(Фамилия И.О., степень, звание) (Оценка)

Дата, подпись ________________ ___________

(Дата) (Подпись)
Замечания:

Москва

2020
Цель: Получить практические навыки разработке алгоритмов и их программной реализации.

Задачи:

1. 
   Представить ранее рассмотренные алгоритмы (лабораторные 2-17)
   
2. 
   Выполнить анализ сложности каждого из алгоритмов.
   

Сортировка «Пузырьком»

#include

#include

using namespace std;
int main(){

int size, i, j, k;

double tm;

for (size = 100; tm < 60; size = size*1.27){

int mas[size];

for (k = 0; k < size; k++) mas[k]=rand()%1000;

clock_t begin = clock();

for (j=0; j
for (k=0; k
if (mas[k]>mas[k+1]){

i=mas[k+1];

mas[k+1]=mas[k];

mas[k]=i;

}

}

}

clock_t end = clock();

tm = (double)(end - begin) / CLOCKS_PER_SEC;

cout << "Массив из " << size << " элементов сортировался " << tm << " секунд." << endl;

}

return 0;

}
Сложность алгоритма: O(_{ }

Сортировка «Расчёска»

#include

#include

using namespace std;
int main()

{

int size, i, j;

double tm;

for (size = 100; tm < 60; size = size*1.27){

int m[size];

for (j = 0; j < size; j++) m[j]=rand()%1000;

clock_t begin = clock();

i=0; int step=size-1; float k=1.247;

while (step>=1){

for (i=0; i
if (m[i]>m[i+step]){

m[i]=m[i]+m[i+step];

m[i+step]=m[i]-m[i+step];

m[i]=m[i]-m[i+step];

}

}

step=step/k;

}
clock_t end = clock();

tm = (double)(end - begin) / CLOCKS_PER_SEC;

cout << size << " " << tm << endl;

}

return 0;

}

Сложность алгоритма:

Худшее время: O(_{ }

Лучшее время: O(_{ })

Сортировка «Вставками»

#include

#include

using namespace std;
int main()

{

int size, i, j, buf;

double tm;

for (size = 100; tm < 60; size = size*1.27){

int m[size];

for (j = 0; j < size; j++) m[j]=rand()%1000;

clock_t begin = clock();

i=0; int step=size-1;

for (i = 1; i < size; i++) {

for (j = i, buf = m[i]; (j > 0) and (m[j - 1] > buf); j--) {

m[j] = m[j - 1];

}

m[j] = buf;

}

clock_t end = clock();

tm = (double)(end - begin) / CLOCKS_PER_SEC;

cout << size << " " << tm << endl;

}

return 0;

}

Сложность алгоритма:

Время работы: O(_{ }

Сортировка «Шелла»

#include

#include

using namespace std;
int main(){

int size, i, j, buf;

double tm;

for (size = 100; tm < 60; size = size*1.27){

int m[size];

for (j = 0; j < size; j++) m[j]=rand()%1000;

clock_t begin = clock();

for (int d=size/2; d>0; d /= 2){

for (i=d; i
buf = m[i];

for (j=i; j>=d; j-=d){

if (buf < m[j-d]){

m[j]=m[j-d];

}

else{

break;

}

}

m[j]=buf;

}

}


clock_t end = clock();

tm = (double)(end - begin) / CLOCKS_PER_SEC;

cout << size << " " << tm << endl;

}

return 0;

}

Сложность алгоритма:

Худшее время: O(_{ }

Лучшее время: O(_{ })

Сортировка «Выбором»

#include

#include

using namespace std;
int main()

{

int n, i, j, buf;

double tm;

for (n = 100; tm < 60; n = n*1.27){

int a[n];

for (j = 0; j < n; j++) a[j]=rand()%1000;

clock_t begin = clock();

int min;

for (i=0; i
for (j=i+1, min=i; j
if (a[j]< a[min]) min = j;

}

buf = a[i];

a[i] = a[min];

a[min] = buf;

}

clock_t end = clock();

tm = (double)(end - begin) / CLOCKS_PER_SEC;

cout << n << " " << tm << endl;

}

return 0;

}

Сложность алгоритма:

Время работы: O(_{ }


Сортировка «Гномья»

#include

#include

using namespace std;
int main()

{

int n, i, j;

double tm;

for (n = 100; tm < 60; n = n*1.27){

int a[n];

for (j = 0; j < n; j++) a[j]=rand()%1000;

clock_t begin = clock();

i=1; j=2; int buf;

while (i
{

if (a[i-1]>a[i])

{

buf=a[i];

a[i]=a[i-1];

a[i-1]=buf;

i--;

if (i>0) continue;

}

i=j++;

}

clock_t end = clock();

tm = (double)(end - begin) / CLOCKS_PER_SEC;

cout << n << " " << tm << endl;

}

return 0;

}

Сложность алгоритма:

Время работы: O(_{ }


Сортировка «Быстрая»

#include

#include

using namespace std;

void quickSort(int *arr, int b, int e){

int l = b, r = e, piv = arr[(b + e) / 2];

while (l <= r) {

while (arr[l] < piv)

l++;

while (arr[r] > piv)

r--;

if (l <= r){

int t = arr[l];

arr[l] = arr[r];

arr[r] = t;

l++;

r--;

}

}

if (b < r)

quickSort(arr, b, r);

if (l < e)

quickSort(arr, l, e);

}

int main(){

int n, i, j;

double tm;

for (n = 100; tm < 60; n = n*1.27){

int a[n];

for (j = 0; j < n; j++) a[j]=rand()%1000;

clock_t begin = clock();

quickSort(a, 0, n - 1);

clock_t end = clock();

tm = (double)(end - begin) / CLOCKS_PER_SEC;

cout << n << " " << tm << endl;

}

return 0;}

Сложность алгоритма:

Худшее время: O(_{ }

Среднее время: O(_{ })

Лучшее время: : O(_{ })