package inplacecountingsort;

/**
 * <p>Title: in place counting sort</p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2002</p>
 * <p>Company: </p>
 * @author Burton Rosenberg
 * @version 7 June 2002
 */

public class InPlaceCountingSort {

  public static void main(String[] args) {
     //int [] a = { 1, 2, 3, 4, 5 } ;
     //int [] a = { 5, 4, 3, 2, 1 } ;
     //int [] a = {1, 1, 1, 1 } ;
     //int [] a = { 3, 0, 5, 6, 6, 2, 8, 6, 4, 3 } ;
     int [] a = { 2, 2, 3, 0, 6, 6, 2, 8, 6, 4, 3 } ;

     printArray("\nInitial array:", "a", a) ;
     inPlaceCountingSort( a ) ;
     printArray("\nFinal array:", "a", a) ;
  }

  static
  int [] createCountArray( int [] a ) {
     int max = 0 ;
     for ( int i=0; i<a.length; i++ ) {
        if ( a[i]<0 ) return null ;
        if ( a[i]>max ) max = a[i] ;
     }
     return new int [max+1] ;
  }

  static
  void initCountArray( int [] a, int [] c ) {
     for ( int i=0; i<a.length; i++ ) c[a[i]]++ ;
     c[0]-- ; // adjust for 0 based arrays.
     for ( int i=1; i<c.length; i++ ) c[i] += c[i-1] ;
  }

  static
  void iterateReplacement( int [] a, int [] c, int k ) {
     int value = a[k] ;
     int nextIndex = c[value] ;
System.out.println("\nenter iterateReplacement:") ;
System.out.print("  cycle of indices: "+k+" -> ");
     while ( nextIndex>k ) {
System.out.print(nextIndex+" -> ") ;
        c[value]-- ;
        int temp = a[nextIndex] ;
        a[nextIndex] = value ;
        value = temp ;
        nextIndex = c[value] ;
     }
System.out.println(k) ;
     if (nextIndex==k) a[k] = value ;
  }

  static
  void inPlaceCountingSort( int [] a ) {
     int [] c = createCountArray(a) ;
     if ( c==null ) return ;
     initCountArray( a, c ) ;
     printArray("\nCounting Array", "c", c) ;
     for ( int i=0 ; i<a.length-1; i++ ) {
        printArray("\nIntermediate array", "a", a ) ;
        iterateReplacement( a, c, i ) ;
     }
  }

  static
  void printArray( String title, String arrayName, int [] a ) {
     System.out.println(title) ;
     for ( int i=0; i<a.length; i++ )
        System.out.println(arrayName+"["+i+"] = "+a[i]) ;
  }
}