Quantcast

Jump to content

» «
Photo

Help with some algoritms

1 reply to this topic
coin-god
  • coin-god

    High Roller

  • $outh $ide Hoodz
  • Joined: 18 Mar 2007
  • None

#1

Posted 18 January 2012 - 09:41 PM

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
  • K^2

    Vidi Vici Veni

  • Moderator
  • Joined: 14 Apr 2004
  • United-States
  • Most Knowledgeable [Web Development/Programming] 2013
    Most Knowledgeable [GTA Series] 2011
    Best Debater 2010

#2

Posted 18 January 2012 - 10:49 PM Edited by K^2, 18 January 2012 - 10:51 PM.

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.

CODE
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)

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

CODE
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.
CODE
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);
}




1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users