Сравнение работы Быстрой сортировки и Сортировки выбором

Министерство образования и науки РФ
ФГАОУ ВПО «УрФУ им. первого Президента России Б.Н.Ельцина»
Кафедра информационных технологий и автоматизации проектирования.








ЛАБОРАТОРНАЯ РАБОТА №14
по дисциплине «Программирование»
«Сравнение работы Быстрой сортировки и Сортировки выбором»






Выполнили
Студенты:
Группа: ММ-130702
Преподаватель:














Екатеринбург
2014
1. Формулировка задания.
Для различного числа элементов n массива А найти время, за которое будут произведены сортировки sort1, sort2, sort3 для 15 элементов и sort2, sort3 для 25 элементов. Количество элементов массива увеличиваются по геометрической прогрессии n0=25, nj=2n, j={1…24}.
sort1 - Сортировка выбором.
sort2 - Быстрая сортировка, где в качестве опорного элемента берется средний элемент массива.
sort3 - Быстрая сортировка, где в качестве опорного элемента берется случайный элемент массива.
Полученные данные записать в текстовый файл Test1 в виде таблицы.

2. Блок-схема алгоритма.
Сортировка выбором(std_sort)




































Быстрая сортировка(hoar_sort)


















































void main(void)






















































































3. Текст программ.

#include <stdio.h>
#include <malloc.h>
#include <time.h>
#include <stdlib.h>
void std_sort(int *x, int n);
void hoar_sort(int *x, int left, int right);
void hoar_sort2(int *x, int left, int right, int n);
void main(void)
{
clock_t start, end;
FILE *fout;
long t;
int *A,i, j, n;
system("cls");
fout=fopen("c:\Test1.txt", "w");
fprintf(fout, " n sort1 sort2 sort3");
for (n = 25, j = 0; j<25; j++, n = n *= 2)
{
srand(time(NULL));
fprintf(fout, "
%10d", n);
A = (int *)malloc(n*sizeof(int));
for (i = 0; i<n; i++)
*(A + i) = rand();
start = clock();
hoar_sort(A, 0, n - 1);
end = clock();
fprintf(fout," %12.5e", (float)(end - start) / CLOCKS_PER_SEC);
free(A);

A = (int *)malloc(n*sizeof(int));
for (i = 0; i<n; i++)
*(A + i) = rand();
start = clock();
hoar_sort2(A, 0, n - 1, n);
end = clock();
fprintf(fout, " %12.5e", (float)(end - start) / CLOCKS_PER_SEC);
free(A);

if (j < 15)
{
A = (int *)malloc(n*sizeof(int));
for (i = 0; i<n; i++)
*(A + i) = rand();
start = clock();
std_sort(A, n);
end = clock();
fprintf(fout," %12.5e", (float)(end - start) / CLOCKS_PER_SEC);
free(A);
}
else
fprintf(fout, " limit");

}
}

void std_sort(int *x, int n)
{
int x_min, i, k, j;
x_min = *x;
k = 0;
for (i = 0; i<n - 1; i++)
{
x_min = *(x + i);
k = i;
for (j = i + 1; j<n; j++)
if (*(x + j)<x_min)
{
x_min = *(x + j);
k = j;
}
*(x + k) = *(x + i);
*(x + i) = x_min;
}
}

void hoar_sort(int *x, int left, int right)
{
int i, j, p, tmp;
i = left;
j = right;
p = x[(left + right) / 2];
do
{
while (*(x + i)<p)
i++;
while (*(x + j)>p)
j--;
if (i <= j)
{
if (i<j)
{
tmp = *(x + i);
*(x + i) = *(x + j);
*(x + j) = tmp;
}
i++;
j--;
}
} while (i <= j);
if (left<j)
hoar_sort(x, left, j);
if (i<right)
hoar_sort(x, i, right);
}

void hoar_sort2(int *x, int left, int right, int n)
{
int i, j, p, tmp;
i = left;
j = right;
p = x[(left + right) / 2];
do
{
while (*(x + i)<p)
i++;
while (*(x + j)>p)
j--;
if (i <= j)
{
if (i<j)
{
tmp = *(x + i);
*(x + i) = *(x + j);
*(x + j) = tmp;
}
i++;
j--;
}
} while (i <= j);
if (left<j)
hoar_sort(x, left, j);
if (i<right)
hoar_sort(x, i, right);
}




















4. Результат.