//OBS: ny version rettet 9/10-2001
//Oprindelig version havde overtaget uhensigtsm¾ssighed i formulering af algoritmen fra
//Wirth (1976) som giver anledning til fejl i quicksort nŒr man, som her, splitter
//'partition' op i en egen metode.

//(Problemet ved Wirth's er at det partitionerede array ikke altid har omdrejningselementet
// (pivot) stŒende med mindre-eller-lig elementer til venstre og st¿rre-eller-lig
// til h¿jre)

public final class QSort
{
    private static void insertionSort( Comparable [ ] a, int low, int high )
    {
        for( int p = low + 1; p <= high; p++ )
        {
            Comparable tmp = a[ p ];
            int j;

            for( j = p; j > low && tmp.compareTo( a[ j - 1 ] ) < 0; j-- )
                a[ j ] = a[ j - 1 ];
            a[ j ] = tmp;
        }
    }


    public static void quicksort( Comparable [ ] a )
    {
        quicksort( a, 0, a.length - 1 );
    }

    public static void insertionSort( Comparable [ ] a )
    {
        for( int p = 1; p < a.length; p++ )
        {
            Comparable tmp = a[ p ];
            int j = p;

            for( ; j > 0 && tmp.compareTo( a[ j - 1 ] ) < 0; j-- )
                a[ j ] = a[ j - 1 ];
            a[ j ] = tmp;
        }
    }


    private static final int CUTOFF = 10;

    public static final void swapReferences( Object [ ] a, int index1, int index2 )
    {
        Object tmp = a[ index1 ];
        a[ index1 ] = a[ index2 ];
        a[ index2 ] = tmp;
    }

 
    private static void quicksort( Comparable [ ] a, int low, int high )
    {
        if( low + CUTOFF > high )
            insertionSort( a, low, high );
        else
        { int middle = ( low + high ) / 2;
	  int newPosForOldMiddleElt = partition(a, low, middle, high);
          quicksort( a, low, newPosForOldMiddleElt - 1 );
          quicksort( a, newPosForOldMiddleElt + 1, high );
        }
    }

/*private*/ public static int partition( Comparable [ ] a, int low, int pivotIndex, int high )
  //return new position for pivot element
  {  Comparable pivot = a[pivotIndex];
     int i = low-1; int j = high;
     swapReferences(a,pivotIndex,high);
     while(true)
       {while (a[++i].compareTo(pivot) < 0);
        while (a[--j].compareTo(pivot) > 0);
        if (i >= j) break;
        swapReferences(a, i, j);
       };
     swapReferences(a,i,high);
     return i;
    }
    
    
   public static String toStringArray(Object [] a)
     {String s="";
      for(int i=0; i < a.length; i++) s+=" "+a[i].toString();
      return s;}

   public static void main( String [ ] args )
    {  Integer [] a = new Integer [17];                        
       a[0] = new Integer(97);
       a[1] = new Integer(87);
       a[2] = new Integer(43);
       a[3] = new Integer(55);
       a[4] = new Integer(48);
       a[5] = new Integer(19);
       a[6] = new Integer(72);
       a[7] = new Integer(72);
       a[8] = new Integer(77);
       a[9] = new Integer(65);
       a[10] = new Integer(44);
       a[11] = new Integer(23);
       a[12] = new Integer(88);
       a[13] = new Integer(15);
       a[14] = new Integer(15);
       a[15] = new Integer(7);
       a[16] = new Integer(46);
       System.out.println(toStringArray(a));
       quicksort(a);
       System.out.println("Sorting...");
       System.out.println(toStringArray(a));
   
    }


}