package esami; public class dicembre18 { public static void main(String[] args) { // TODO Auto-generated method stub int[] a={22, -6,11, -12, 17, 15, 30, 3, 9, 26}; int[] b={2, 7, 9, 0,33,24, 77}; stampaArray(a); insertionSort(a); stampaArray(a); stampaArray(b); insertionSort(b); stampaArray(b); System.out.println(sommaRic(a)); System.out.println(sommaRic(b)); System.out.println(binarySearch(a, 17)); System.out.println(binarySearch(b, 34)); } static void stampaArray (int[]a) { if (a==null) { System.out.println("Array non inizializzato"); return; } System.out.print("{ "); for (int i=0; i a[j] ) candidato=j; // c7 | somma(i da 0 a n-1) (n-i-1) volte // =n(n-1)/2 volte temp=a[i]; // c8 | n volte a[i]=a[candidato]; // c9 | n volte a[candidato]=temp; // c10| n volte } } /* Complessità sort C(n) è dell'ordine di n al quadrato */ static void insertionSort (int[] a) { //dimensione dell'input n=a.length if (a==null|| a.length==0) return; // c1 | 1 volta for(int i=1;i=0 && a[j]>key; j--){ // c5 | somma(i da 1 a n-1) (i+1) volte a[j+1]=a[j]; // c6 | somma(i da 1 a n-1) (i) volte } a[j+1]=key; // c7 | n volte } } /* Complessità sort C(n) è dell'ordine di n al quadrato */ static int sommaRic (int[] a) { // dimensione dell'input n=a.length if (a==null || a.length ==0) return 0; return sommaRic (a, 0, a.length-1);} static int sommaRic (int[] a, int l,int r){ //dimensione dell'input n=r-l+1 //CASO BASE if (l==r) return a[l]; // c1 | 1 volta //CASO NON BASE int m=(l+r)/2; // l<=m1 * RISOLVENDO C(n) è dell'ordine di n */ static int binarySearch (int[] a, int v) //dimensione dell'input n=a.length //a si suppone ordinato {if (a==null || a.length ==0) return -1; return binarySearch (a, v, 0, a.length-1);} static int binarySearch (int[] a, int v, int l,int r) { //dimensione dell'input n=r-l+1 //CASO BASE if (l==r) {if (a[l]==v) return l; else return -1;} // c1 | 1 volta //CASO NON BASE int m=(l+r)/2; // l<=m1 * RISOLVENDO C(n) è dell'ordine di log(n) */ }