public class Selection {
public static void sort(Comparable[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
int min = i;
for (int j = i+1; j < n; j++) {
if (less(a[j], a[min])) min = j;
}
exch(a, i, min);
}
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}
}
Above is the code for Selection sort in java
public class Insertion {
public static void sort(Comparable[] a) {
int n = a.length;
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && less(a[j],a[j-1]); j--) {
exch(a,j,j-1);
}
}
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static void exch(Comparable[] a, int i, int j) {
Comparable swap = a[i];
a[i] = a[j];
a[j] = swap;
}
}
Above is the code for Insertion sort in java
import java.util.Random;
public class SortCompare {
public static double time(String alg, Double[] a) {
Stopwatch sw = new Stopwatch();
if (alg.equals("Insertion")) Insertion2.sort(a);
else if (alg.equals("Selection")) Selection.sort(a);
else throw new IllegalArgumentException("Invalid algorithm: " + alg);
return sw.elapsedTime();
}
// Use alg to sort trials random arrays of length n.
public static double timeRandomInput(String alg, int n, int trials) {
double total = 0.0;
Random r=new Random();
Double[] a = new Double[n];
// Perform one experiment (generate and sort an array).
for (int t = 0; t < trials; t++) {
for (int i = 0; i < n; i++)
a[i] = r.nextDouble();
total += time(alg, a);
}
return total;
}
public static void main(String[] args) {
String alg1 = args[0];
String alg2 = args[1];
int n = Integer.parseInt(args[2]);
int trials = Integer.parseInt(args[3]);
double time1, time2;
time1 = timeRandomInput(alg1, n, trials); // Total for alg1.
time2 = timeRandomInput(alg2, n, trials); // Total for alg2.
System.out.printf("For %d random Doubles\n %s is", n, alg1);
System.out.println();
System.out.printf(" %.1f times faster than %s\n", time2/time1, alg2);
}
}
Above is the test code to compare the speed of the two sort
Below is the result
For 1000 random Doubles
Insertion is
0.7 times faster than Selection
below is the helper class to measure the time
public class Stopwatch {
private final long start;
/**
* Initializes a new stopwatch.
*/
public Stopwatch() {
start = System.currentTimeMillis();
}
/**
* Returns the elapsed CPU time (in seconds) since the stopwatch was created.
*
* @return elapsed CPU time (in seconds) since the stopwatch was created
*/
public double elapsedTime() {
long now = System.currentTimeMillis();
return (now - start) / 1000.0;
}
}
why the Insertion sort is slower than selection sort?
i see the Algorithms Fourth Edition says the Insertion sort is faster than selection sort and the result the book acquire is 1.7times.but what i conclude is 0.7 or 0.8 times