comparing integer lists

[Chris27]

Say the arrays are labled 'A' and 'B'. Just two pointers 'a' and 'b' (pointing in their respective arrays). Without loss of generality, say that 'B' starts with a larger element. Keep on advancing 'a' until *a < *b is no longer true. As these arrays are sorted, these values must be unique to A. Now advance 'b' in a similar manner. In the case where *a == *b, advance both pointers. Don't output the element as it exists in both.

Alternately, add all elements of A into a hashtable. Now iterate through B outputting all elements that are not in the hashtable.

Both algorithms have the same asympotic complexity but the first doesn't require any extra memory and should run a bit faster.



Here is algorithm 1

#include <stdio.h>
#include <stdlib.h>

void mydiff(int * arr1, int * end1,  int * arr2, int * end2, int * diff1, int* diff2);

int main() {
	int arr1[] = {2, 4, 5, 6, 7, 8, 20, 33, 34, 56};
	int arr2[] = {1, 2, 6, 7, 8, 10, 11, 45, 98};
	
	int * diff1 = calloc(sizeof(int), 10);
	int * diff2 = calloc(sizeof(int), 9);

	mydiff(arr1, arr1 + 10, arr2, arr2 + 9, diff1, diff2);
	
	printf("diff in arr1:\n");
	while(*diff1) {
		printf("%d ", *diff1);
		diff1++;
	}
	printf("\ndiff in arr2:\n");
	while(*diff2) {
		printf("%d ", *diff2);
		diff2++;
	}
	
	
}


void getTail(int * arr, int * end, int * diff) {
	while(arr != end) {
		*diff = *arr;
		diff++;
		arr++;
	}
}

void mydiff(int * arr1, int * end1,  int * arr2, int * end2, int * diff1, int * diff2) {
	
	if(arr1 == end1) {
		getTail(arr2, end2, diff2);
		return;
	}
		
	if(arr2 == end2) {
		getTail(arr1, end1, diff1);
		return;
	}
	
	while(*arr1 < *arr2 && arr1 != end1) {
		*diff1 = *arr1;
		diff1++;
		arr1++;
	}
	
	while(*arr2 < *arr1 && arr2 != end2) {
		*diff2 = *arr2;
		diff2++;
		arr2++;
	}
	
	if(*arr1 == *arr2) {
		if(arr1 != end1)
			arr1++;
		if(arr2 != end2)
			arr2++;
	}
	
	mydiff(arr1, end1, arr2, end2, diff1, diff2);
}