sorting using recursion

Question

I have the following function to sort an unordered array to having even numbers in the front and odd numbers in the back. Is there a way to get it done 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);
        }
    }
}

Stephen · Accepted Answer · 2010-04-27 01:32:56Z

3

Mergesort is fairly trivial to 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'll leave making it sort even/odd as an exercise to the reader :)

(Sounds like homework)

edited Apr 27, 2010 at 1:32

answered Apr 27, 2010 at 1:10

Stephen

49.4k7 gold badges63 silver badges70 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Charles Ma Over a year ago

I don't think the structure of merge sort is the right kind of structure for this problem. This recurses in towards the middle, there's no divide and conquer involved, just pure iterative recursion.

hzap Over a year ago

Charles: How is splitting the array in the middle, using recursion on both halves, and then merging them, not a divide-and-conquer algorithm?

Charles Ma Over a year ago

I was saying that this problem doesn't require divide and conquer (which merge sort IS), divide and conquer problems are usually solved in O(nlogn), where as this one can be done in O(n)

Charles Ma Over a year ago

Oh and I'm assuming that it doesn't require numbers to be sorted among themselves, just the even half on the front (not necessarily sorted) and odd ones in the back.

Stephen Over a year ago

@Charles Ma: Yep, you got a +1 from me.

|

Charles Ma · Accepted Answer · 2010-04-27 01:13:45Z

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

In this case, the base condition is when front == back, because you start from the edges and end up in the middle. When you get to the middle you know it's done.

Before you do the recursive step, you have to do a bit of sorting. You're only doing the sorting one step at a time, so only deal with the elements at array[front] and array[back] for now. After you arrange those into the right place, do a recursive call.

You'll 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's untested and probably doesn't work for edge conditions, but it's a good start :)

500 - Internal Server Error · Accepted Answer · 2010-04-27 01:17:13Z

2

Wouldn't that simply 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); 
        } 
    } 
}

?

answered Apr 27, 2010 at 1:17

500 - Internal Server Error

29k8 gold badges64 silver badges78 bronze badges

Comments

Hamish Grubijan · Accepted Answer · 2010-04-27 02:12:38Z

1

May 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 one needs to build a comparator function that returns negative, 0, and positive and use that.

edited Apr 27, 2010 at 2:12

answered Apr 27, 2010 at 1:28

Hamish Grubijan

10.9k23 gold badges106 silver badges150 bronze badges

Comments

Puppy · Accepted Answer · 2010-04-27 01:09:40Z

0

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.
}

answered Apr 27, 2010 at 1:09

Puppy

147k40 gold badges271 silver badges481 bronze badges

1 Comment

Oddthinking Over a year ago

Hmm... If you call it with record=false, it does nothing. If you call it with recursed=true, it recurses forever.

polygenelubricants · Accepted Answer · 2010-04-27 02:08:36Z

0

The following should be instructive. It's a recursive O(N) solution that rearranges the even numbers in front and odd numbers in the back, but doesn't do any ordering beyond that.

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 flow more naturally, but if you're not that comfortable with how it works, you can just use 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);
    }
}

edited Apr 27, 2010 at 2:08

answered Apr 27, 2010 at 1:42

polygenelubricants

385k129 gold badges568 silver badges627 bronze badges

3 Comments

Stephen Over a year ago

Abuse of nested ternary operators. :P

polygenelubricants Over a year ago

@Stephen: I disagree. There's a reason why the ternary operator is right-associative, and it's to allow this kind of expression-level if-else like constructs.

Keith Randall Over a year ago

I agree with Stephen. Just because you can write it without parentheses doesn't mean you should. The expression x ^ a + b ^ c + d is perfectly well-defined, but those who don't know the precedence rules by heart will be incredibly confused.

Collectives™ on Stack Overflow

sorting using recursion

6 Answers 6

6 Comments

Comments

Comments

Comments

1 Comment

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

6 Comments

Comments

Comments

Comments

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related