# Thread: what is ALGORITHM this implementation an sorting and ascending order.

1. ## what is ALGORITHM this implementation an sorting and ascending order.

Code:
```processing in machine wrest case, bast case and so...

#include<iostream>
#include<ctime>
#include<cstdlib>
#include<fstream>

#define START_SIZE 10000
#define END_SIZE   50000
#define delta  10000

using namespace std;

long *data;

double time_taken[5][4][500]; //time_taken[i,j,k] the time taken for

sorting algorithm i, using data format j, and input size k
//i = 0 for insertion, 1 for bubble 2 for selection, 3 for merge sort and 4 for quick sort

//j = 0 for ascending, 1 for descending, 2 for random

//k  refers to the data size 1000 * 10^k

void quicksort (long int a[], long int lo, long int hi);

void mergeSort(long int A[], long int start, long int end);

void merge(long int A[], long int start, long int mid, long int end);

void selection_sort(long a[],long n);

void bubble_sort(long a[],long n);

void insertion_sort(long a[],long n);

void set_time_information(long n, int k);

void file_findings(int k);

int main()

{

long i,j, n = START_SIZE;
int k = 0;

while (n <= END_SIZE){

data=new long[n];

set_time_information(n, k);

delete [] data;

n = n  + delta;

k++;

}

file_findings(k);

system("PAUSE");

return EXIT_SUCCESS;

}

void file_findings(int k)

{
ofstream outf;

outf.open("test.txt");

long  n = START_SIZE;

outf<<"Insertion - Ascending "<<endl;

for(int i = 0; i < k; i++){

outf<<n<<"\t"<<time_taken[0][0][i]<<endl;

n = n + delta;
}

n = START_SIZE;
outf<<"Insertion - Descending "<<endl;

for(int i = 0; i < k; i++){

outf<<n<<"\t"<<time_taken[0][1][i]<<endl;

n = n + delta;

}

outf<<"Insertion - Random "<<endl;

n = START_SIZE;

for(int i = 0; i < k; i++){

outf<<n<<"\t"<<time_taken[0][2][i]<<endl;

n = n + delta;
}

outf<<"Bubble - Ascending "<<endl;

n = START_SIZE;

for(int i = 0; i < k; i++){

outf<<n<<"\t"<<time_taken[1][0][i]<<endl;

n = n + delta;
}
outf<<"Bubble - Descending "<<endl;

n = START_SIZE;

for(int i = 0; i < k; i++){

outf<<n<<"\t"<<time_taken[1][1][i]<<endl;

n = n + delta;

}
outf<<"Bubble - Random "<<endl;
n = START_SIZE;
for(int i = 0; i < k; i++){
outf<<n<<"\t"<<time_taken[1][2][i]<<endl;
n = n + delta;
}

outf<<"Selection - Ascending "<<endl;
n = START_SIZE;
for(int i = 0; i < k; i++){
outf<<n<<"\t"<<time_taken[2][0][i]<<endl;
n = n + delta;
}
outf<<"Selection - Descending "<<endl;
n = START_SIZE;
for(int i = 0; i < k; i++){
outf<<n<<"\t"<<time_taken[2][1][i]<<endl;
n = n + delta;
}
outf<<"Selection - Random "<<endl;
n = START_SIZE;
for(int i = 0; i < k; i++){
outf<<n<<"\t"<<time_taken[2][2][i]<<endl;
n = n + delta;
}

outf<<"Merge - Ascending "<<endl;
n = START_SIZE;
for(int i = 0; i < k; i++){
outf<<n<<"\t"<<time_taken[3][0][i]<<endl;
n = n + delta;
}
outf<<"Merge - Descending "<<endl;
n = START_SIZE;
for(int i = 0; i < k; i++){
outf<<n<<"\t"<<time_taken[3][1][i]<<endl;
n = n + delta;
}
outf<<"Merge - Random "<<endl;
n = START_SIZE;
for(int i = 0; i < k; i++){
outf<<n<<"\t"<<time_taken[3][2][i]<<endl;
n = n + delta;
}

outf<<"Quick - Ascending "<<endl;
n = START_SIZE;
for(int i = 0; i < k; i++){
outf<<n<<"\t"<<time_taken[4][0][i]<<endl;
n = n + delta;
}
outf<<"Quick - Descending "<<endl;
n = START_SIZE;
for(int i = 0; i < k; i++){
outf<<n<<"\t"<<time_taken[4][1][i]<<endl;
n = n + delta;
}
outf<<"Quick - Random "<<endl;
n = START_SIZE;
for(int i = 0; i < k; i++){
outf<<n<<"\t"<<time_taken[4][2][i]<<endl;
n = n + delta;
}

outf.close();

}
void set_time_information(long n, int k)
{
cout<<"===============PROCESSING AT SIZE ================="<<n<<endl;
long j;
clock_t start,end;
double time_elapsed;

for( j=0;j<=n-1;j++)
data[j]=3*j+2;

start=clock() ;
mergeSort(data,0, n-1);
end=clock();
time_elapsed = double((end-start))/CLOCKS_PER_SEC;

cout<<"\tData generated in ascending order"<<endl;
cout<<"\t\tTime analysis of merge sort "<<endl;
cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t";
cout<<"Time taken  = "<<time_elapsed<<endl;
time_taken[0][0][k] = time_elapsed;

start=clock() ;
quicksort(data,0, n-1);
end=clock();
time_elapsed = double((end-start))/CLOCKS_PER_SEC;

cout<<"\tData generated in ascending order"<<endl;
cout<<"\t\tTime analysis of quick sort "<<endl;
cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t";
cout<<"Time taken  = "<<time_elapsed<<endl;
time_taken[0][0][k] = time_elapsed;

start=clock() ;
insertion_sort(data,n);
end=clock();
time_elapsed = double((end-start))/CLOCKS_PER_SEC;

cout<<"\tData generated in ascending order"<<endl;
cout<<"\t\tTime analysis of insertion sort "<<endl;
cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t";
cout<<"Time taken  = "<<time_elapsed<<endl;
time_taken[0][0][k] = time_elapsed;

start=clock();
bubble_sort(data,n);
end=clock();
time_elapsed = double((end-start))/CLOCKS_PER_SEC;
cout<<"\t\tTime analysis of bubble sort "<<endl;
cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t";
cout<<"Time taken  = "<<time_elapsed<<endl;
time_taken[1][0][k] = time_elapsed;

start=clock();
selection_sort(data,n);
end=clock();
time_elapsed = double((end-start))/CLOCKS_PER_SEC;
cout<<"\t\tTime analysis of selection sort "<<endl;
cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t";
cout<<"Time taken  = "<<time_elapsed<<endl;
time_taken[2][0][k] = time_elapsed;

for(j=0;j<=n-1;j++)
data[j]=((4*n)-(3*j+2));

start=clock() ;
mergeSort(data,0, n-1);
end=clock();
time_elapsed = double((end-start))/CLOCKS_PER_SEC;

cout<<"\tData generated in Descending order"<<endl;
cout<<"\t\tTime analysis of merge sort "<<endl;
cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t";
cout<<"Time taken  = "<<time_elapsed<<endl;
time_taken[0][0][k] = time_elapsed;

start=clock() ;
quicksort(data,0, n-1);
end=clock();
time_elapsed = double((end-start))/CLOCKS_PER_SEC;

cout<<"\tData generated in Descending order"<<endl;
cout<<"\t\tTime analysis of quick sort "<<endl;
cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t";
cout<<"Time taken  = "<<time_elapsed<<endl;
time_taken[0][0][k] = time_elapsed;

start=clock() ;
insertion_sort(data,n);
end=clock();
time_elapsed = double((end-start))/CLOCKS_PER_SEC;
cout<<"\tData generated in Descending order"<<endl;
cout<<"\t\tTime analysis of insertion sort "<<endl;
cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t";
cout<<"Time taken  = "<<time_elapsed<<endl;
time_taken[0][1][k] = time_elapsed;

start=clock();
bubble_sort(data,n);
end=clock();
time_elapsed = double((end-start))/CLOCKS_PER_SEC;
cout<<"\t\tTime analysis of bubble sort "<<endl;
cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t";
cout<<"Time taken  = "<<time_elapsed<<endl;
time_taken[1][1][k] = time_elapsed;

start=clock();
selection_sort(data,n);
end=clock();
time_elapsed = double((end-start))/CLOCKS_PER_SEC;
cout<<"\t\tTime analysis of selection sort "<<endl;
cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t";
cout<<"Time taken  = "<<time_elapsed<<endl;
time_taken[2][1][k] = time_elapsed;

for(j=0;j<=n-1;j++)
data[j]=(rand()%(3*n));

start=clock() ;
mergeSort(data,0, n-1);
end=clock();
time_elapsed = double((end-start))/CLOCKS_PER_SEC;

cout<<"\tData generated in random order"<<endl;
cout<<"\t\tTime analysis of merge sort "<<endl;
cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t";
cout<<"Time taken  = "<<time_elapsed<<endl;
time_taken[0][0][k] = time_elapsed;

start=clock() ;
quicksort(data,0, n-1);
end=clock();
time_elapsed = double((end-start))/CLOCKS_PER_SEC;

cout<<"\tData generated in random order"<<endl;
cout<<"\t\tTime analysis of quick sort "<<endl;
cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t";
cout<<"Time taken  = "<<time_elapsed<<endl;
time_taken[0][0][k] = time_elapsed;

start=clock() ;
insertion_sort(data,n);
end=clock();
cout<<"\tData generated in random order"<<endl;
cout<<"\t\tTime analysis of insertion sort "<<endl;
cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t";
cout<<"Time taken  = "<<time_elapsed<<endl;
time_taken[0][2][k] = time_elapsed;

start=clock();
bubble_sort(data,n);
end=clock();
time_elapsed = double((end-start))/CLOCKS_PER_SEC;
cout<<"\t\tTime analysis of bubble sort "<<endl;
cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t";
cout<<"Time taken  = "<<time_elapsed<<endl;
time_taken[1][2][k] = time_elapsed;

start=clock();
selection_sort(data,n);
end=clock();
time_elapsed = double((end-start))/CLOCKS_PER_SEC;
cout<<"\t\tTime analysis of selection sort "<<endl;
cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t";
cout<<"Time taken  = "<<time_elapsed<<endl;
time_taken[2][2][k] = time_elapsed;
}
void mergeSort(long int A[], long int start, long int end){
long int mid;
if (start < end){
mid = (start + end)/2;
mergeSort(A, start, mid);
mergeSort(A, mid + 1, end);
merge(A, start, mid, end);
}
}
void merge(long int A[], long int start, long int mid, long int end){
long int *B = new long int[end-start + 1];
long int i = start, j = mid+1, k = 0;
while(i <= mid && j <= end){
if(A[i] < A[j]) B[k++] = A[i++];
else B[k++] = A[j++];
}
while(i <= mid)B[k++] = A[i++];
for(long int i=0; i<k; i++) A[start+i] = B[i];
}
void quicksort (long int a[], long int lo, long int hi)
{
//  lo & hi are the lower upper indices of the region of array a that is to be sorted
long int i=lo, j=hi, h;
long int x=a[(lo+hi)/2];
//  partition
do {
while (a[i]<x) i++;     while (a[j]>x) j--;
if (i<=j) {
h=a[i]; a[i]=a[j]; a[j]=h; i++; j--;
}
} while (i<=j);
//  recursion
if (lo<j) quicksort(a, lo, j);
if (i<hi) quicksort(a, i, hi);
}
void selection_sort(long a[],long n){
long index, temp, i,j;
for(j=0;j<n;j++){
index=j;
for(i=j+1;i<n-1;i++){
if(a[i]<a[index])
index=i;
}
temp=a[index];
a[index]=a[j];
a[j]=temp;
}
}

void bubble_sort(long a[],long n){
long i, j, temp;
for(i=0;i<n;i++){
for(j=1;j<=n-1-i;j++){
if(a[j-1]>a[j]) {
temp=a[j-1];
a[j-1]=a[j];
a[j]=temp;
}
}
}
}

void insertion_sort(long a[],long n) {
long key,i,j;
for(j=1;j<n;j++) {
key=a[j];
i=j-1;
while(i>=0 && a[i]>key){
a[i+1]=a[i];
i=i-1;
}
a[i+1]=key;
}
}```

2. Welcome to the Board! ;o)

Your question does not translate into english well. Maybe a more detailed description of what you are trying to accomplish would help and any compiler errors you may be getting.

I can say that your indentation in int main is quite sloppy. Maybe clean it up a little?

3. I need to how to analysis to algorithms to determine the amount of resources (such as time and storage) necessary to execute it.

4. For storage, it's how many items is space allocated for with new[], plus how deep does the recursion go.
For time, a common measure is the number of comparisons between items.

Do you need worst-case answers, or average case, or both?

5. Originally Posted by iMalc
[..]For time, a common measure is the number of comparisons between items.[..]
I would add the number of copy operations. A careful implementation of insertion sort, for example, requires only O(n log n) comparisons. (You can use a binary search to determine the insertion point)

6. @iMalc yes please, both of worst-case and average case.
how to define on algorithm or write to report?

7. I still don't understand which is your question. The program you posted seems to do exactly that: test some sorting algorithms with different data sets (shuffled / sorted / reverse-sorted) of different sizes, measure the time they take, and print the result.

All you have to do is run the program and see, for every algorithm, how does the time change when the size is increased.

By the way, where is the 'delete' for that 'new' in function merge()?