C program problem

smiles

Right, there's probably something very simple wrong with this.... but i can't find it (and it's driving me nuts)...

Essentially I've to write various different sorting algorithms, and the one of the moment is "mergesort"

3 files
list.h
list.c
mergesort.c

[b]list.h[/b]
/* makes the intention of our data clearer  */
typedef int *LIST;

/* displays the list a of lenght n */
void writelist(int n, LIST a);

LIST readlist(int n);
void swap(int i, LIST a);

// declaration for merge
LIST merge(int m, LIST a, int n, LIST b);

// declaration for mergesort
LIST mergesort(int n, LIST a);

[b]list.c[/b]
#include <stdio.h>
#include <stdlib.h>

#include "list.h"

/* displays the list l of length n */
void writelist(int n, LIST a)
{
  int i;
  for (i = 0; i < n; i++) {
    printf(" %d", a[i]);
  }
  printf(".\n");
}

/* creates space for and reads a list of lenght n */
LIST readlist(int n)
{
  int i;
  LIST a;
  
  a = calloc(n, sizeof(int));
  printf("\nPlease enter %d items, separated by spaces: ", n);
  for (i = 0; i < n; i++) {
    scanf("%d", a+i);
  }
  return a;
}

/* swaps item i with its successor in the list l */
void swap(int i, LIST a)
{
  int s;
  s = a[i];
  a[i] = a[i+1];
  a[i+1] = s;
}

// merge sort
LIST merge(int m, LIST a, int n, LIST b)
{	
	LIST c = calloc(m+n, sizeof(int));

	int i = 0;
	int j = 0;
	int k;

	for(k = 0; k <= m+n; k++)
	{
		if(i < m && j < n)
		{
			if(a[i] < b[j])
			{
				c[k] = a[i];
				i = i + 1;
			}			
			else
			{
				c[k] = b[j];
				j = j + 1;
			}
		}
		else 
		{
			if(i < m)
			{
				c[k] = a[i];
				i = i + 1;
			}
			else
			{
				c[k] = b[j];
				j = j + 1;
			}
		}
	}

	return c;
}

LIST mergesort(int n, LIST a)
{
	LIST d, b, c;
	int r, s;

	if(n == 1)
	{
		d = calloc(1, sizeof(int));
		d[0] = a[0];
	}
	else
	{
		r = n/2;
		printf("%d\n", r);
		s = n - r;
		printf("%d\n\n", s);
		b = mergesort(r, a);
		c = mergesort(s, a+r);
		d = merge(r, b, s, c);	
	}
	return d;
}

[b]mergesort.c[/b]
#include <stdio.h>
#include <stdlib.h>
#include "list.h"

int main() 
{
	int n;
	LIST l;

	printf("\nPlease enter the length of the list: ");
	scanf("%d", &n);

	l = readlist(n);

	printf("\nThe given list is: ");
	writelist(n, l);

	mergesort(n, l);
	printf("\nThe sorted list is: ");
	writelist(n, l);

	printf("\n");

	/* the allocated memory must be freed */
	free(l);
	return 0;
}

mergesort doesn't mergesort the lists. merge on its own will add two lists of increasing order together (tested seperately)... but I can't see why mergesort wont work. (probably something blatently obvious, but I really can't see it)

Anyone help?

<< Fio >>

Zab

Well, it doesn't look like you are sorting them in place (due to the many occurances of calloc in list.c), so your problem is probably that you are printing out the old list at the end of main, rather than the list returned by mergesort. On the other hand, dynamic memory allocation is costly, so you should probably look into alternative methods.

Zab.

smiles

Originally posted by Zab
so your problem is probably that you are printing out the old list at the end of main, rather than the list returned by mergesort.

DOH!!! Thats exactly it. I knew it'd be something blatent like that. Thanks a million.

Originally posted by Zab
On the other hand, dynamic memory allocation is costly, so you should probably look into alternative methods.

Zab.

I know, but this is the way we have to do it

Thanks again

<< Fio >>