Help with some algoritms

[coin-god]

I have to write a function in JAVA that modifies an array by using the first element as a pivot and moves all the elements that are smaller to it's left and the ones bigger to it's right. I have to use crossed recursion. The pivot is compared to each of the other elements only once.

 

Example:

 

3 4 1 8 6 5 2

 

Should end up like this (I think):

 

1 2 3 4 8 6 5 (3 is pivot)

 

I guess the actual order of the smaller/bigger elements dosn't matter.

I honestly have no idea of were to start. They didn't give use much information about how to do this kind of stuff in college.

This is not "homework", I'm studing for my final exam.

[K^2]

Are you sure you are supposed to use recursion for pivoting? This is part of the quick sort algorithm, which indeed, is done recursively. You could make even the pivot recursive, but I don't see why you'd want to. There are several ways of doing this. The most typical actually used by quick sort would proceed like this.

 

 

Indecies of two pointers start at two ends of array, excluding pivot.3 4 1 8 6 5 2 One on the left is > pivot, while right < pivot. Swap.* ^         ^3 2 1 8 6 5 4 Left pointer is < pivot, so pointer is advanced. Right > pivot, advanced.* ^         ^3 2 1 8 6 5 4 Again, both are correct, so both are advanced.*   ^     ^3 2 1 8 6 5 4 Left pointer > pivot. Right > pivot. Left stays, right advances.*     ^ ^3 2 1 8 6 5 4 Pointers merged. Now we need to step back, and swap with pivot.*     ^3 2 1 8 6 5 4 Perform swap.^   ^1 2 3 8 6 5 4 Final state. To do full quick sort, repeat with 1 and 8 as pivots, etc.

 

 

Code for it would look something like this. (C syntax)

 

 

a=1;b=length-1;while(a!=b){  if(array[a]<array[0]){a++; continue;}  if(array[b]>array[0]){b--; continue;}  swap(array+a, array+b);}swap(array, array+a-1);

 

 

If you insist on this part being done recursively, you can make it run something along the lines of this.

 

 

void pivot(int array[], int a, int b){   if(a==b){swap(array, array+a-1);return;}   if(array[a]<array[0]){pivot(array,a+1,b); return;}   if(array[b]>array[0]){pivot(array,a,b-1); return;}   swap(array+a, array+b);   pivot(array,a,b);}pivot(array, 1, length-1);

 

 

But honestly, that's just a waste of stack space and jump instructions.

 

Full quick sort written to implement the first form with recursion would be written like this.

 

void quicksort(int array[], int length){   if(length<=1)return;   a=1;   b=length-1;   while(a!=b)   {     if(array[a]<array[0]){a++; continue;}     if(array[b]>array[0]){b--; continue;}     swap(array+a, array+b);   }   swap(array, array+a-1);   quicksort(array, a-1);   quicksort(array+a,length-a);}

 

Edited January 18, 2012 by K^2