|
Re: sorting algorithms
Quote:
|
Originally Posted by xlonehats
thanx very much...the importing works now
jst another thing.....i want to find the average time taken for each set of data input.....a friend has suggested that i should loop that particular sorting code and get the average....
start clock
for(int i=0;i<5;i++)
merge_sort(............)
end clock
then divide
im not sure whether it would give me an accurate average because after the
first loop the data in my array is already sorted...!!!!! any ideas
in my array i use random no. till 10000 or higher to get a decent time
i can get average simply by generating another set of same no. of data in another array and sorting it...and then calculating average but this would mean a lot of repeating codes.....any ideas
|
I used the same array for each test in my own coded effort...and made a copy before invoking each sorting algorithm. I did not include the cost of copying in my timing. This allowed me to use the "same unsorted" array over and over again.
My code, which is nothing more than a quick hack, initializes an array of some user-specified size to the counting numbers of 1 to array elements + 1. Then I used std::random_shuffle to "mix up" the content of the array. I created interfaces to the sorting algorithms that required each of the arrays to be const. This was to ensure that my "original, mixed-up" array wasn't mutated by the individual sorting algorithms.
In order for these sorting algorithms to work properly, since they each mutate the contents of the array, I made a copy of the array and sorted it rather than the original array. I only timed the time that it takes to make the call (and return from it) to the particular sorting algo.
Here is the code that I used. You'll note that the "PerfTimer" class is yet another quickly hacked together example of producing some performance timing. Note that you can easily reimplement its interfaces using Win32-specific functionality and test on Windoze.
perf.cpp
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
#include <sorting_algorithms.h>
#include <PerfTimer.h>
void spew_array( int const* array, const int array_size )
{
for( int i = 0; i < array_size; i++ )
{
cout << array[i] << endl;
}
}
float test_bubble_sort( int const* array, int array_size )
{
int* copy_of_array = new int[array_size];
memcpy( copy_of_array, array, array_size * sizeof( int ) );
PerfTimer* pt = PerfTimer::instance();
pt->start();
bubble_sort( copy_of_array, array_size );
float f = pt->stop();
delete [] copy_of_array;
return f;
}
float test_heap_sort( int const* array, int array_size )
{
int* copy_of_array = new int[array_size];
memcpy( copy_of_array, array, array_size * sizeof( int ) );
PerfTimer* pt = PerfTimer::instance();
pt->start();
heap_sort( copy_of_array, array_size );
float f = pt->stop();
delete [] copy_of_array;
return f;
}
float test_insertion_sort( int const* array, int array_size )
{
int* copy_of_array = new int[array_size];
memcpy( copy_of_array, array, array_size * sizeof( int ) );
PerfTimer* pt = PerfTimer::instance();
pt->start();
insertion_sort( copy_of_array, array_size );
float f = pt->stop();
delete [] copy_of_array;
return f;
}
float test_merge_sort( int const* array, int array_size )
{
int* copy_of_array = new int[array_size];
memcpy( copy_of_array, array, array_size * sizeof( int ) );
int* temp_array = new int[array_size];
PerfTimer* pt = PerfTimer::instance();
pt->start();
merge_sort( copy_of_array, temp_array, array_size );
float f = pt->stop();
delete [] copy_of_array;
delete [] temp_array;
return f;
}
float test_quick_sort( int const* array, int array_size )
{
int* copy_of_array = new int[array_size];
memcpy( copy_of_array, array, array_size * sizeof( int ) );
PerfTimer* pt = PerfTimer::instance();
pt->start();
quick_sort( copy_of_array, array_size );
float f = pt->stop();
delete [] copy_of_array;
return f;
}
float test_selection_sort( int const* array, int array_size )
{
int* copy_of_array = new int[array_size];
memcpy( copy_of_array, array, array_size * sizeof( int ) );
PerfTimer* pt = PerfTimer::instance();
pt->start();
selection_sort( copy_of_array, array_size );
float f = pt->stop();
delete [] copy_of_array;
return f;
}
float test_shell_sort( int const* array, int array_size )
{
int* copy_of_array = new int[array_size];
memcpy( copy_of_array, array, array_size * sizeof( int ) );
PerfTimer* pt = PerfTimer::instance();
pt->start();
shell_sort( copy_of_array, array_size );
float f = pt->stop();
delete [] copy_of_array;
return f;
}
int main()
{
cout << "Enter the number of elements: ";
int elements = 0;
cin >> elements;
int* array = (int*)new int[elements];
for( int i = 0; i < elements; i++ )
{
array[i] = i + 1;
}
srand( time(0) );
random_shuffle( array, array + elements );
// uncomment the next line to view result of randomization of the array
//spew_array( array, elements );
cout << setiosflags( ios::fixed | ios::showpoint ) << setprecision( 6 );
cout << "bubble," << elements << "," << test_bubble_sort( array, elements ) << endl;
cout << "heap," << elements << "," << test_heap_sort( array, elements ) << endl;
cout << "insertion," << elements << "," << test_insertion_sort( array, elements ) << endl;
cout << "merge," << elements << "," << test_merge_sort( array, elements ) << endl;
cout << "quick," << elements << "," << test_quick_sort( array, elements ) << endl;
cout << "selection," << elements << "," << test_selection_sort( array, elements ) << endl;
cout << "shell," << elements << "," << test_shell_sort( array, elements ) << endl;
delete [] array;
return 0;
}
PerfTimer.h
#ifndef _PerfTimer_h_
#define _PerfTimer_h_
#include <sys/time.h>
class PerfTimer* g_instance;
class PerfTimer
{
public:
static PerfTimer* instance()
{
if( !g_instance )
{
g_instance = new PerfTimer();
}
return g_instance;
}
void start()
{
gettimeofday( &m_last, NULL );
}
float elapsed()
{
timeval result;
gettimeofday( &m_now, NULL );
timersub( &m_now, &m_last, &result );
float elapsed_time = result.tv_sec + (1.0e-6 * result.tv_usec);
return elapsed_time;
}
float stop()
{
return elapsed();
}
protected:
private:
struct timeval m_now;
struct timeval m_last;
PerfTimer()
{
}
};
#endif // ! _PerfTimer_h_
sorting_algorithms.h
#ifndef _sorting_algorithms_h_
#define _sorting_algorithms_h_
#ifdef __cplusplus
extern "C"
{
#endif
void bubble_sort( int numbers[], int array_size );
void heap_sort( int numbers[], int array_size );
void insertion_sort( int numbers[], int array_size );
void merge_sort( int numbers[], int temp[], int array_size );
void quick_sort( int numbers[], int array_size );
void selection_sort( int numbers[], int array_size );
void shell_sort( int numbers[], int array_size );
#ifdef __cplusplus
}
#endif
#endif /* _sorting_algorithms_h_ */
sorting_algorithms.c
#include <sorting_algorithms.h>
void bubble_sort( int numbers[], int array_size )
{
int i, j, temp;
for( i = (array_size - 1); i >= 0; i-- )
{
for( j = 1; j <= i; j++ )
{
if( numbers[j-1] > numbers[j] )
{
temp = numbers[j-1];
numbers[j-1] = numbers[j];
numbers[j] = temp;
}
}
}
}
void sift_down( int numbers[], int root, int bottom )
{
int done, maxChild, temp;
done = 0;
while( (root*2 <= bottom) && (!done) )
{
if( root*2 == bottom )
{
maxChild = root * 2;
}
else if( numbers[root * 2] > numbers[root * 2 + 1] )
{
maxChild = root * 2;
}
else
{
maxChild = root * 2 + 1;
}
if( numbers[root] < numbers[maxChild] )
{
temp = numbers[root];
numbers[root] = numbers[maxChild];
numbers[maxChild] = temp;
root = maxChild;
}
else
{
done = 1;
}
}
}
void heap_sort( int numbers[], int array_size )
{
int i, temp;
for( i = (array_size / 2)-1; i >= 0; i-- )
{
sift_down(numbers, i, array_size);
}
for( i = array_size-1; i >= 1; i-- )
{
temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
sift_down(numbers, 0, i-1);
}
}
void insertion_sort( int numbers[], int array_size )
{
int i, j, index;
for( i=1; i < array_size; i++ )
{
index = numbers[i];
j = i;
while( (j > 0) && (numbers[j-1] > index) )
{
numbers[j] = numbers[j-1];
j = j - 1;
}
numbers[j] = index;
}
}
void merge( int numbers[], int temp[], int left, int mid, int right )
{
int i, left_end, num_elements, tmp_pos;
left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
while( (left <= left_end) && (mid <= right) )
{
if( numbers[left] <= numbers[mid] )
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
while( left <= left_end )
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while( mid <= right )
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
for( i=0; i <= num_elements; i++ )
{
numbers[right] = temp[right];
right = right - 1;
}
}
void m_sort( int numbers[], int temp[], int left, int right )
{
int mid;
if( right > left )
{
mid = (right + left) / 2;
m_sort( numbers, temp, left, mid );
m_sort( numbers, temp, mid+1, right );
merge( numbers, temp, left, mid+1, right );
}
}
void merge_sort( int numbers[], int temp[], int array_size )
{
m_sort( numbers, temp, 0, array_size - 1 );
}
void q_sort(int numbers[], int left, int right)
{
int pivot, l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = numbers[left];
while( left < right )
{
while( (numbers[right] >= pivot) && (left < right) )
{
right--;
}
if( left != right )
{
numbers[left] = numbers[right];
left++;
}
while( (numbers[left] <= pivot) && (left < right) )
{
left++;
}
if( left != right )
{
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if( left < pivot )
{
q_sort( numbers, left, pivot - 1 );
}
if( right > pivot )
{
q_sort( numbers, pivot + 1, right );
}
}
void quick_sort( int numbers[], int array_size )
{
q_sort( numbers, 0, array_size - 1 );
}
void selection_sort( int numbers[], int array_size )
{
int i, j;
int min, temp;
for( i = 0; i < array_size - 1; i++ )
{
min = i;
for( j = i+1; j < array_size; j++ )
{
if( numbers[j] < numbers[min] )
{
min = j;
}
}
temp = numbers[i];
numbers[i] = numbers[min];
numbers[min] = temp;
}
}
void shell_sort( int numbers[], int array_size )
{
int i, j, increment, temp;
increment = 3;
while( increment > 0 )
{
for( i=0; i < array_size; i++ )
{
j = i;
temp = numbers[i];
while( (j >= increment) && (numbers[j-increment] > temp) )
{
numbers[j] = numbers[j - increment];
j = j - increment;
}
numbers[j] = temp;
}
if( increment/2 != 0 )
{
increment = increment/2;
}
else if( increment == 1 )
{
increment = 0;
}
else
{
increment = 1;
}
}
}
Output:
Code:
Enter the number of elements: 100000
bubble,100000,20.307362
heap,100000,0.013039
insertion,100000,2.099443
merge,100000,0.017994
quick,100000,0.009736
selection,100000,4.463685
shell,100000,1.698534
...using a: Intel(R) Core(TM)2 CPU 6600 @ 2.40GHz
Note that I wrote my interfaces to the performance testing such that they return the elapsed time for the sorting algorithm call. Therefore, it would be easy (trivial) to modify this code to support averaging the sorts over a period of some number of iterations. Here is an example:
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
#include <sorting_algorithms.h>
#include <PerfTimer.h>
void spew_array( int const* array, const int array_size )
{
for( int i = 0; i < array_size; i++ )
{
cout << array[i] << endl;
}
}
float test_bubble_sort( int const* array, int array_size )
{
int* copy_of_array = new int[array_size];
memcpy( copy_of_array, array, array_size * sizeof( int ) );
PerfTimer* pt = PerfTimer::instance();
pt->start();
bubble_sort( copy_of_array, array_size );
float f = pt->stop();
delete [] copy_of_array;
return f;
}
float test_heap_sort( int const* array, int array_size )
{
int* copy_of_array = new int[array_size];
memcpy( copy_of_array, array, array_size * sizeof( int ) );
PerfTimer* pt = PerfTimer::instance();
pt->start();
heap_sort( copy_of_array, array_size );
float f = pt->stop();
delete [] copy_of_array;
return f;
}
float test_insertion_sort( int const* array, int array_size )
{
int* copy_of_array = new int[array_size];
memcpy( copy_of_array, array, array_size * sizeof( int ) );
PerfTimer* pt = PerfTimer::instance();
pt->start();
insertion_sort( copy_of_array, array_size );
float f = pt->stop();
delete [] copy_of_array;
return f;
}
float test_merge_sort( int const* array, int array_size )
{
int* copy_of_array = new int[array_size];
memcpy( copy_of_array, array, array_size * sizeof( int ) );
int* temp_array = new int[array_size];
PerfTimer* pt = PerfTimer::instance();
pt->start();
merge_sort( copy_of_array, temp_array, array_size );
float f = pt->stop();
delete [] copy_of_array;
delete [] temp_array;
return f;
}
float test_quick_sort( int const* array, int array_size )
{
int* copy_of_array = new int[array_size];
memcpy( copy_of_array, array, array_size * sizeof( int ) );
PerfTimer* pt = PerfTimer::instance();
pt->start();
quick_sort( copy_of_array, array_size );
float f = pt->stop();
delete [] copy_of_array;
return f;
}
float test_selection_sort( int const* array, int array_size )
{
int* copy_of_array = new int[array_size];
memcpy( copy_of_array, array, array_size * sizeof( int ) );
PerfTimer* pt = PerfTimer::instance();
pt->start();
selection_sort( copy_of_array, array_size );
float f = pt->stop();
delete [] copy_of_array;
return f;
}
float test_shell_sort( int const* array, int array_size )
{
int* copy_of_array = new int[array_size];
memcpy( copy_of_array, array, array_size * sizeof( int ) );
PerfTimer* pt = PerfTimer::instance();
pt->start();
shell_sort( copy_of_array, array_size );
float f = pt->stop();
delete [] copy_of_array;
return f;
}
int main()
{
cout << "Enter the number of elements: ";
int elements = 0;
cin >> elements;
int* array = (int*)new int[elements];
for( int i = 0; i < elements; i++ )
{
array[i] = i + 1;
}
srand( time(0) );
random_shuffle( array, array + elements );
// uncomment the next line to view result of randomization of the array
//spew_array( array, elements );
cout << setiosflags( ios::fixed | ios::showpoint ) << setprecision( 6 );
int iterations = 0;
cout << "Enter the number of iterations (may take a long time with a lot of elements & iterations!): ";
cin >> iterations;
float bubble_result = 0.0F;
float heap_result = 0.0F;
float insertion_result = 0.0F;
float merge_result = 0.0F;
float quick_result = 0.0F;
float selection_result = 0.0F;
float shell_result = 0.0F;
for( int i = 0; i < iterations; i++ )
{
bubble_result += test_bubble_sort( array, elements );
heap_result += test_heap_sort( array, elements );
insertion_result += test_insertion_sort( array, elements );
merge_result += test_merge_sort( array, elements );
quick_result += test_quick_sort( array, elements );
selection_result += test_selection_sort( array, elements );
shell_result += test_shell_sort( array, elements );
}
cout << "bubble," << elements << "," << iterations << "," << bubble_result/iterations << endl;
cout << "heap," << elements << "," << iterations << "," << heap_result/iterations << endl;
cout << "insertion," << elements << "," << iterations << "," << insertion_result/iterations << endl;
cout << "merge," << elements << "," << iterations << "," << merge_result/iterations << endl;
cout << "quick," << elements << "," << iterations << "," << quick_result/iterations << endl;
cout << "selection," << elements << "," << iterations << "," << selection_result/iterations << endl;
cout << "shell," << elements << "," << iterations << "," << shell_result/iterations << endl;
delete [] array;
return 0;
}
Output:
Code:
Enter the number of elements: 10000
Enter the number of iterations (may take a long time with a lot of elements & iterations!): 100
bubble,10000,100,0.206015
heap,10000,100,0.001024
insertion,10000,100,0.021924
merge,10000,100,0.001537
quick,10000,100,0.000854
selection,10000,100,0.045961
shell,10000,100,0.018120
:davis: |
03-Sep-2007, 08:49
Meeting the populace by crystalattice
Similar Threads
