Recursion Sort

Question

I have the following function to sort an unordered array with even numbers in the front and odd numbers in the back. Is there any way to do this without using any loops?

//front is 0, back =array.length-1; arrangeArray (front, back); public static void arrangeArray (int front, int back) { if (front != back || front<back) { while (numbers [front]%2 == 0) front++; while (numbers[back]%2!=0) back--; if (front < back) { int oddnum = numbers [front]; numbers[front]= numbers[back]; numbers[back]=oddnum; arrangeArray (front+1, back-1); } } } 

Answer 1

Mergesort is pretty trivial for code without loops:

 void mergesort(int lo, int hi) { if (lo<hi) { int m=(lo+hi)/2; mergesort(lo, m); mergesort(m+1, hi); merge(lo, m, hi); } } 

I will leave it clear / odd as an exercise for the reader :)

(Sounds like homework)

Answer 2

When you do a recursion, you have a base step and a recursive step.

In this case, the basic condition is when the front == back, because you start from the edges and end up in the middle. When you get to the middle, you know that.

Before you take a recursive step, you need to sort a little. You do sorting only one step at a time, so at the moment we are dealing only with the elements of the array [front] and array [back]. After you place them in the right place, make a recursive call.

You end up with something like this:

 public static void arrangeArray (int front, int back) { if(front >= back) return; int f = numbers[front]; int b = numbers[back]; if(f%2 == 0) { front++; } else { numbers[back] = f; back--; } if (b%2 == 0) { numbers[front] = b; front++; } else { back--; } arrangeArray(front, back); } 

It is not tested and probably does not work for boundary conditions, but this is a good start :)

Answer 3

Wouldn't it be:

 //front is 0, back =array.length-1; arrangeArray (front, back); public static void arrangeArray (int front, int back) { if (front != back || front<back) { if (numbers [front]%2 == 0) arrangeArray (front+1, back); else if (numbers[back]%2!=0) arrangeArray (front, back-1); else if (front < back) { int oddnum = numbers [front]; numbers[front]= numbers[back]; numbers[back]=oddnum; arrangeArray (front+1, back-1); } } } 

?

Answer 4

Can I recommend this Python snippet to inspire high-level thinking?

 compare = lambda x,y: x - y if x%2 == y%2 else y%2 - x%2 >>> sorted([3,4,2,1,5,6,7,90,23,44], cmp=compare) [1, 3, 5, 7, 23, 2, 4, 6, 44, 90] 

I think we need to build a comparator function that returns negative, 0 and positive and use this.

Answer 5

What you want to do is

 arrangeArray(front, back, bool recursed=false) { if (recursed) { arrangeArray(front, back/2, true); return arrangeArray(back/2, back, true); } // Do stuff here. } 

Answer 6

The following should be instructive. This is a recursive O(N) solution that rearranges even numbers in the front and odd numbers in the back, but does not make any orders outside of this.

 static boolean isEven(int n) { return (n & 1) == 0; } static boolean isOdd(int n) { return !isEven(n); } static int[] swapped(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; return nums; } static int[] arrange(int[] nums, int lo, int hi) { return (lo >= hi) ? nums : (isEven(nums[lo])) ? arrange(nums, lo + 1, hi) : (isOdd(nums[hi])) ? arrange(nums, lo, hi - 1) : arrange(swapped(nums, lo, hi), lo + 1, hi - 1); } static void evenOddSort(int... nums) { System.out.println(java.util.Arrays.toString( arrange(nums, 0, nums.length - 1) )); } public static void main(String[] args) { evenOddSort(1,3,5,7,2,4,6); } // prints "[6, 4, 2, 7, 5, 3, 1]" 

---

I think the ternary operator makes the recursion stream more natural, but if you don't like the way it works, you can just use the traditional if-else .

 static int[] arrange(int[] nums, int lo, int hi) { if (lo >= hi) { return nums; } else if (isEven(nums[lo])) { return arrange(nums, lo + 1, hi); } else if (isOdd(nums[hi])) { return arrange(nums, lo, hi - 1); } else { return arrange(swapped(nums, lo, hi), lo + 1, hi - 1); } }