C++ сравнение методов сортировки одномерного массива и таймер

[Bitter_Schokolade]

Здравствуйте.
Помогите, пожалуйста, решить задачу по программированию:

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

Начала решать задачу с самой простой сортировки - пузырьковой. Хоть убейте, другие сортировки я не понимаю! (непонятен сам алгоритм). Но на текущий момент проблема даже не в этом.
Дело в том, что я пытаюсь засечь время выполнения пузырьковой сортировки малого массива из 15 элементов. Оно равно нулю. Я пробовала разные способы, но результат такой: либо 0, либо не компилируется.

Программу пишу c помощью Visual Studio.

#include <iostream>
#include <stdio.h>
#include <time.h>

using namespace std;

int main()
{
	int arr_m[15];
	int res = 0;
	clock_t start;
	clock_t stop;
	for (int i = 0; i < 15; ++i)
	{
		arr_m[i] = rand()%15 - 5;
	}
	cout<<"Dannyj massiv:"<<endl;
	for (int i = 0; i < 15; ++i)
	{
		cout<<arr_m[i]<<"; ";
	}
	cout<<endl;
	start = clock();
	for (int i = 1; i < 15; i++) 
	{
		for (int j = 0; j < 15 - i; j++) 
		{
			if (arr_m[j] > arr_m[j + 1])
			{ 
				res = arr_m[j]; 
				arr_m[j] = arr_m[j + 1]; 
				arr_m[j + 1] = res; 
			}
		}
	}
	stop = clock();
	cout<<"Novyj massiv:"<<endl;
	for (int i = 0; i < 15; ++i)
	{
		cout<<arr_m[i]<<"; ";
	}
	cout<<endl;
	long double time = long double ((stop - start) / CLOCKS_PER_SEC);
	cout<<"Vremja sortirovki: "<<time<<endl;
	
	system ("pause");
	return 0;
}

Объясните, пожалуйста, в чем проблема.

[type_Oleg]

Может быть массив маловат. Слишком быстро сортируется, бистрее, чем 1 " клок ".
Чему там у Вас равно CLOCKS_PER_SEC ?
Я C++ почти совсем не знаю. Но чисто ради интереса сравнивал разные методы сортировки на Delphi. Использовал тип TDateTime. Тоже иногда получался 0, приходились один и тот же массив сортировать по многу раз, чтобы получить время.
Например, методом пузырька массив в 10 элементов - 0.0000045 секунд, в 30 элементов - 0.000035, .... в 3000 элементов - 0,32 сек.
Цифры разные получались, даже если постоянно брать тот же массив. От загрузки процессора наверное зависит.

[Bitter_Schokolade]

А пробовала с разными размерностями массива, но результат один. При выводе на экран значений start и stop они оба равны 109.

Только когда я отладку запускаю, тогда у меня ответ получается отличным от нуля.

[Bitter_Schokolade]

Добавила в код сортировку вставками (вроде правильно, могу ошибаться)
Время исполнения сортировки равно нулю в обоих случаях.

#include <iostream>
#include <stdio.h>
#include <time.h>

using namespace std;

void puz_sort (int arr_m[15])
{
	for (int i = 1; i < 15; i++) 
	{
		for (int j = 0; j < 15 - i; j++) 
		{
			if (arr_m[j] > arr_m[j + 1])
			{ 
				int res = arr_m[j]; 
				arr_m[j] = arr_m[j + 1]; 
				arr_m[j + 1] = res; 
			}
		}
	}
}

void vst_sort (int arr_m[15])
{
	for (int i = 1; i < 15; i++)
	{
		int res = arr_m[i];
		for (int j = i-1; j >= 0 && res < arr_m[j] ; j--)
		{
			arr_m[j+1] = arr_m[j];
			arr_m[j+1] = res;
		}
	}

}

int main()
{   
	int arr_m[15];

	for (int i = 0; i < 15; ++i)
	{
		arr_m[i] = rand()%15 - 5;
	}
	cout<<"Dannyj massiv:"<<endl;
	for (int i = 0; i < 15; ++i)
	{
		cout<<arr_m[i]<<"; ";
	}
	cout<<endl;
	clock_t start1 = clock();
	puz_sort(arr_m);
	clock_t stop1 = clock();

	cout<<endl;
	long double time1 = long double (stop1 - start1);
	cout<<"Vremja sortirovki (puz_sort): "<<time1<<endl;

	clock_t start2 = clock();
	vst_sort(arr_m);
	clock_t stop2 = clock();

	cout<<endl;
	long double time2 = long double (stop2 - start2);
	cout<<"Vremja sortirovki (vst_sort): "<<time2<<endl;

	system ("pause");
	return 0;
}

[rlib]

Сообщение от Bitter_Schokolade

Время исполнения сортировки равно нулю в обоих случаях.
[

Вы хотите в секундах отследить сортировку массива разметом 15 байт? )))

Возмите массив в 3 мегабайта, а потом сравнивайте.

[Bitter_Schokolade]

Отсчет в секундах? А в 10^-3 сек как сделать?

[type_Oleg]

Bitter_Schokolade, все таки Вы недооцениваете быстроедействие нонешних компьютеров. Особенно с целочисленными массивами. В то время, когда космические корабли бороздят просторы ...

rlib, 3 Мбайта - это конечно слишком. У сортировки время обычно пропорционально квадрату объема массива.

#include <iostream>
#include <stdio.h>
#include <time.h>
#include <cstdlib>
#define NMAS 1000
using namespace std;

int main()
{
	int arr_m[NMAS];
	int res = 0;
	clock_t start;
	clock_t stop;
	for (int i = 0; i < NMAS; ++i)
	{
		arr_m[i] = rand()%NMAS - 5;
	}
	cout<<"Dannyj massiv:"<<endl;
	for (int i = 0; i < NMAS; ++i)
	{
		cout<<arr_m[i]<<"; ";
	}
	cout<<endl;
	start = clock();
	for (int i = 1; i < NMAS; i++) 
	{
		for (int j = 0; j < NMAS - i; j++) 
		{
			if (arr_m[j] > arr_m[j + 1])
			{ 
				res = arr_m[j]; 
				arr_m[j] = arr_m[j + 1]; 
				arr_m[j + 1] = res; 
			}
		}
	}
	stop = clock();
	cout<<"Novyj massiv:"<<endl;
	for (int i = 0; i < NMAS; ++i)
	{
		cout<<arr_m[i]<<"; ";
	}
	cout<<endl;
	double tim = double(stop - start) / CLOCKS_PER_SEC;  // вот так
	cout<<"Vremja sortirovki: "<<tim<<endl;
	
	system ("pause");
	return 0;
}

Найдите 10 различий.
И результат:

[rlib]

Сообщение от Bitter_Schokolade

Отсчет в секундах? А в 10^-3 сек как сделать?

С помощью АНСИ Ц вам не удасться получить временную резолюцию больше секунды. Смотрите time.h..

Решений 2.
Либо возьмите больший массив, чтобы потратить больше, чем 1 сек на сортировку. Либо пользуйте системные функции (под Винду или Линукс, в зависимости, где запускаете прогу) для большей резолюции по времени.

[Smitt&Wesson]

Вот пользуйтесь. Пример программы сортировки.

// Инициализация таймера замера времени выполнения алгоритма
LARGE_INTEGER freq;
QueryPerformanceFrequency(&freq);
LARGE_INTEGER time1;
QueryPerformanceCounter(&time1);

// Необходимые расчёты

// Снятие показаний таймера
LARGE_INTEGER time2;
QueryPerformanceCounter(&time2);
time2.QuadPart -= time1.QuadPart;
double span = (double) time2.QuadPart / freq.QuadPart;

span = span * pow(10,9);// Результат

Результат в наносекундах.

[type_Oleg]

Кстати, чтобы rand каждый раз выдавала разные значения, надо еще вызывать srand.