Comparison of sorting algorithms 26/04/10 Added mergesort and other changes.
A small program in java that allows compare the differences in efficiency (in time) among the most popular sorting algorithms: selection sort
* 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 Order { static final int dim = 1000000 ;
private static int [] disorderly (
int [] array) {Random
generator = new Random (); for (
int i = 0; i \u0026lt;array. length
i + +) array [i] = generator. nextInt (dim);
return array; }
public
static void
stampa
( int [] array){ /* stampa */
for
( int i= 0 ; i<array. length ; i++) System
. out . print (array[i]+ " " ); }
public static void main (
String args []) {
int [] array = new
int [dim]; int choice = 100 ; long start = 0
, end = 0 ;
BufferedReader in = new
BufferedReader (new InputStreamReader ( System .
in
));
/ / randomize array disorderly array = (array); do {
System. out.
println ( " \\ n \\ n
" ) / / choose algorithm
System. out. println ( " \\ t ORDER ARRAY \\ n Select the algorithm: \\ n " )
System.
out. println (
"0. Regenerates random array"
)
System. out. println ( " \\ n O (n ²)" ); System
. out. print
( "1 selectionSort \\ n " ); System . out. print ( "2 insertionsort \\ n " );
System . out. print ( "3 BubbleSort \\ n
" ); System . out. println ( " \\ n
O (nlogn) ") System . out . print (" 4. QuickSort \\ n
") System . out . print ( "41. QuickSort JDK (Bentley-McIlroy) \\ n
" ) System . out . print ( "42. mergesort \\ n
") System . out . println ("
\\ n Θ (log N) ") System . out . println (" 5. Heapsort ")
System . out . println (" \\ n 8. Stampa
) System . out . println ( 9. Quit ) System
. out . print ( "==>" ) try {choice = 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; homes
9 : System.
exit (0
)
default : System. out.
println ( "Enter an appropriate value." ) break;}
System. out. println ( "
\\ n \\ n \\ t Execution time:"
+ (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] <A [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 <a.length;
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 <a.length-1; k
++){ x = a[k+1];
for
( j= k; j > =0; j--) // 1
if (a[j] < =x) break; if (j
<k ) for ( t = k; t >
j +1, t -) to [t +1] = a [t];
a [j +1] = x;}
return a;}
/ **
* BubbleSort * in each scan are compared to pairs of adjacent elements * 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 ; i<a.
length - 1 ; i++){ scambi=
false ; for (j=
1 ; j<a. length -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 (inf \u0026lt;f & & a [sub] \u0026lt; = x) sub + +; while (a [f]> x) f -;
if (inf \u0026lt;f) {temp = a [sub] a [sub] = a [f]; a [f] = temp;}
else break;}
temp = a [i], a [i] = a [f] to [f] = temp; / / set pivot the center return f;}
/ ** *
HEAPIFY * @ param
h
array to be sorted
*
@ param index
index scan
*
@ return array sorted by the structure binary albero * / private
static void heapify ( int [] h, int index, int heapsize) {int no = 2 * index + 1 , des = 2 * index + 2, max = 0
; if (without \u0026lt;heapSize && h[sin]> h [ index]) max = no; else max = index; if (des \u0026lt;heapsize & & h[des]>h[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]; } }
Altri confronti.
Animazioni interattive degli algoritmi.
sabayon alex # 
START 
CLRF CK_PREC 
GOTO UPDATE 
CHECK CHECK 
or: 
Project per 
(a version made by me "and that of 
* Ordinamento.java 
Monticelli – GELLI K 6-0 
