class QuickSort{

  public static void main(String[] args){

    int[] arr = new int[30];

    fillArray(arr,10);

    System.out.println("Unsorted:");
    print(arr);

    quicksort(arr);
    System.out.println("\nSorted:");
    print(arr);

  }


  static void fillArray(int[] a, int m){
    for(int i = 0; i<a.length; i++)
      a[i] = (int)(Math.random()*m);
  }

  static void quicksort(int[] a){
    qsort(a,0,a.length-1);
    return;
  }

  static void qsort(int[] a, int l, int r){
    if(l < r){
      int i = l;
      int j = r;
      int x = a[(i+j)/2];
      do{
	while(a[i]<x) i++;
	while(a[j]>x) j--;
	if(i<=j)
	{
	  swap(a,i,j);
	  i++;
	  j--;
	  }
      }while(i<=j);
      qsort(a,l,j);
      qsort(a,i,r);
    }
    return; 
  }  

  static void swap(int[] a, int s, int t)
  {
    int temp = a[s]; a[s] = a[t]; a[t] = temp;
    return;
  }

  static void printArray(int[] a){
    for(int i = 0; i<a.length; i++)
      System.out.println(a[i]);
    return;
  }

  static void print(int[] a){
    for(int i = 0; i<a.length; i++)
      System.out.print(a[i] + " ");
    System.out.println();
    return;
  }

}