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.
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.
What are you trying to accomplish in this portion of code -- it makes no sense to me:
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.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();
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.
Definition: Politics -- Latin, from
poly meaning many and
tics meaning blood sucking parasites
-- Tom Smothers
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.
Mod noteCode:#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)); }
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)); }