Set Operations

They will be performed on two arrays. These also removes duplicate elements.

Union

Copy the elements from the first array, and then from the second one, while also removing duplicates. This is a pretty slow, O(n²) operation since it has to traverse the array each time to check for duplicates.
If the arrays are already sorted, this operation will be significantly faster at O(n).


struct Array *Union(struct Array *arr1, struct Array *arr2) {
  int i, j, k;
  i = j = k = 0;

  struct Array *arr3 = (struct Array *)malloc(sizeof(struct Array));

  while (i < arr1->length && j < arr2->length) {
    if (arr1->A[i] < arr2->A[j])
      arr3->A[k++] = arr1->A[i++];
    else if (arr2->A[j] < arr1->A[i])
      arr3->A[k++] = arr2->A[j++];
    else {
      arr3->A[k++] = arr1->A[i++];
      j++;
    }
  }

  for (; i < arr1->length; i++)
    arr3->A[k++] = arr1->A[i];

  for (; j < arr2->length; j++)
    arr3->A[k++] = arr2->A[j];

  arr3->length = k;
  arr3->size = 10;

  return arr3;
}

Intersection

We take the common elements of A and B and store them in C.
Checking elements of array A, and before copying, check if they are already in array B.
This is also time consuming, unless all the elements are already sorted.


struct Array *Intersection(struct Array *arr1, struct Array *arr2) {
  int i, j, k;
  i = j = k = 0;

  struct Array *arr3 = (struct Array *)malloc(sizeof(struct Array));

  while (i < arr1->length && j < arr2->length) {
    if (arr1->A[i] < arr2->A[j])
      i++;
    else if (arr2->A[j] < arr1->A[i])
      j++;
    else if (arr1->A[i] == arr2->A[j]) {
      arr3->A[k++] = arr1->A[i++];
      j++;
    }
  }

  arr3->length = k;
  arr3->size = 10;

  return arr3;
}

Difference

Subtraction of two sets, A - B means that we want all the elements in A which are not in B.
Every element of A is compared with all the elements of B, and if it is not there then we copy it to C.
If he elements are sorted, it is similar to the merging procedure; we compare each element in A and B at the same position, and copy to C if they are different. We will only be copying from A.


struct Array *Difference(struct Array *arr1, struct Array *arr2) {
  int i, j, k;
  i = j = k = 0;

  struct Array *arr3 = (struct Array *)malloc(sizeof(struct Array));

  while (i < arr1->length && j < arr2->length) {
    if (arr1->A[i] < arr2->A[j])
      arr3->A[k++] = arr1->A[i++];
    else if (arr2->A[j] < arr1->A[i])
      j++;
    else {
      i++;
      j++;
    }
  }

  for (; i < arr1->length; i++)
    arr3->A[k++] = arr1->A[i];

  arr3->length = k;
  arr3->size = 10;

  return arr3;
}

Set membership

This is to know whether an elements belongs to a set or not. It's the same as searching.

Debugging Grimoire

Set Operations