/**
  John P. Cataldo &lt;cataldoj@ccs.neu.edu&gt;<br>
  Daniel Rinehart &lt;danielr@ccs.neu.edu&gt;<br>
  Aris Yannopoulos &lt;aris@ccs.neu.edu&gt;<br>
  COM1390 Programming Assignment #1<P>

  $Id: Partition.java,v 1.1 1999/02/16 02:48:44 danielr Exp $<P>

  Partition around a given element.

  */
public class Partition {

  /**
    Partition the given array around the element in r.

    @param S the array to partition
    @param p the begin point of the range to consider
    @param r the end point of the range to consider which also contains the value to partition around
    
    @return the index for which all element to the left are less than it and all elements to the right of it are greater than it

    */
  public static int partition( int[] S, int p, int r ) {
    int comp = 0;
    int x = S[ r ];
    
    int i = p - 1;
    for( int j = p; j < r; j++ ) {
      comp++;
      if ( S[ j ] < x ) {
	i++;
	int temp = S[ i ];
	S[ i ] = S[ j ];
	S[ j ] = temp;
      }
    }
    int temp = S[ i + 1 ];
    S[ i + 1 ] = S[ r ];
    S[ r ] = temp;
    
    FindQuantiles.incComp( comp );
    
    return( i + 1 );
  }
}