CODEWITHSUNDEEP
arraysalgorithmrecursion
Kevin
Kevin

Reputation: 6831

Segregate Even and Odd numbers In an Integer Array using Recursion

I am doing an algorithm exercise, which asks to rearrange an array of integers, to put all the even-valued elements before odd-valued elements.

I thought for a while and came up with the following pseudo code:

int[] Rearrange(int [] arr)
{

   if arr.length=1
     return arr;

   if arr[0] is even
    return arr[0] followed by Rearrange(arr.subarray(1,arr.length))
   else
    return Rearrange(arr.subarray(1,arr.length)) followed by arr[0]

}

I am bit concerned about my proposed solution above, since I need to do a copy operation in each recursion cycle, which is expensive. Experts please kindly advise, thanks!

Upvotes: 0

Views: 1469

Answers (2)

M.Soyturk
M.Soyturk

Reputation: 370

Even though the question was answered, I'm putting the recursive version of solving this problem here so that people, who are wondering, can see why recursion is a bad approach for this problem. 

public static int[] segregate(int[] array, int left) {

    int leftIndex = left;

    if(left == array.length) {
        return array;
    }

    for(int i = leftIndex + 1; i < array.length; i++) {
        if(array[leftIndex] % 2 == 1) {
            if(array[i] % 2 == 0) {
                int temp = array[leftIndex];
                array[leftIndex] = array[i];
                array[i] = temp;
            }
        }
    }

    return segregate(array, leftIndex + 1);
}

As can be seen from the code, the method will call itself N times. When you consider the fact that the complexity of for loop in the method is O(N), the total complexity of recursion will be O(n*2) which is worse than non-recursive solution.

Upvotes: 0

Duncan C
Duncan C

Reputation: 131426

Recursion is expensive, and your approach would create tons of extra copies. Sometimes recursion yields an elegant solution, and other times it is absolutely the wrong tools for the job. This is a wrong-tool-for-the job case.

Instead, write a method that keeps a head index and a tail index. Initialize the head pointer to the beginning of the array and the tail index to the end.

At each pass, loop through the items at the head of the list, looking for odd values. When you find one, stop, then look for an even value from the end, looking backwards. When you find one, switch the two values (using a third int as temporary storage.) Repeat forever. When the head and tail indexes meet, you're done.

Something like this:

int head_index = 0;
int tail_index = array.count;
int temp;
while (true)
{
  //Find the next odd number at the front of the array.
  while (array[head_index] %2==0) && head_index < tail_index)
    head_index++;

  //Find the next even number at the end of the array.
  while (array[tail_index]%2==1 && head_index < tail_index)
    tail_index--;

  //If the pointers meet, we're done
  if (head_index <= tail_index)
    break;

  //Swap the items at the current indexes
  temp = array[head_index];
  array[head_index] = array[tail_index];
  array[tail_index] = temp;
}

(Completely untested, and I'm tired, but the basic idea should work)

It's more-or-less C syntax pseudo code.

It should run in O(n) time, with the only extra RAM needed being your 2 indexes and the temporary holding variable.

Upvotes: 1

Related Questions