/* 
*  COMPSCI.220S1.T -- 2003
*  Sorting methods: insertionSort, 
*                   shellSort, 
*                   mergeSort, 
*                   quickSort, 
*                   heapSort
*  This file contains class methods for
*  sorting integer arrays. The methods
*  are described in detail in handouts
*  and the coursebook.
*/ 


  //    cutoff threshold for quickSort

  static public int CUTOFF = 10; 

  //---------------------------------------------
  //    insertion sort algorithm 
  //    a[]  an integer array to be sorted 
  //--------------------------------------------- 
 
  public static void insertionSort(int [] a) { 
    int i, tempi, k; 
 
    for( i = 1; i < a.length; i++ ) { 
      tempi = a[ i ]; 
      k = i - 1; 
      while( k >= 0 && tempi < a[ k ] ) { 
	a[ k + 1 ] = a[ k ]; 
	k--; 
      } 
      a[ k + 1 ] = tempi; 
    } 
  } 
 
  //---------------------------------------------
  //    Shell's sort algorithm 
  //    a[]  an integer array to be sorted 
  //--------------------------------------------- 
 
  public static void shellSort(int [] a) { 
    int i, tempi, k, gap; 
 
    for( gap = a.length / 2; gap > 0; 
        gap = ( gap == 2 )?  1 : (int)( gap / 2.2 ) ) 
      for( i = gap; i < a.length; i++ ) { 
	tempi = a[ i ]; 
	k = i; 
	while( k >= gap && tempi < a[ k - gap ]) { 
	  a[ k ] = a[ k - gap ]; 
	  k -= gap; 
	} 
	a[ k ] = tempi; 
      } 
  } 
 
  //---------------------------------------------
  //    merge sort algorithm 
  //    a[]  an integer array to be sorted 
  //
  //    private methods: 
  //      mergeSort() - recursive split / merge
  //         of a subarray (a[left],...,a[right])
  //      merge() - merge two presorted subarrays 
  //--------------------------------------------- 
 
  public static void mergeSort( int [] a ) { 
    int []tmpArray = new int[ a.length ]; 
    mergeSort( a, tmpArray, 0, a.length - 1 ); 
  } 
 
  private static void  mergeSort( 
                         int [] a,   
                         int [] tmpArray,   
                         int left,  int right ) { 
    if ( left < right ) { 
      int centre = ( left + right ) / 2; 
      mergeSort( a, tmpArray, left, centre); 
      mergeSort( a, tmpArray, centre + 1, right); 
      merge( a, tmpArray, left, centre + 1, right ); 
    } 
  } 
 
  private static void merge( 
                         int [] a,  
                         int [] tmpArray,   
                         int leftPos,  int rightPos, 
                         int rightEnd ) { 
    int leftEnd = rightPos - 1; 
    int tmpPos = leftPos; 
    int leftBeg = leftPos; 
     
    // Main merging loop 
    while( leftPos <= leftEnd && rightPos <= rightEnd ) 
      if ( a[ leftPos ] < a[ rightPos ] )  
        tmpArray[ tmpPos++ ] = a[ leftPos++ ]; 
      else 
        tmpArray[ tmpPos++ ] = a[ rightPos++ ]; 
 
    // Copy the rest of the first half if any
    while( leftPos <= leftEnd ) 
      tmpArray[ tmpPos++ ] = a[ leftPos++ ];      
 
    // Copy the rest of the second half if any 
    while( rightPos <= rightEnd ) 
      tmpArray[ tmpPos++ ] = a[ rightPos++ ]; 
 
    // Copy tmpArray back 
    for( tmpPos=leftBeg; tmpPos <= rightEnd; tmpPos++ ) 
      a[ tmpPos ] = tmpArray[ tmpPos ]; 
  } 
 
  //---------------------------------------------
  //    quicksort algorithm 
  //    a[]  an integer array to be sorted 
  //
  //    private methods: 
  //      quickSort() - choose a median-of-three
  //        pivot for partitioning a subarray 
  //        (a[low],...,a[high]) and recursively
  //        sort the parts
  //      swap() - swap elements of an array
  //      insertionSort() - insertion sort of a
  //        subarray 
  //--------------------------------------------- 
 
  public static void quickSort( int [] a ) { 
    quickSort( a, 0, a.length - 1 ); 
  } 
 
  private static void quickSort( int  [] a,  
	              int low,   int high) { 
      if( low + CUTOFF > high ) 
		     insertionSort( a, low, high ); 
      else { 
	// Sort low, middle, high 
	int middle = ( low + high ) / 2; 
	if ( a[ middle ] < a[ low ]    ) 
	  swapElements( a, low, middle  ); 
	if ( a[ high ]   < a[ low ]    ) 
	  swapElements( a, low, high    ); 
	if ( a[ high ]   < a[ middle ] ) 
	  swapElements( a, middle, high ); 
 
	// Place pivot at position high - 1 
	swapElements( a, middle, high - 1 ); 
	int pivot = a[ high - 1]; 
 
	// Begin partitioning 
        int i, j; 
	for( i = low, j = high - 1; ; ) { 
	  while( a[ ++i ] < pivot ); 
          while( pivot < a[ --j ] ); 
          if ( i < j ) 
	    swapElements( a, i, j ); 
	  else 
	    break; 
	} 
 
	// Restore pivot 
	swapElements( a, i, high - 1 ); 
 
	quickSort( a, low, i - 1 ); // Sort small elements 
	quickSort( a, i + 1, high ); // Sort large elements 
      } 
  } 
 
  private static void swapElements( int [] a,  
	                        int i, int j ) { 
    int temp = a[ i ]; 
    a[ i ] = a[ j ]; 
    a[ j ] = temp; 
  } 
 
  private static void insertionSort(int [] a,  
			  int low,  int high) { 
    int i, tempi, k; 
 
    if (low > high || low < 0 || high >= a.length ) { 
       low = 0;
       high = a.length - 1;
    } 
    for( i = low + 1; i <= high; i++) { 
       tempi = a[ i ]; 
       k     = i - 1; 
       while( k >= low && tempi < a[ k ] ) { 
	 a[ k+1 ] = a[ k]; 
	 k--; 
       } 
       a[ k+1 ] = tempi; 
    } 
  } 

  //---------------------------------------------
  //    heapsort algorithm 
  //    a[]  an integer array to be sorted 
  //
  //    private methods: 
  //      heapify() - convert a subarray to a heap
  //      swap() - swap elements of an array
  //--------------------------------------------- 
  public static void heapSort( int [] a ) { 
    int index;
 
    // build heap 
    for( index = a.length / 2 - 1; index >= 0; 
                                         index-- )
      heapify( a, index, a.length ); 

    // deleteMax 
    for( index = a.length - 1; index >= 1; 
                                       index-- ) { 
      swapElements( a, 0, index );
      heapify( a, 0, index ); 
    } 
  } 
  
  private static void heapify( int [] a, 
                               int index, 
                               int size ) { 
    int childPos;  
    int parentPos = index + 1; 
    // position is equal to index plus 1; 

    for( childPos = parentPos * 2; childPos < size;  
		          childPos = parentPos * 2 ) {	 
      if ( a[ parentPos - 1 ] < a[ childPos - 1 ] || 
		a[ parentPos - 1 ] < a[ childPos ] ) {  
	if ( a[ childPos - 1 ] < a[ childPos] ) { 
	  swapElements( a, parentPos - 1, childPos ); 
	  parentPos = childPos + 1; 
	} 
	else { 
	  swapElements( a, parentPos - 1, childPos - 1 ); 
	  parentPos = childPos; 
        } 
      } 
      else break; 
    } 
    if ( childPos == size && 
        a[ parentPos - 1 ] < a[ childPos - 1 ] ) 
      swapElements( a, parentPos - 1, childPos - 1 ); 
  }