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

Лабораторная работа по предмету «Программирование»
Информация о работе
  • Тема: Сравнение работы Быстрой сортировки и Сортировки выбором
  • Количество скачиваний: 3
  • Тип: Лабораторная работа
  • Предмет: Программирование
  • Количество страниц: 9
  • Язык работы: Русский язык
  • Дата загрузки: 2014-11-26 12:33:41
  • Размер файла: 35.71 кб
Помогла работа? Поделись ссылкой
Ссылка на страницу (выберите нужный вариант)
  • Сравнение работы Быстрой сортировки и Сортировки выбором [Электронный ресурс]. – URL: https://www.sesiya.ru/laboratornaya-rabota/programmirovanie/sravnenie-raboty-bystroy-sortirovki-i-sortirovki-vyborom/ (дата обращения: 25.06.2021).
  • Сравнение работы Быстрой сортировки и Сортировки выбором // https://www.sesiya.ru/laboratornaya-rabota/programmirovanie/sravnenie-raboty-bystroy-sortirovki-i-sortirovki-vyborom/.
Есть ненужная работа?

Добавь её на сайт, помоги студентам и школьникам выполнять работы самостоятельно

добавить работу
Обратиться за помощью в подготовке работы

Заполнение формы не обязывает Вас к заказу

Информация о документе

Документ предоставляется как есть, мы не несем ответственности, за правильность представленной в нём информации. Используя информацию для подготовки своей работы необходимо помнить, что текст работы может быть устаревшим, работа может не пройти проверку на заимствования.

Если Вы являетесь автором текста представленного на данной странице и не хотите чтобы он был размешён на нашем сайте напишите об этом перейдя по ссылке: «Правообладателям»

Можно ли скачать документ с работой

Да, скачать документ можно бесплатно, без регистрации перейдя по ссылке:

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








ЛАБОРАТОРНАЯ РАБОТА №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. Результат.