package scratchpad;
 
import java.math.*;
 
class SortInsertion {
  // Insertion sort
  public static <T extends Comparable>
  void insertion_sort ( T[] list, int size )
  {
    for ( int i = 1; i < size; i++ ) {
      T save = list[i];
      int j = i;
 
      while ( j >= 1 && save.compareTo ( list[j - 1] ) < 0 ) {
        list[j] = list[j - 1];
        --j;
      }
 
      list[j] = save;
    }
  }
 
  // Shell sort
  public static <T extends Comparable>
  void shell_sort ( T[] list, int size )
  {
    int h = 1;
 
    while ( h <= size / 9 ) {
      h = 3 * h + 1;
    }
 
    while ( h > 0 ) {
      for ( int i = h; i < size; i++ ) {
        T save = list[i];
        int j = i;
 
        while ( j >= h && save.compareTo ( list[j - h] ) < 0 ) {
          list[j] = list[j - h];
          j -= h;
        }
 
        list[j] = save;
      }
 
      h /= 3;
    }
  }
}
 
class SortExchange {
  // Bubble sort
  public static <T extends Comparable>
  void bubble_sort ( T[] list, int size )
  {
    int bound = size - 1;
 
    while ( bound > 0 ) {
      int new_bound = 0;
 
      for ( int i = 0; i < bound; i++ ) {
        if ( list[i].compareTo ( list[i + 1] ) > 0 ) {
          T save = list[i];
          list[i] = list[i + 1];
          list[i + 1] = save;
 
          new_bound = i;
        }
      }
 
      bound = new_bound;
    }
  }
 
  // Quicksort
  private static <T extends Comparable>
  void quicksort ( T[] list, int l, int r )
  {
    int[] stack = new int[50];
    int m, top = 0;
    T pivot;
 
    while ( true ) {
      while ( r > l + 10 ) {
        // Median of three partition
        m = ( l + r ) / 2;
 
        if ( list[l].compareTo ( list[m] ) > 0 ) {
          T save = list[l]; list[l] = list[m]; list[m] = save;
        }
        if ( list[l].compareTo ( list[r] ) > 0 ) {
          T save = list[l]; list[l] = list[r]; list[r] = save;
        }
        if ( list[m].compareTo ( list[r] ) > 0 ) {
          T save = list[m]; list[m] = list[r]; list[r] = save;
        }
 
        if ( r - l <= 2 ) {
          break;
        }
 
        pivot = list[m];
        list[m] = list[r - 1];
        list[r - 1] = pivot;
 
        int i = l;
        int j = r - 1;
 
        while ( true ) {
          while ( list[++i].compareTo ( pivot ) < 0 ) {
            // No body
          }
          while ( list[--j].compareTo ( pivot ) > 0 ) {
            // No body
          }
 
          if ( j < i ) {
            break;
          }
 
          T save = list[i];
          list[i] = list[j];
          list[j] = save;
        }
 
        pivot = list[i];
        list[i] = list[r - 1];
        list[r - 1] = pivot;
 
        // Simulated recursive calls
        if ( j - l > r - i ) {
          stack[top++] = l;
          stack[top++] = j;
          l = i + 1;
        }
        else {
          stack[top++] = i + 1;
          stack[top++] = r;
          r = j;
        }
      }
 
      if ( top == 0 ) {
        break;
      }
 
      r = stack[--top];
      l = stack[--top];
    }
  }
 
  public static <T extends Comparable>
  void quicksort ( T[] list, int size )
  {
    quicksort ( list, 0, size - 1 );
    SortInsertion.insertion_sort ( list, size );
  }
}
 
class SortSelection {
  // Selection sort
  public static <T extends Comparable>
  void selection_sort ( T[] list, int size )
  {
    for ( int i = 0; i < size - 1; i++ ) {
      int min = i;
 
      for ( int j = i + 1; j < size; j++ ) {
        if ( list[j].compareTo ( list[min] ) < 0 ) {
          min = j;
        }
      }
 
      if ( min != i ) {
        T save = list[i];
        list[i] = list[min];
        list[min] = save;
      }
    }
  }
 
  // Heapsort
  private static <T extends Comparable>
  void push_down ( T[] list, int l, int r )
  {
    int i, j;
 
    for ( i = l; ( j = i * 2 + 1 ) <= r; i = j ) {
      if ( j + 1 <= r && list[j + 1].compareTo ( list[j] ) > 0 ) {
        ++j;
      }
 
      T save = list[i];
      list[i] = list[j];
      list[j] = save;
    }
 
    while ( true ) {
      j = ( i - 1 ) / 2;
 
      if ( j < l || j == i || list[j].compareTo ( list[i] ) > 0 ) {
        break;
      }
 
      T save = list[i];
      list[i] = list[j];
      list[j] = save;
 
      i = j;
    }
  }
 
  public static <T extends Comparable>
  void heapsort ( T[] list, int size )
  {
    if ( size-- < 2 ) {
      return;
    }
 
    int i;
 
    for ( i = ( size - 1 ) / 2; i >= 0; i-- ) {
      push_down ( list, i, size );
    }
 
    while ( size > 0 ) {
      T save = list[size];
      list[size] = list[0];
      list[0] = save;
 
      push_down ( list, 0, --size );
    }
  }
}
 
public class Main {
  public static void main ( String[] args )
  {
    Integer[] a = new Integer[20];
 
    for ( int i = 0; i < 20; i++ ) {
      a[i] = (int)( Math.random() * 100 );
    }
 
    System.out.println ( "Before: " );
    for ( int i : a ) {
      System.out.print ( i + " " );
    }
    System.out.println ( "" );
 
    // Insert your sorting method of choice here
 
    System.out.println ( "After: " );
    for ( int i : a ) {
      System.out.print ( i + " " );
    }
    System.out.println ( "" );
  }
}