/*
 *      Ordinamento.java
 *      
 *      Copyright 2010 alessandro 
 *      
 *      This program is free software; you can redistribute it and/or modify
 *      it under the terms of the GNU General Public License as published by
 *      the Free Software Foundation; either version 2 of the License, or
 *      (at your option) any later version.
 *      
 *      This program is distributed in the hope that it will be useful,
 *      but WITHOUT ANY WARRANTY; without even the implied warranty of
 *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *      GNU General Public License for more details.
 *      
 *      You should have received a copy of the GNU General Public License
 *      along with this program; if not, write to the Free Software
 *      Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 *      MA 02110-1301, USA.
 */
/**
 *  @author Alessandro 
 *  @version 0.1
 *  @see tuxerrante.blogspot.com
 */ 

import java.util.Random;
import java.io.IOException;
import java.util.Arrays;
import java.io.InputStreamReader;
import java.io.BufferedReader;

public class Ordinamento {

final static int dim=1000000; 

private static int[] disordina(int [] array){
Random generator = new Random();
for (int i=0; ilength; i++)
   array[i]= generator.nextInt(dim);
return array;
  }

public static void stampa(int[] array){
/* stampa */
for (int i=0; ilength; i++)
System.out.print(array[i]+" ");
  }


public static void main (String args[]) {  

int []array= new int [dim];  
int scelta=100;
long start = 0, end=0;
BufferedReader in = new BufferedReader ( new InputStreamReader(System.in));

// randomizza array
  array = disordina(array);

do {

System.out.println("\n\n");
//       scegli algoritmo
System.out.println("\t ORDINAMENTO ARRAY \n Scegli l'algoritmo: \n");
System.out.println(" 0. rigenera array casuale");
System.out.println("\nO(n²)");
System.out.print(" 1. selectionSort \n");
System.out.print(" 2. insertionSort \n");
System.out.print(" 3. BubbleSort \n");
System.out.println("\nO(nlogn) ");
System.out.print(" 4. QuickSort \n");
System.out.print(" 41. QuickSort del JDK (Bentley-McIlroy)\n");
System.out.print(" 42. MergeSort \n");

System.out.println("\nΘ(logn) ");
System.out.println(" 5. HeapSort ");

System.out.println("\n 8. Stampa ");
System.out.println(" 9. Esci ");
System.out.print(" ==> ");

try {
   scelta = Integer.parseInt(in.readLine());
  } 
catch ( IOException e) { 
System.err.println(" ERRORE: : "+ e.getMessage());   
   }

switch (scelta){

case 0 :     
     array=disordina(array);
break;

case 1: 
     start = System.currentTimeMillis();
     array = AlgOrdinamento.selectionSort(array);
     end = System.currentTimeMillis();     
break;

case 2: 
     start = System.currentTimeMillis();
     array = AlgOrdinamento.insertionSort(array);
     end = System.currentTimeMillis();     
break;

case 3: 
     start = System.currentTimeMillis();
     array = AlgOrdinamento.bubbleSort(array);
     end = System.currentTimeMillis();     
break;     
case 4: //  QUICKSORT
     start = System.currentTimeMillis();
     AlgOrdinamento.quickSort(array, 0, array.length-1 );
     end = System.currentTimeMillis();     
break;

case 41: //  QUICKSORT AT&T jdk
     start = System.currentTimeMillis();
Arrays.sort(array);
     end = System.currentTimeMillis();     
break;

case 42: //  MERGESORT
    start = System.currentTimeMillis();
    AlgOrdinamento.mergesort(array,0,array.length-1);    
    end = System.currentTimeMillis();      
break;

case 5: //  HEAPSORT
    start = System.currentTimeMillis();
    AlgOrdinamento.heapSort(array, array.length);
    end = System.currentTimeMillis();     
break;  

case 8: 
stampa(array);
break;     

case 9: System.exit(0);
default: System.out.println(" Inserisci un valore adeguato. "); break;   
   }

System.out.println("\n\n\t Tempo esecuzione : "+(end-start)+" ms");
    } while( true);   

 } //--end main


}
// ___________________________________________________________________________________________

class AlgOrdinamento {

/**
  * algoritmo SelectionSort(array a) 
  *   for k=0 to n-2 do
  *   m = k+1
  *   for j=k+2 to n do
  *    if ( A[j][m] ) m=j;
*   scambia A[m] con A[k]
*  
*  ordina in loco n elementi eseguendo al più O(n²) confronti
*/

 public static int[] selectionSort(int[] a){
  int k=0, m=0, j=0, temp;

  for ( k=0; k< (a.length-2); k++){
   m = k+1;
   for (j=k+2; j j++)
    if (a[j]< a[m]) m=j;
   temp=a[m];
   a[m]=a[k];
   a[k]=temp;
}
  return a;  
}

/**
* algoritmo insertionSort( Array A) 
*  1) individua la posizione j del più grande elemento minore di x, se esiste
*  2) altrimenti sarà posto a zero per indicare che x andrà posto all'inizio
*  3) j+1 è la posizione dove sarà inserito x
*  ordina in loco n elementi eseguendo al più O(n²) confronti 
*/
 public static int[] insertionSort(int a[]){
  int x, k, j, t;
  for ( k=0; k k++){
   x = a[k+1];
   for ( j=k; j>=0; j--) // 1
    if (a[j]<=x) break;
   if (j)
    for ( t=k; t>j+1; t--)
     a[t+1]=a[t];
   a[j+1]=x;   
   }
  
  return a;  
  }
  
 /**
  *  bubbleSort
  *   in ogni scansione vengono confrontate coppie di elementi adiacenti
  *   che vengono scambiate se non ordinate
  *   se durante una scansione non vengono effettuati scambi, l'alg termina.* 
  *   F = O(n²)
  */
public static int[] bubbleSort(int[] a){
int i,j,temp;
boolean scambi;
for (i=1; ilength-1; i++){
    scambi=false;
for (j=1; jlength-i+1; j++)
if( a[j-1] > a[j] ){
      temp=a[j-1];
      a[j-1]=a[j];
      a[j]=temp;
      scambi=true;
      }
if (!scambi) break;
    }
return a;
  }


/** ___________ QUICKSORT
  * 
  */
public static void quickSort(int []a,int i,int f){
if (i>=f) return;
int m = partiziona(a,i,f);
quickSort(a,i,m-1); // possibile stackOverflow se già ordinato
quickSort(a,m+1,f);

  }
private static int partiziona(int []a,int i,int f){
int x = a[i], inf=i, temp;

while (true){

while ( infwhile ( a[f]>x ) f--;
if ( inf     temp=a[inf]; a[inf]=a[f]; a[f]=temp;
     }
else break;
   }
  temp=a[i]; a[i]=a[f]; a[f]=temp; // posiziona pivot al centro
return f;
  }

/**
   * HEAPIFY
   * @param h array da ordinare
   * @param index  indice di scansione  
   * @return array ordinato secondo la struttura albero binario
   */
private static void heapify( int[] h,int index, int heapSize){
int sin=2*index+1, des=2*index+2, max=0;

if ( sinh[index]) max=sin;
else max=index;

if ( desh[max]) max=des; // confronto il figlio destro con il padre
// nota che il padre potrebbe essere l'ex sin() 

if (index!=max) {
swap(h,index,max);
heapify(h,max, heapSize);
    }

  }

static void heapSort(int A[], int n)
  {
int i, HeapSize = n;

for (i= HeapSize/2; i >= 0; i--)
heapify(A,i,HeapSize);

for (i=n-1 ; i>=1; i--) {
swap( A, i, 0 );
            HeapSize--;
heapify(A,0,HeapSize);
       }
  }

private  static void swap (int []h, int x, int y){
int sw=h[x];
   h[x]=h[y];
   h[y]=sw;      
  }
/** HEAPSORT
   *  dato un array genera un albero fittizio nello stesso array (heap binario), 
   *  dove il valore di un nodo è sempre maggiore di quello dei suoi figli.
   */ 
/*  public static void heapSort(int[] a){
   heapify(a,0); // crea l'heap dall'array su sé stesso   
   return;   
  } */

/**_________ MERGESORT 
   * 
   */
public static void mergesort(int []A, int i, int f){
if (i>=f) return;
int m=(i+f)/2; 
mergesort(A,i,m);
mergesort(A,m+1,f);
merge(A,i,m,f);
  }

private static void merge(int []A, int i1, int f1, int f2){
int []X= new int[f2-i1+1];
int i=0, i2 = f1+1, left=i1;

while (i1<=f1 && i2<=f2){
if ( A[i1]<=A[i2]){
     X[i]=A[i1];
     i1++;
    }
else {
     X[i]=A[i2];
     i2++;
    }
    i++;    
   }

//se i e' minore di center significa che alcuni elementi 
//della prima meta' non sono stati inseriti nel vettore
// copia A[i1, f1] alla fine di X     
for (; i1<=f1; i1++, i++) 
     X[ i ]= A[i1];    
// copia A[i2, f2] alla fine di X
for (; i2<=f2; i++, i2++) 
     X[ i ]= A[i2];

for (int k=left; k<=f2; k++)
    A[k]=X[k-left];
  }  

 }