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

  1. #1
    Registered User
    Join Date
    May 2003
    Posts
    7

    Angry 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. #2
    Been here, done that.
    Join Date
    May 2003
    Posts
    1,164
    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.
    Definition: Politics -- Latin, from
    poly meaning many and
    tics meaning blood sucking parasites
    -- Tom Smothers

  3. #3
    Registered User
    Join Date
    May 2003
    Posts
    7

    Angry

    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 < >

  4. #4
    Registered User
    Join Date
    May 2003
    Posts
    7

    Sorry about that...

    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));
    
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. beginner help with selection sort
    By chelpme in forum C Programming
    Replies: 3
    Last Post: 04-26-2009, 10:27 PM
  3. Selection Sort problem #2
    By Twigstar in forum C++ Programming
    Replies: 7
    Last Post: 07-11-2005, 07:27 PM
  4. recursive quick sort - stack overflow
    By Micko in forum C Programming
    Replies: 9
    Last Post: 01-01-2005, 05:51 PM
  5. Bubble Sort / selection problem
    By Drew in forum C++ Programming
    Replies: 7
    Last Post: 08-26-2003, 03:23 PM