# Thread: merge sort and selection sort and time spent on both

1. ## merge sort and selection sort and time spent on both

I've attached the code. I've been working on this and I can't seem to get the random function to work. I think I have the basic algorithms down, but I just don't know how to arrange it. I'm getting really confused.

2. What are you trying to accomplish in this portion of code -- it makes no sense to me:
Code:
```void copy(int A[], int B[], int n)
{
int i;
for(i=1; i<=n; ++i)
{
B[i]=A[i];
}
}

int main(void)
{
int A[MAX], B[MAX];
int n;
clock_t start, finish, selectionstart, selectionfinish;

for (n = 100; n < 1000000; n *= 10)
{
//generate size numbers randomly
A[n]=rand()%20;

//copy the numbers into array a and array b
copy(A,B,n);

//sort array a using mergesort
start = clock();
mergesort(A, 0, n-1);
finish = clock();```
You start a loop at 100, load A[100] with a random value, (A array is actually defined as 0 to 99, so you are outside your array) then move 98 undefined values (skipping the first, A[0]) and one random number to the B array.

Next time thru the loop you load A[1000], way out of bounds.

Walk thru your program with pencil and paper to see what you are really doing.

3. Okay. Well I've been working on this for awhile. Instead of using arrays, I used pointers. It compiles, but I don't know where I went wrong. PLEASE HELP.

Code:
```#include <stdio.h>
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <time.h>
#include <sys/types.h>

/* Prototypes */

void selection_sort (int *x, int n);
int find_max_pos (int *x, int i, int n);
void swap (int *x, int i, int max_pos);

void mergesort (int *a, int l, int r);
void merge (int *a, int l, int r, int m);

int createArray ();
void printArray (int *a, int n);

int main (void)
{
int *a;
int size;

size = createArray (&a);
printf("%d", size);

printArray (a, size);
printf ("\n");

mergesort (a, 0, size-1);
printArray (a, size);

return 1;

}

void selection_sort (int *x, int n)
{
int max_pos, i;

for (i = 0; i < n -1; i++)
{
max_pos = find_max_pos (x, i, n);
swap (x, i, max_pos);
}
}

int find_max_pos (int *x, int i, int n)
{
int max_pos = i;
int walk;

for ( walk = i; walk < n; walk++)
{
if (*(x+walk) < *(x+max_pos))
max_pos = walk;
}

return max_pos;
}

void swap (int *x, int i, int max_pos)
{
int temp;

temp = *(x+i);
*(x+i) = *(x+max_pos);
*(x+max_pos) = temp;

}

void mergesort (int *a, int l, int r)
{

int m;
if (r > l)
{
m = (r + l) / 2;
mergesort (a, l, m);
mergesort (a, m+1, r);
merge (a, l, m, r );
}
}

void merge(int *a, int l, int m, int r)
{
/* Merges the two halves into a temporary array, then copies
the sorted elements back into the original array. */

int index;
int tracer1 = l, tracer2 = m + 1;

int *temp = (int *) calloc (r+1, sizeof (int));

index = l;

/* Do this until one of the halves is emptied. */
while (tracer1 <= m && tracer2 <= r)
{
if (a[tracer1] < a[tracer2])
temp[index++] = a[tracer1++];
else
temp[index++] = a[tracer2++];
//    ++comparisons;
}

/* Now copy the leftover elements from the non-empty half. */
while (tracer2 <= r)   /* right half is non-empty */
temp[index++] = a[tracer2++];
while (tracer1 <= m)  /* left half is non-empty */
temp[index++] = a[tracer1++];

/* Copy from temporary array back into a. */
for (index = l; index <= r; ++index)
a[index] = temp[index];
return;
}

int createArray ()
{
int *a, *b;
int size;
int i;
int		x;
time_t	t;

x = (int)time(&t) % RAND_MAX;
srand (x);

for (size = 100; size < 1000000; size *= 10)
//size = 20;
a = (int *) calloc (size, sizeof (int));
b = (int *) calloc (size, sizeof (int));

for (i = 0; i < size ; i++)
{
b[i] = a[i] = rand ();
}
return size;
}

void printArray (int *a, int n)
{
int i;

for (i = 0 ; i < n ; i++)
printf ("%d\n", *(a+i));

}```
Mod note
The tags are surrounded with [ ] not < >

Code:
```#include <stdio.h>
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <time.h>
#include <sys/types.h>

/* Prototypes */

void selection_sort (int *x, int n);
int find_max_pos (int *x, int i, int n);
void swap (int *x, int i, int max_pos);

void mergesort (int *a, int l, int r);
void merge (int *a, int l, int r, int m);

int createArray ();
void printArray (int *a, int n);

set_time ();
long get_delay ();

int main (void)
{
int *a;
int size;

size = createArray (&a);
printf("%d", size);

printArray (a, size);
printf ("\n");

mergesort (a, 0, size-1);
printArray (a, size);

return 1;

}

void selection_sort (int *x, int n)
{
int max_pos, i;

for (i = 0; i < n -1; i++)
{
max_pos = find_max_pos (x, i, n);
swap (x, i, max_pos);
}
}

int find_max_pos (int *x, int i, int n)
{
int max_pos = i;
int walk;

for ( walk = i; walk < n; walk++)
{
if (*(x+walk) < *(x+max_pos))
max_pos = walk;
}

return max_pos;
}

void swap (int *x, int i, int max_pos)
{
int temp;

temp = *(x+i);
*(x+i) = *(x+max_pos);
*(x+max_pos) = temp;

}

void mergesort (int *a, int l, int r)
{

int m;
if (r > l)
{
m = (r + l) / 2;
mergesort (a, l, m);
mergesort (a, m+1, r);
merge (a, l, m, r );
}
}

void merge(int *a, int l, int m, int r)
{
/* Merges the two halves into a temporary array, then copies
the sorted elements back into the original array. */

int index;
int tracer1 = l, tracer2 = m + 1;

int *temp = (int *) calloc (r+1, sizeof (int));

index = l;

/* Do this until one of the halves is emptied. */
while (tracer1 <= m && tracer2 <= r)
{
if (a[tracer1] < a[tracer2])
temp[index++] = a[tracer1++];
else
temp[index++] = a[tracer2++];
//    ++comparisons;
}

/* Now copy the leftover elements from the non-empty half. */
while (tracer2 <= r)   /* right half is non-empty */
temp[index++] = a[tracer2++];
while (tracer1 <= m)  /* left half is non-empty */
temp[index++] = a[tracer1++];

/* Copy from temporary array back into a. */
for (index = l; index <= r; ++index)
a[index] = temp[index];
return;
}

int createArray ()
{
int *a, *b;
int size;
int i;
int		x;
time_t	t;

x = (int)time(&t) % RAND_MAX;
srand (x);

for (size = 100; size < 1000000; size *= 10)
//size = 20;
a = (int *) calloc (size, sizeof (int));
b = (int *) calloc (size, sizeof (int));

for (i = 0; i < size ; i++)
{
b[i] = a[i] = rand ();
}
return size;
}

void printArray (int *a, int n)
{
int i;

for (i = 0 ; i < n ; i++)
printf ("%d\n", *(a+i));

}```