Ok:
1) I added counts to the for and while loops. So i should be counting every operation now.
*Note: My instructor did an example with a different sort, and i tried to match the placements of the counts in my program with his (ex: counts inside for and while loops).
2) I now have three sets of numbers that are the number of operations it takes to sort: A) A randomly generated array B) An already sorted array C) Reverse Sorted Array.
Output is as follows:
Code:
size a b c
1 2 2 2
2 12 10 10
3 18 15 15
4 40 33 33
5 54 43 49
6 66 48 57
7 82 58 67
8 99 63 75
9 113 73 85
10 162 121 133
20 371 236 290
30 727 494 623
40 993 644 809
70 2233 1472 1859
100 3466 2082 2673
200 8066 5125 5980
300 14062 9178 11401
500 24682 15263 19127
1000 57107 35476 40663
2000 128925 80899 92179
5000 371277 227157 283188
Do these values seem correct? The running times of the reverse sorted array are generally less than the randomly sorted array.
This could be possible i guess, depending on the nature of the sort, but it seems odd. I read how this sorting algorithm works, but i didn't fully understand it.
On the examples we did in class, the reverse sort arrays always took more operations.
As for making a class to count the number of operations.
This was how my instructor counted his sorting algorithm (probably for simplicity since he was doing it in class).
So, i tired to follow his example, since i don't have much experience programming.
Thanks for the help.
Here is my code if needed:
*Note: I have a printing function that i used to test if the arrays were sorted correctly.
When i would shrink the number and size of the arrays to say...11 and 40 instead of 21 and 5000, they seemed to be sorted correctly.
When i changed back the number and size of the arrays back to 21 and 5000, i suppose something could have gone wrong.
Code:
#include <iostream>
#include <time.h>
using namespace std;
void fill_array(int A[], int size);
int shell_sort(int A[], int size);
void print_array(int A[], int size);
int main()
{
const int size = 5000;
int A [size];
int B [21] = {1,2,3,4,5,6,7,8,9,10,20,30,40,70,100,200,300,500,1000,2000,5000};
int C [size];
int new_size = 0;
srand ((unsigned int)time((time_t)0));
cout<<"Randomly Generated:"<<endl;
for (int i = 0; i < 21; i++)
{
int sum = 0;
for(int j = 0; j <= 30; j++)
{
new_size = B[i];
fill_array(A, new_size);
sum+= shell_sort(A, new_size);
}
cout.width(4);
cout<<sum/30<<endl;
//new_size<<": "<<sum/30<<endl;
}
cout<<endl<<"Sorted:"<<endl;
for (int k = 0; k < 21; k++)
{
new_size = B[k];
cout.width(4);
//cout<<new_size<<": "
cout<<shell_sort(A, new_size)<<endl;
}
cout<<endl<<"Reverse Sorted:"<<endl;
for( int m = 0; m < 5001; m++)
{
C[m] = A[4999-m];
}
for (int l = 0; l < 21; l++)
{
new_size = B[l];
cout.width(4);
//cout<<new_size<<": "
cout<<shell_sort(C, new_size)<<endl;
}
//print_array(C, size);
return 0;
}
int shell_sort(int A[], int size)
{
int count = 0 ;
int i, j, increment, temp;
increment = size / 2; ++count;
while (++count && increment > 0)
{
for (i = increment; ++count && i < size; i++)
{
j = i; ++count;
temp = A[i]; ++count;
while (++count &&(j >= increment) && (A[j-increment] > temp))
{
A[j] = A[j - increment]; ++count;
j = j - increment; ++count;
}
A[j] = temp; ++count;
}
if (increment == 2)
{
increment = 1; ++count;
}
else
{
increment = (int) (increment / 2.2); ++count;
}
}
return count;
}
void fill_array(int A[], int size)
{
int first_rand = 0;
while(first_rand < size)
{
A[first_rand] = rand() % 2100;
first_rand++;
}
}
void print_array(int A[], int size)
{
int first_pos = 0;
cout.width(2);
cout<<size<<": ";
while(first_pos < size)
{
cout<<A[first_pos]<<" ";
first_pos++;
}
cout<<endl;
}
Originally Posted by Cpro
