import java.util.Vector;

/** En klasse egnet til sortering af vectorer. Alle metoder er erklæret static, så 
  * de direkte kan kaldes med korrekte parametre.<p>
  * Klassen  skulle være temmelig hurtig, da den bruger en QuickSort algoritme.
  */
class VectorSort
{
	/** Kald denne metode for at sortere en Vector. Der skal leveres et IVectorSort object til at lave
	  * sammenligningerne mellem to elementer. IVectorComp skal kunne håndere alle de forskellige 
	  * objekter, der kan findes i vectoren.
	  * @param v En Vector, der skal sorteres
	  * @param comp Et Call-Back interface, der sørger for sammenligningen.
	  * @return Antallet af ombytninger.
	  */
	public static int Sort( Vector v, IVectorSort comp )
	{
		return QSort( v, 0, v.size()-1, comp );
	} // public int Sort()
	
	/** Intern funktion, der laver selve sorteringen. Kaldes rekursivt */
	protected static int QSort( Vector data, int left, int right, IVectorSort comp )
	{
		int middle = left, 
		    swapc = 0,
		    swaps = 0,
		    c = right;
		Object swap = null;
		    
		
		if (left==right) return 0;
		    
		do
		{
			// find first element on right side less than middle
			while ( comp.compareObject(data.elementAt(middle),data.elementAt(c))<0 ) c--;

			
			// swap middle and right
			if ( c!=middle )
			{
				swap = data.elementAt(c);
				data.setElementAt(data.elementAt(middle), c);
				data.setElementAt(swap,middle);
				swapc = middle;
				middle = c;
				c = swapc+1;
				swaps++;
			}
			
			// find first element on left side larger than middle
			while ( comp.compareObject(data.elementAt(middle),data.elementAt(c))>0 ) c++;
			

			// swap the two elements
			if ( c!=middle )
			{
				swap = data.elementAt(c);
				data.setElementAt(data.elementAt(middle), c);
				data.setElementAt(swap, middle);
				swapc = middle;
				middle = c;
				c = swapc-1;
				swaps++;
			}
		} while ( c != middle );
		
		if ( left < middle ) 
			swaps += QSort( data, left, middle-1, comp );
		if ( middle < right )
			swaps += QSort( data, middle+1, right, comp );
		return swaps;
	} 
	
	
	
}