Tag: Remove

I am looking for an algorithm to move a subarray before an element (which is not part of this subarray) in the same array where the last element of the subarray is the last element of the array with O (1) extra space and O (n ) Running time.

e.g. where * p1 = 5 and * p2 = 3:

1 2 5 6 7 3 4

becomes

1 2 3 4 5 6 7

This is what I have so far (written in C programming language). Problems occur when p1 reaches p2.

void swap(long* p1, long* p2, long* array_end) {
  long* p2_i = p2;
  while (p1 < array_end) {
    if (p2_i > array_end) {
      p2_i = p2;
    }

    // swap *p1 and *p2_i
    long* temp = p1;
    *p1 = *p2_i;
    *p2_i = temp;

    ++p1;
    ++p2_i;
  }
}