package basics.methods;

import java.util.Arrays;
import java.util.Random;
import basics.testing.Test;

public class Quicksort
{
public void quicksort(int array[], int links, int rechts)
{
   int pivot, temp;
   int l, r;
   if(links < rechts)
   {
      l = links;
      r = rechts;
      pivot = array[(links + rechts) >> 1];
      do
      {
         while(array[l] < pivot)
            l++;
         while(array[r] > pivot)
            r--;
         if(l <= r)
         {
            temp = array[r];
            array[r] = array[l];
            array[l] = temp;
            l++;
            r--;
         }
      } while(l <= r);
      quicksort(array, links, r);
      quicksort(array, l, rechts);
   }
}

static Random random = new Random();

public static void fillArray(int [] array)
{
   int r = random.nextInt(3 * array.length);
   for(int i = 0; i < array.length; i++)
   {
      array[i] = random.nextInt(r + 1);
   }
}

public static void unittest()
{
   int [] array = new int [100];
   for(int i = 0; i < 1000; ++i)
   {
      fillArray(array);
      int [] array2 = (int [])array.clone();
      new Quicksort().quicksort(array, 0, array.length - 1);
      Arrays.sort(array2);
      if(!Test.assertTrue(Arrays.equals(array, array2),
         "Quicksort: result differs from array sort!"))
      {
         Test.printout("QS sorted:[");
         StringBuffer sb = new StringBuffer();
         for(int j = 0; j < array.length; ++j)
            sb.append(array[j] + " ");
         Test.printout(sb.toString());
         Test.printout("]");
         sb = new StringBuffer();
         for(int j = 0; j < array2.length; ++j)
            sb.append(array2[j] + " ");
         Test.printout(sb.toString());
         Test.printout("]");
      }
   }
}
}