Check sorted Arrays

Inserting in a Sorted array

You need to find the position to insert the element to, and after the comparison you also have to shift them.

For loops are mostly useful when you know how many times you are going to repeat, so we will use a while loop.

void InsertSort(struct Array *arr, int x) {
  if (arr->length == arr->size) {
    return;
  }

  int i = arr->length - 1;

  while (i >= 0 && arr->A[i] > x) {
    arr->A[i + 1] = arr->A[i];
    i--;
  }

  arr->A[i + 1] = x;
  arr->length++;
}

Checking if an array is sorted

Start from the first array element. If the number in that slot is smaller than the next one, continue. Every present number should be smaller than the next number.

int isSorted(struct Array arr) {
  int i;

  for (i = 0; i < arr.length - 1; i++) {
    if (arr.A[i] > arr.A[i + 1])
      return 0;
  }

  return 1;
}

Arranging all negative values on the left side

• We want to bring all the negative numbers on the left hand side, then followed by that we should have positive numbers.
• For this we can take two index pointers, i and j, one in the beginning of the list and one in the end.
• Using i we look for positive numbers, using j we look for negative numbers. If found they will exchange.

void Rearrange(struct Array *arr) {
  int i, j;
  i = 0;
  j = arr->length - 1;

  while (i < j) {
    while (arr->A[i] < 0) {
      i++;
    }

    while (arr->A[j] >= 0) {
      j--;
    }

    if (i < j) {
      int temp;
      temp = arr->A[i];
      arr->A[i] = arr->A[j];
      arr->A[j] = temp;
    }
  }
}