Tra le prime cose che si studiano in informatica, almeno per chi sceglie di fare il programmatore, c’è l’ordinamento di un array.
I benefici computazionali di avere una sequenza di dati ordinata sono molteplici. Pensiamo ad esempio ad una ricerca di un elemento in un array. Se abbiamo la sequenza ordinata possiamo applicare algoritmi decisamente più efficienti della ricerca sequenziale, ad esempio potremmo applicare una ricerca dicotomica ed effettuare invece di n tentativi nel caso peggiore, “log n” tentativi (logaritmo in base due di n). Per capirci se la sequenza di dati contiene 65536 elementi nel caso di ricerca sequenziale, nel caso peggiore (stiamo cercando proprio 65536), l’algoritmo impiegherebbe 65536 confronti, mentre quello dicotomico, nel caso di array ordinato, Log2 65536 = 16 confronti.
I benefici in termini di tempo sarebbero come dire logaritmici, ma a questi bisognerebbe aggiungere i tempi per tenere ordinato l’array, ma questa è un’altra questione e non è quello di cui vogliamo parlare.
Infatti non sempre serve avere per forza un array ordinato per avere dei benefici. Non sempre l’ordine è la cosa che serve di più in informatica.Pensiamo ad esempio ad un gioco di carte.
Come simulare l’atto del mazziere che mischia le carte?
Diamo per assunto che un mazzo di carte ipotetico si può rappresentare con un array di 54 interi
private static int [] array= { 9,4,3,2,6,7,8,5,0,1,
13,12,11,14,15,17,16,10,19,18,
24,23,22,25,27,20,26,21,29,28,
32,34,31,33,36,35,38,37,39,30,
41,46,45,44,43,40,42,48,47,49,
51,53,52,50
};
Il codice Java seguente mostra un “didattico” algoritmo di ordinamento a cicli fissi implementato nel metodo doSort() ed un banalissimo metodo doMess() che genera degli indici casuali su cui applicare uno scambio di dati all’interno dell’array tramite il metodo doSwap().
/*
* Net-1 Coding
* How to unsort an array after you've sorted it.
*/
package orderdisorder;
/**
*
* @author Administrator
*/
public class Main {
/**
* @param args the command line arguments
*/
private static int [] array= { 9,4,3,2,6,7,8,5,0,1,
13,12,11,14,15,17,16,10,19,18,
24,23,22,25,27,20,26,21,29,28,
32,34,31,33,36,35,38,37,39,30,
41,46,45,44,43,40,42,48,47,49,
51,53,52,50
};
private static int disorderDegree=100;
public static void main(String[] args) {
System.out.println("Before Sorting...");
doShowArray();
System.out.println("Sorting...");
doSort();
System.out.println("After Sorting...");
doShowArray();
System.out.println("Let's do some mess...");
doMess();
System.out.println("After my messy method...");
doShowArray();
}
private static void doSwap(int i,int j) {
int swap=array[i];
array[i]=array[j];
array[j]=swap;
}
private static void doSort(){
int min;
for(int i=0;iarray[j]) {
min=array[j];
doSwap(j,i);
}
}
}
}
private static void doShowArray(){
for(int i=0;i
Buona partita.
