Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 13.12.2010, 18:07   #1
Fantom.as
Пользователь
 
Аватар для Fantom.as
 
Регистрация: 19.04.2010
Сообщений: 62
Восклицание Сравнение методов сортировок массивов. Семестровая работа

Пишу семестровую по методам сортировки массивов. В моем варианте метод прямого выбора и метод Шейкера.
Надо сравнить количество перестановок для различного числа элементов массива.
n = 20, 40,60,...,10000.
с-количество сравнений
m-количество перестановок
t-время работы функции сортировки
Сравнение идет на 3 видах массивов почти упорядоченный, плохо упорядоченный и случайный.Я написал программу, но сравнивая результаты получается, что количества сравнений приблизительно равны для разных массивов. Помогите разобраться в чем дело!!! Плиз! И как подсчитать время, чтобы оно более удобно выводилось?
Код:
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <memory.h>
#include <time.h>
#include "sys/timeb.h"
void sort_prv(int* arr, int size, int &m, int &c, double &workTime);
void sort_sheiker(int* arr,int size,int &m, int &c,double &workTime);		
const int maxA=10000;
FILE *f,*f1;
int _tmain(void)
{
	setlocale(LC_ALL,"rus");
	int m,c; //кол-во перестановок и сравнений
	int a[maxA+1],arr[maxA+1];
	int n;
	double t;
	//Сортировка почти упорядоченного массива
	f=fopen("input1.txt","r");					
	for(int i=1; i<=maxA; i++)
	{
		fscanf(f,"%d",&a[i]);
	}
	f1=fopen("output1.1.txt","w");
	fprintf(f1,"n\t\tc\t\tm\t\tt\n");
	printf("Началась сортировка хорошо упорядоченного массива прямым выбором\n");
	for(n=20; n<=maxA; n+=20)
	{
		for (int i=1; i<=n; i++)	arr[i]=a[i];		
		sort_prv(arr,n,m,c,t);		
		fprintf(f1,"%d\t\t%d\t\t%d\t\t%.6f\n",n,c,m,t);
	}
	fclose(f); fclose(f1);
	printf("Закончилась сортировка хорошо упорядоченного массива прямым выбором\n\n");
	//Сортировка плохо упорядоченного массива//
	f=fopen("input2.txt","r");					
	for(int i=1; i<=maxA; i++)					
	{
		fscanf(f,"%d",&a[i]);
	}
	f1=fopen("output2.1.txt","w");
	fprintf(f1,"n\t\tc\t\tm\t\tt\n");
	printf("Началась сортировка плохо упорядоченного массива прямым выбором\n");
	for(n=20; n<=maxA; n+=20)
	{
		for (int i=1; i<=n; i++)	arr[i]=a[i];		
		sort_prv(arr,n,m,c,t);		
		fprintf(f1,"%d\t\t%d\t\t%d\t\t%.6f\n",n,c,m,t);
	}
	fclose(f); fclose(f1);
	printf("Закончилась сортировка плохо упорядоченного массива прямым выбором\n\n");
	//Сортировка рандомно упорядоченного массива
	f=fopen("input3.txt","r");
	for(int i=1; i<=maxA; i++)
	{
		fscanf(f,"%d",&a[i]);
	}
	f1=fopen("output3.1.txt","w");
	fprintf(f1,"n\t\tc\t\tm\t\tt\n");
	printf("Началась сортировка случайно упорядоченного массива прямым выбором\n");
	for(n=20; n<=maxA; n+=20)
	{
		for (int i=1; i<=n; i++)	arr[i]=a[i];		
		sort_prv(arr,n,m,c,t);		
		fprintf(f1,"%d\t\t%d\t\t%d\t\t%.6f\n",n,c,m,t);
	}
	fclose(f); fclose(f1);
	printf("Закончилась сортировка случайно упорядоченного массива прямым выбором\n\n");

	//Сортировка почти упорядоченного массива методом Шейкера
	f=fopen("input1.txt","r");
	for(int i=1; i<=maxA; i++)
	{
		fscanf(f,"%d",&a[i]);
	}
	f1=fopen("output1.2.txt","w");
	fprintf(f1,"n\t\tc\t\tm\t\tt\n");
	printf("Началась сортировка хорошо упорядоченного массива методом шейкера\n");
	for(n=20; n<=maxA; n+=20)
	{
		for (int i=1; i<=n; i++)	arr[i]=a[i];		
		sort_sheiker(arr,n,m,c,t);		
		fprintf(f1,"%d\t\t%d\t\t%d\t\t%.6f\n",n,c,m,t);
	}
	fclose(f); fclose(f1);
	printf("Закончилась сортировка хорошо упорядоченного массива методом шейкера\n");
	//Сортировка плохо упорядоченного массива методом шейкера
	f=fopen("input2.txt","r");
	for(int i=1; i<=maxA; i++)
	{
		fscanf(f,"%d",&a[i]);
	}
	f1=fopen("output2.2.txt","w");
	fprintf(f1,"n\t\tc\t\tm\t\tt\n");
	printf("Началась сортировка плохо упорядоченного массива методом шейкера\n");
	for(n=20; n<=maxA; n+=20)
	{
		for (int i=1; i<=n; i++)	arr[i]=a[i];		
		sort_sheiker(arr,n,m,c,t);	
		fprintf(f1,"%d\t\t%d\t\t%d\t\t%.6f\n",n,c,m,t);
	}
	fclose(f); fclose(f1);
	printf("Закончилась сортировка плохо упорядоченного массива методом шейкера\n");
	//Сортировка рандомно упорядоченного массива методом шейкера
	f=fopen("input3.txt","r");
	for(int i=1; i<=maxA; i++)
	{
		fscanf(f,"%d",&a[i]);
	}
	f1=fopen("output3.2.txt","w");
	fprintf(f1,"n\t\tc\t\tm\t\tt\n");
	printf("Началась сортировка случайно упорядоченного массива методом шейкера\n");
	for(n=20; n<=maxA; n+=20)
	{
		for (int i=1; i<=n; i++)	arr[i]=a[i];		
		sort_sheiker(arr,n,m,c,t);	
		fprintf(f1,"%d\t\t%d\t\t%d\t\t%.6f\n",n,c,m,t);
	}
	fclose(f); fclose(f1);
	printf("Закончилась сортировка случайно упорядоченного массива методом шейкера\n");
	return 0;
}
<--<--<--Нажми на весы слева <---<---<---
Fantom.as вне форума Ответить с цитированием
Старый 13.12.2010, 18:08   #2
Fantom.as
Пользователь
 
Аватар для Fantom.as
 
Регистрация: 19.04.2010
Сообщений: 62
По умолчанию

функции сортировок пишу отдельно, т.к. количество символов превышено
Код:
//метод прямого выбора
void sort_prv(int *arr, int size, int &m, int &c, double &workTime)
{
	clock_t start,finish;
	start=clock();
	int i,k,b;
	int min;
	//количество пересылок и сравнений
	m=0; c=0;
	//проходимся по массиву с 0
	
	for (i=1; i<size; i++)
	{	min=i;
		//проходимся с и до конца массива и ищем минимальный
		//при этом запоминаем количество пересылок и сравнений
		for (k=i+1; k<=size; k++)
		{	c++;
			if (arr[k]<arr[min]) min=k;
		}
		if (min!=i)
		{	b=arr[i]; arr[i]=arr[min]; arr[min]=b;
			m++;
		} }
	finish=clock();
	workTime=(double)(finish - start) / CLOCKS_PER_SEC;
 }
//метод Щейкера
void sort_sheiker(int* arr,int size,int &m, int &c,double &workTime)
{	
	clock_t start,finish;
	start=clock();
	int i,k,b;
	m=0; c=0;
	int l=1;
	int r=size-1; k=size-1;
	do
	{	for (i=r; i>=l; i--)		//идем вверх по массиву
		{	c++;
			if (arr[i-1]>arr[i])		//сравниваем элемент по весу с соседним верхним
			{
			   b=arr[i]; arr[i]=arr[i-1]; arr[i-1]=b; k=i; m++;	//двигаем легкий элемент по массиву вверх
			} }
		l=k+1;	//верхняя граница - выше которой алгоритм не поднимется проверять элементы
		for (i=l; i<=r; i++)	//меняем направление - вниз
		{	c++;
			if (arr[i-1]>arr[i])		//сравниваем элемент по весу с соседним нижним
			{
			   b=arr[i-1]; arr[i-1]=arr[i]; arr[i]=b; k=i; m++;	//двигаем тяжелый элемент по массиву вниз
			} }
		r=k-1;	//нижняя граница - ниже которой алгоритм не опускается проверять элементы
	}
	while (r>=l);
	finish=clock();
	workTime=(double)(finish - start) / CLOCKS_PER_SEC;
	}
<--<--<--Нажми на весы слева <---<---<---
Fantom.as вне форума Ответить с цитированием
Старый 16.12.2010, 12:03   #3
Fantom.as
Пользователь
 
Аватар для Fantom.as
 
Регистрация: 19.04.2010
Сообщений: 62
По умолчанию

Вопрос уже решен, тему можно удалить или закрыть!
<--<--<--Нажми на весы слева <---<---<---
Fantom.as вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
сравнение массивов nik1905 Microsoft Office Excel 3 13.12.2010 13:53
паскаль, сравнение сортировок Хоара и пузырька semak Помощь студентам 0 01.12.2010 10:57
Сравнение сортировок Паскаль Igomax Помощь студентам 6 24.10.2009 17:58
сравнительный анализ различных методов сортировки целочисленных массивов Freak Помощь студентам 2 05.05.2008 12:37